React Internals (Diffing Algorithm)

PayPal's "React Internals (Diffing Algorithm)" interview question focuses on explaining React's reconciliation process, particularly list diffing with keys, as no single public source provides a formal "problem statement" with I/O examples and constraints matching those exact tags.[1][2]

Problem Overview

Interviewees are typically asked to describe how React's diffing algorithm compares old and new virtual DOM trees for arrays of children (e.g., lists), handling insertions, deletions, moves, and reorders efficiently using heuristics and keys. The core challenge is understanding why React avoids O(n³) general diffing in favor of O(n) optimizations via assumptions like type stability and unique keys.[5][9][1]

Key Assumptions

React relies on these heuristics:

• Different element types (e.g., <div> vs <span>) produce entirely different subtrees, triggering full rebuilds.[2][5]
• Lists use stable key props to match elements across renders; without keys or with indices, React assumes positional identity, causing unnecessary re-renders.[9][1]

Core Algorithm Steps

1. Compare root nodes by type; mismatch destroys/recreates the subtree.[2][5]
2. For matching types, diff attributes/props.[2]
3. For child arrays, perform list diffing:
   • Traverse from start with two pointers (oldFiber, newIdx).[1]
   • Match by key first, then type/index.
   • Reuse matching fibers (newFiber.alternate); delete mismatches (deleteChild).[1]
   • Handle remaining old children via mapRemainingChildren for key-based reuse or deletion.[1]

Example Scenarios

No formal test cases exist publicly, but common illustrations include:

Input (Old Children): [<A key="a"/>, <B key="b"/>, <C key="c"/>] Input (New Children): [<A key="a"/>, <C key="c"/>, <B key="b"/>] Expected: React detects move of <B> (via keys), reuses all fibers, updates positions without full re-render.[9][1]

Input (Old): [<A/>, <B/>, <C/>] (no keys) Input (New): [<A/>, <C/>, <B/>] Expected: React treats as replacement (positional match fails), unmounts <B>, remounts new <B>—losing state.[7][1]

Edge Case (Longer New List): Remaining new children trigger insertions after matching prefix.[1]

Constraints/Performance Notes

• Time: O(n) average for sibling lists via single-pass traversal; no true two-ended optimization due to fiber linked lists (not arrays).[3][1]
• Keys must be stable/unique; indices break on reorders.[9]
• Deep trees or missing keys degrade to unnecessary DOM ops.[2][9]