Graph Algorithms, Search, And Snapshotting

What's being tested

Candidates must demonstrate graph traversal and search patterns (multi-source BFS, DFS, backtracking) plus set-aggregation and ranking for recommendation-style outputs. For distributed problems, show asynchronous message-passing reasoning and simple snapshot/aggregation protocols to get correct counts under asynchrony.

Patterns & templates

• Use an adjacency list representation (dict of lists) for sparse graphs; adjacency matrix only for N ≲ 2000 due to O(N^2) memory.

• Multi-source BFS for shortest distances from several seeds; use collections.deque and visited sets; O(V+E) time.

• DFS + backtracking with constraint propagation for CSPs (crossword): pick most-constrained slot first, prune by prefix/index.

• Count-based top-K recommendations: aggregate friend-of-friend counts in a hashmap, then use heapq min-heap of size K; overall O(M + U log K).

• For asynchronous aggregation, implement tree-based or flooding-based protocols (parent-child aggregation) and deduplicate messages with unique IDs.

• Memoize subproblems when branching overlaps (e.g., pattern→candidate-words cache) using a dict to avoid repeated dictionary lookups.

• When ranking ties matter, define stable tie-breakers (timestamp, user-id) and document complexity and space tradeoffs.

Common pitfalls

Pitfall: Assuming unbounded recursion for DFS; for large graphs use iterative stacks or increase recursion limits and justify it.

Pitfall: Double-counting in friend-of-friend recommendations; always exclude direct friends and the seed user when aggregating.

Pitfall: For asynchronous counting, returning after first reply is tempting; require termination detection or acknowledgements to ensure correctness.

The practice cards below cover the canonical variants — solve all of them and time yourself.