Traverse All Reachable Pages With Parallel BFS
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
A collection of web pages is modeled as a directed graph. `graph[page]` lists the pages linked from `page` in a stable order. Implement `reachable_pages(graph, start)` and return every page reachable from `start`, including `start`, in breadth-first discovery order. Visit neighbors in their listed order.
## Constraints
- Up to 200,000 pages and 1,000,000 links
- Page identifiers are strings.
- The graph may contain cycles, duplicate links, and links to pages with no entry in `graph`.
- Each page must appear at most once in the result.
## Examples
```text
graph = {
A: [B, C],
B: [D],
C: [D, E],
D: [A]
}
start = A
```
Return `[A, B, C, D, E]`.
## Clarifications
A missing adjacency list means the page has no outgoing links. Marking a page as discovered must happen before it is queued so duplicate links do not schedule duplicate work.
## Hint
Separate the frontier for the current depth from the next frontier. This makes both BFS ordering and a later parallel implementation easier to reason about.
## Interview Follow-ups
- Explain why recursive DFS can fail on a deep page graph.
- Process each BFS frontier with multiple workers while keeping discovery thread-safe.
- Discuss deterministic ordering, backpressure, fetch failures, and per-host rate limits in a real crawler.
Quick Answer: Return every web page reachable from a starting page in stable breadth-first discovery order, including the start exactly once. Handle cycles, duplicate links, missing adjacency lists, very large graphs, parallel processing, deterministic ordering, fetch failures, backpressure, and per-host rate limits.
A collection of web pages is modeled as a directed graph. graph[page] lists, in a stable order, the pages linked from page. Implement reachable_pages(graph, start). Return every page reachable from start, including start, exactly once in breadth-first discovery order, and visit each page's neighbors in their listed order. The graph may contain cycles and duplicate links. A page with no entry in graph has no outgoing links. Treat a page as discovered before scheduling it so duplicate or converging links cannot schedule repeated work.
Constraints
- The graph contains at most 200,000 pages and 1,000,000 directed links.
- Every page identifier is a string.
- Each adjacency list has a stable order that must be respected.
- Cycles, duplicate links, empty adjacency lists, links to pages with no graph entry, and a start page with no graph entry are valid.
- Return each reachable page at most once, and always include start.
Examples
Input: ({}, 'solo')
Expected Output: ['solo']
Explanation: With no adjacency entry for the start page, the start is still reachable from itself and is the only result.
Input: ({'A': ['A', 'A']}, 'A')
Expected Output: ['A']
Explanation: A duplicated self-loop must not enqueue or return A again after A is initially discovered.
Hints
- Decide exactly when a page becomes discovered so a duplicate link cannot make it eligible for a later second visit.
- Apply the two ordering rules consistently: smaller link distance first, then listed-neighbor order for discoveries at the same depth.