Repair the Spread Traversal

Start from brute force

Skip the adjacency map and simulate the rounds directly: each round, snapshot the infected set, scan every pair, and infect an endpoint whenever the other endpoint was in the snapshot. Checking both endpoints handles the undirected relation, and the snapshot keeps each round to exactly one hop, so the answer is correct. It costs O(R · E) time for R rounds and E pairs, and O(V) space. Every round rescans every pair, including pairs whose ends were infected long ago, and rounds beyond the graph’s diameter change nothing. Drop the snapshot and update in place, and the chain a-b, b-c, c-d is fully infected after one round.

The approach

Breadth-first search, one level per round. The reference infected builds adj with adj.setdefault(a, set()).add(b) and the mirror line, so every contact is visible from both ends, which repairs the first defect. It starts with seen = {start} and frontier = {start}, then each round builds a fresh set nxt: for every node in the frontier and every neighbor nb not yet in seen, it adds nb to seen and to nxt on the spot. Marking at first reach, and collecting into a set, are the other two repairs: a node that two frontier nodes both reach enters the next frontier once.

The invariant after round r: seen holds exactly the nodes within r hops of start, and frontier holds the ones at exactly r hops. Each node therefore joins one frontier, in the round of its shortest distance, and its contacts are scanned once. sorted(seen) is the answer. The TypeScript version mirrors it with a Record of Sets.

Walk through an example

On the first example, the chain a-b, b-c, c-d with two rounds, the two-way map lets b see a, and seen skips it.

Complexity

Time O(V log V + E + R) for V nodes, E pairs and R rounds: building adj is O(E), each node joins one frontier and has its contacts scanned once, the loop itself runs R times, and the final sort is O(V log V). Space O(V + E) for the map and the sets. The pair-scan simulation is O(R · E) time and O(V) space.

Edge cases to test

• pairs = [("b","a"), ("c","b")], start = "a", 1 round → ["a", "b"]. The inherited one-way map gives ["a"]; this is the only hidden test the inherited code fails.
• The chain with rounds = 0 → ["a"]. The start is infected before any round runs.
• pairs = [("a","b"), ("x","y")], 5 rounds → ["a", "b"]. Nodes named in pairs but unreachable from the start stay out.
• pairs = [("x","y")], start = "a", 3 rounds → ["a"]. A start with no contacts works because adj.get(node, ()) returns an empty tuple instead of raising.
• A ladder of 10 layers, each with two nodes joined to both nodes of the next: the answer is all 21 nodes either way, but with duplicates allowed the frontier doubles every round, to 1,024 entries by round 10, while the repaired frontier never holds more than 2.
• The chain with rounds = 10**6 → ["a", "b", "c", "d"], yet the loop still runs a million empty rounds. Break as soon as the frontier is empty.

Common mistakes

• Building a one-directional adjacency map from pairs that describe a symmetric relationship.
• Marking a node seen when you process it rather than when you first reach it — the classic BFS duplicate bug.
• Mutating the frontier while iterating it, which quietly merges round N and round N+1.
• Forgetting that the start node is infected at round 0 even when rounds is 0.

Follow-ups an interviewer asks next

Return the round in which each node was infected.

Replace seen with a dict dist and store the round number at the moment a node is first reached. That is unweighted single-source shortest path: BFS reaches every node first along a shortest path, so the stored round is its hop distance from the start. Time and space stay O(V + E), and the infected list is the dict’s keys.

Several people start out infected.

Use multi-source BFS: seed seen and frontier with every start node, then run the same rounds. The result after r rounds is every node within r hops of any start, and the cost stays O(V + E), against O(S · (V + E)) for running one search per source and merging the results.

Each contact transmits only with some probability.

Then the spread is random and one run is one sample. Simulate many runs, giving each newly infected node one weighted coin flip per uninfected neighbor (the independent cascade model), and report how often each node ends up infected. If edges carry transmission delays instead, earliest infection time is a shortest-path problem and Dijkstra replaces BFS.

The contact graph does not fit on one machine.

Partition the nodes across workers and run level-synchronous BFS: each round, every worker expands the frontier nodes it owns and sends newly reached neighbors to the workers that own them, then all workers wait at a barrier before the next round. One round is one superstep, the model that graph systems such as Pregel use.

Where this shows up

Level-order spread over a contact graph is the same computation as blast-radius analysis for a change, permission propagation through a group hierarchy, and dependency impact in a build system — all things an FDE gets asked for on a customer’s real data. Debugging rounds favor it because the bugs are invisible in small examples and obvious in the right one, which is exactly the skill being tested.

Check yourself

Reference solution

CHAIN = [("a", "b"), ("b", "c"), ("c", "d")]        # provided fixtures
DIAMOND = [("a", "b"), ("a", "c"), ("b", "d"), ("c", "d")]
REVERSED = [("b", "a"), ("c", "b")]
ISLAND = [("a", "b"), ("x", "y")]


def infected(pairs, start, rounds):
    adj = {}
    for a, b in pairs:
        adj.setdefault(a, set()).add(b)
        adj.setdefault(b, set()).add(a)      # undirected: both directions
    seen = {start}
    frontier = {start}
    for _ in range(rounds):
        nxt = set()
        for node in frontier:
            for nb in adj.get(node, ()):
                if nb not in seen:
                    seen.add(nb)             # mark when first reached
                    nxt.add(nb)
        frontier = nxt
    return sorted(seen)


print(infected(CHAIN, "a", 2))     # -> ['a', 'b', 'c']
print(infected(DIAMOND, "a", 1))   # -> ['a', 'b', 'c']

const CHAIN: [string, string][] = [["a", "b"], ["b", "c"], ["c", "d"]];          // provided fixtures
const DIAMOND: [string, string][] = [["a", "b"], ["a", "c"], ["b", "d"], ["c", "d"]];
const REVERSED: [string, string][] = [["b", "a"], ["c", "b"]];
const ISLAND: [string, string][] = [["a", "b"], ["x", "y"]];

function infected(pairs: [string, string][], start: string, rounds: number): string[] {
  const adj: Record<string, Set<string>> = {};
  for (const [a, b] of pairs) {
    (adj[a] = adj[a] || new Set()).add(b);
    (adj[b] = adj[b] || new Set()).add(a);          // undirected: both directions
  }
  const seen = new Set<string>([start]);
  let frontier = new Set<string>([start]);
  for (let r = 0; r < rounds; r++) {
    const nxt = new Set<string>();
    frontier.forEach(function (node) {
      (adj[node] || new Set<string>()).forEach(function (nb) {
        if (!seen.has(nb)) { seen.add(nb); nxt.add(nb); }   // mark when first reached
      });
    });
    frontier = nxt;
  }
  return Array.from(seen).sort();
}

console.log(infected(CHAIN, "a", 2));     // -> ["a","b","c"]
console.log(infected(DIAMOND, "a", 1));   // -> ["a","b","c"]