Sequence Reconstruction

Sequence Reconstruction

What is this problem about?

The Sequence Reconstruction interview question gives you a target sequence nums and a list of subsequences. Determine whether nums is the UNIQUE shortest supersequence that can be reconstructed from the given subsequences. In other words, verify that: (1) nums can be built from the subsequences' ordering constraints, and (2) no other valid sequence satisfies all constraints. This is a topological sort uniqueness problem.

Why is this asked in interviews?

Amazon and Google ask this problem because it tests topological sort with a uniqueness condition — a subtle but important distinction from standard topological ordering. Unique topological ordering exists when the processing queue always has exactly one candidate at each step. This models dependency graphs in build systems, task schedulers, and course prerequisite validation where the unique execution order must be determined.

Algorithmic pattern used

The pattern is topological sort (BFS/Kahn's algorithm) with uniqueness check. Build a directed graph from the subsequences: for consecutive pairs (seqs[k][i], seqs[k][i+1]), add an edge. Compute in-degrees. Run BFS (Kahn's): at each step, check that the queue has exactly one node — if more than one, the topological order is NOT unique. Process nodes in the order they're dequeued and compare to nums. The sequence matches and is unique only if the BFS produces exactly nums with the queue always having one element.

Example explanation

nums = [1, 2, 3]. seqs = [[1, 2], [1, 3], [2, 3]].

Edges: 1→2, 1→3, 2→3. In-degrees: 1:0, 2:1, 3:2.

BFS:

• Queue: [1] (size 1 ✓). Process 1. Reduce in-degree of 2,3.
• Queue: [2] (size 1 ✓). Process 2. Reduce in-degree of 3.
• Queue: [3] (size 1 ✓). Process 3.

Order: [1,2,3] == nums. Queue size always 1 → unique → return true.

If seqs = [[1,2],[1,3]]: 2 and 3 both have in-degree 0 after processing 1 → queue size 2 → NOT unique → return false.

Common mistakes candidates make

• Checking only that nums is a valid topological order without verifying uniqueness (queue-size-1 condition).
• Not adding all nodes from nums to the graph — nodes not appearing in any sequence but in nums must still be present.
• Processing duplicates in edges — deduplicate edge insertions to avoid incorrect in-degree counts.
• Not handling the case where the graph has more or fewer nodes than nums.

Interview preparation tip

For the Sequence Reconstruction coding problem, the topological sort graph interview pattern with uniqueness verification is the key skill. The single rule: Kahn's BFS with a queue that always has exactly one node guarantees uniqueness. Amazon and Google interviewers test this exact condition — practice articulating why a queue size > 1 means ambiguity. Relate this to course scheduling (if two courses are both prerequisites of a third and neither is a prerequisite of the other, there are two valid orderings). Master topological sort uniqueness — it's reused in build system dependency resolution.