Prompt and context
You receive n users and q timestamped operations. add id u v adds an undirected relationship with an ID, remove id removes it, and ask u v asks whether two users are connected at that time. Each relationship is added and removed at most once, and all operations are known before answers are produced.
Return a Boolean answer for every ask. Explain why ordinary disjoint-set union cannot safely process deletion, how to map relationship lifetimes onto a timeline, how to restore state, and which boundaries and complexity matter. The target is offline dynamic connectivity, not arbitrary online updates.
What the interviewer is testing
- Whether you recognize that the monotonic union-find invariant breaks when edges disappear.
- Whether you can represent each edge as a half-open lifetime interval
[add time, remove time). - Whether you can decompose an interval into
O(log q)segment-tree nodes. - Whether you can implement rollback DSU without path compression and with union by size.
- Whether you can connect snapshots, recursion returns, and query correctness.
Questions to clarify first
- Are all operations known in advance? If answers must be online, the timeline approach does not apply.
- Does every relationship have a unique ID? Without one, deletion of duplicate edges is ambiguous.
- Is the graph undirected? A directed graph needs a different reachability structure.
- Can an ID be added again after removal? If so, each lifetime needs its own interval.
- Are queries only connectivity, or also component size, shortest paths, or actual paths?
30-second answer framework
Ordinary DSU can merge components but cannot delete an edge without knowing which structure must be split. I would scan the operations, create [add, remove) for each edge, and extend an edge with no removal to q. I would place each interval in a segment tree over time. During DFS, apply a node's edges, answer queries at leaves, and rollback to the entry snapshot when leaving the node. The rollback DSU avoids path compression and uses union by size, so each change is recorded and the overall cost is O(q log q log n) with O(n + q log q) space.
Step-by-step deep dive
Step 1: Identify why ordinary DSU fails
Ordinary DSU stores the result of all merges seen so far. Removing one edge may leave a component connected through another edge or may require splitting a tree; parent pointers alone do not reveal the affected cut. There is no safe “reverse union.”
Step 2: Build edge lifetime intervals
Record each add time. When its remove appears, close [add, remove); the half-open form keeps the edge out of the removal timestamp. An edge still open at the end becomes [add, q).
Step 3: Cover intervals with a segment tree
Store an interval in segment-tree nodes that fully cover it. One interval occupies at most O(log q) nodes. Every edge stored at a node is valid for the node's entire time range, so it is merged once rather than at every leaf.
Step 4: Design rollback DSU
Keep parent and size. find follows parents without path compression. union attaches the smaller root to the larger root and pushes the changed child, root, and old size onto a history stack. Union by size bounds tree height by O(log n).
Step 5: DFS with snapshots and restoration
Save the history length on entry, apply the node's edges, and answer ask at a leaf. After both children finish, pop back to the saved length. Parent edges remain active for the next child, while child-only edges cannot leak across siblings.
Step 6: Implementation shape
The implementation has four phases: build half-open intervals, add each interval to a time segment tree, traverse with a rollback DSU, and answer leaves. The critical details are no path compression, recording the old component size, and restoring exactly to the snapshot.
Step 7: Prove the invariant and complexity
On entry to a segment-tree node, DSU contains exactly the edges active throughout that node's range plus edges applied by ancestors. Child edges exist only in the child subtree and are removed on return, so a leaf sees exactly the active-edge union. Each edge is stored in O(log q) nodes and each union costs O(log n) with union by size, giving O(q log q log n) time and O(n + q log q) storage.
Step 8: Compare alternatives and failure cases
If edges only arrive and connectivity is queried, ordinary DSU is simpler with near-constant amortized operations. True online deletions require a dynamic-connectivity structure; the timeline tree cannot know an unknown future removal. DSU also cannot answer shortest paths, which need BFS, Dijkstra, or another path structure.
High-quality sample answer
I would first confirm that every operation is known and every relationship has a stable ID. Ordinary DSU only merges, and deletion breaks its component invariant, so I would scan operations into half-open edge lifetimes and extend still-open edges to the end. I would place those intervals in a segment tree over time, merge node edges during DFS, answer connectivity at leaves, and rollback to the entry history length on return. The rollback DSU avoids path compression, uses union by size, and records parent and size changes, giving O(log n) tree height. Each edge appears in O(log q) nodes, so time is O(q log q log n) and space is O(n + q log q). For additions only I would use ordinary DSU; for online deletions or shortest paths I would choose a stronger dynamic structure.
Common mistakes
- Reversing a union for deletion → merges are not invertible → use lifetime intervals and rollback.
- Using path compression in rollback DSU → many parent writes are not logged → use union by size without compression.
- Treating the lifetime as closed
[add, remove]→ the edge remains active at removal → use[add, remove). - Re-merging every edge at every leaf → complexity loses the segment-tree benefit → merge at covering nodes.
- Restoring only a parent pointer → later union-by-size choices are corrupted → restore the old size too.
- Promising an offline method for online updates → future intervals are unknown → confirm the interaction model first.
Follow-up questions and responses
What if the same relationship ID is added again after removal?
Create a new open record for each add, and let remove close only the currently open lifetime. The same ID then produces multiple disjoint intervals instead of overwriting the old one.
Can the same design answer current component size?
Yes. Keep root size, return the root from find, and restore old sizes during rollback. Additional component aggregates also need old values on the history stack and reversible updates.
What if q is so large that recursion or memory becomes the bottleneck?
Check whether O(q log q) interval storage fits first. Then replace recursive DFS with an explicit stack, compact edge storage, or process time blocks. Do not enable path compression and silently break rollback correctness.
Why cannot the timeline method simply be changed to online deletion?
The method needs a removal timestamp to build each interval. Online input does not reveal that future timestamp, so preprocessing cannot place the edge in the tree. Use a structure designed for online dynamic connectivity and re-evaluate its latency and implementation cost.