CODING CHALLENGE · N°70

Repair the Spread Traversal

Medium FDEInterviewGraphs

Inherited code computes how far something spreads through a contact graph, and the answers are wrong in a way that is invisible on small inputs. Three planted defects: a one-way adjacency map, a frontier with no dedupe, and a seen-set updated one step too late. Hidden tests.

The problem

You are given pairs, a list of two-element contact pairs describing an undirected graph, a start node, and a number of rounds. In each round, every currently infected node infects all of its direct contacts. Implement infected(pairs, start, rounds) returning the sorted list of infected node names after that many rounds. The start node counts as infected from round 0. The starting code is what you inherited — it is wrong in three places.

EXAMPLE 1

Input chain a-b-c-d, start a, rounds 2

Output ["a","b","c"]

two hops, not three

EXAMPLE 2

Input rounds 0

Output ["a"]

the start is already infected

EXAMPLE 3

Input pairs listed as (b,a)

Output a still reaches b

the relation is symmetric

CONSTRAINTS

The graph is undirected: a pair (x, y) means x contacts y and y contacts x.
A node is infected in the earliest round it can be reached; it never enters a later frontier.
Nodes that appear only in pairs and are unreachable from start must not appear in the result.
Return the result sorted, so the comparison is order-independent.

SOLVE IT YOURSELF

Your turn — write it

Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.

YOUR TASK

Read the inherited infected(...), find the three defects against the spec, and fix them one at a time.

HINTS — 4 IDEAS

Bug 1: the adjacency map is built in one direction only. The relation is symmetric.
Bug 2: the frontier is a list with no membership check, so a node reachable two ways is processed twice.
Bug 3: nodes are added to seen after the neighbour loop rather than when first reached, so they can enter the next frontier again.
Test with a diamond (a-b, a-c, b-d, c-d) — the duplicate bugs are invisible on a straight chain.

CPython · WebAssembly

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"]];

// --- INHERITED CODE. Three defects. Do not rewrite it; find them. ---
function infected(pairs: [string, string][], start: string, rounds: number): string[] {
  const adj: Record<string, string[]> = {};
  for (const [a, b] of pairs) {
    (adj[a] = adj[a] || []).push(b);
  }
  const seen = new Set<string>();
  let frontier: string[] = [start];
  seen.add(start);
  for (let r = 0; r < rounds; r++) {
    const nxt: string[] = [];
    for (const node of frontier) {
      for (const nb of adj[node] || []) {
        if (!seen.has(nb)) nxt.push(nb);
      }
      seen.add(node);
    }
    for (const n of nxt) seen.add(n);
    frontier = nxt;
  }
  return Array.from(seen).sort();
}

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

Approach, complexity & discussion — open after you solve

The approach

Three classic graph defects live in this one function. The contact list is undirected but the inherited adjacency map is built one way only, so half the contacts are invisible. The frontier is a list with no membership check, so nodes are re-processed and rounds bleed into each other. And the seen-set is updated after the inner loop instead of when a node is first reached, which lets the same node enter the next frontier twice.

The correct shape is level-order traversal: keep seen and a frontier, and for each round build the next frontier from unseen neighbours only, marking them seen as you add them.

Complexity

Time O(V + E) — each node and edge is examined a bounded number of times. Space O(V).

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.

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 favour it because the bugs are invisible in small examples and obvious in the right one, which is exactly the skill being tested.

Explore the topic

See this challenge alongside everything else on the same subject — handbooks, system designs, algorithms and tools, in one place.

Algorithms & DSA Interview Prep Forward Deployed Engineering