Graph Coding Interview Prep: A Staged Plan for Big Tech

As of 2026-11-02, TrueInterview's bank holds 256 graph practice questions reported at 25 big-tech companies, 231 of them last reported within the prior 12 months. Study them in five stages: grid BFS, topological sort with cycle detection, union-find, shortest paths over modelled state, then applied simulations. That order is our judgement built on candidate reports: topological sort is tagged on 20 of the 256 questions, and Course Schedule is filed under 9 companies. Several dependency-ordering, incremental and applied problems draw more senior than junior links, though the counts are small, so prepare for follow-ups beyond the base traversal.

Disclosure: TrueInterview is an interview-preparation product and publishes this article. Facts about other products come from their public pages on the dates listed under Sources.

Which graph patterns do candidates actually report?

A short list of patterns covers the most-linked questions, and it is not the list a textbook would give you. Beyond the graph tag itself, the most frequent topics on the 256 questions are matrix (38), trees (25), hashing (22) and backtracking (21). The most-linked titles are grid traversals, dependency orders, one union-find problem and two applied simulations.

Write-up links count what candidates wrote up, not how often a company asks, and these are candidate-reported questions reconstructed for practice rather than any company's official list. Lowest Common Ancestor is a tree problem that sits inside a graph-tagged set, so treat it as tree practice, not as a graph algorithm.

The Tech Interview Handbook's graph guide ranks algorithms by opinion. It lists breadth-first and depth-first search as common, and it files topological sort in its "Uncommon - Topological Sort, Dijkstra's algorithm" tier. The same guide puts Bellman-Ford, Floyd-Warshall, Prim's and Kruskal's in an almost-never tier and adds: "Your interviewer likely doesn't know them either."

Our take: the handbook calls topological sort uncommon, and only 20 of the 256 questions carry the tag, but two of the most-linked titles are dependency-ordering problems, so it earns an early slot. The bank tags topics rather than individual algorithms, so it cannot count Bellman-Ford or Kruskal's directly. What it does show is that none of the most-linked titles above needs them. That does not prove the classic algorithms are never asked. It means they should not take a slot from the five stages below when you have three weeks and a full-time job.

Stage one: why start with grid BFS?

Start with breadth-first search on a grid, because matrix is the most common topic after the graph tag itself and grid problems turn up in every round. Lyft's Rotten Oranges / Grid Infection BFS was reported in an OA as recently as 2026-10, and Snowflake's Shortest Path in a Binary Matrix with Obstacles in a phone screen the same month. Before stage two, you should be able to write the queue, the four-direction loop and the visited check without pausing.

The Tech Interview Handbook's graph guide says that in algorithm interviews "graphs are commonly given in the input as 2D matrices where cells are the nodes and each cell can traverse to its adjacent cells (up/down/left/right)." The guide advises checking on every move that the position is inside the matrix and not yet visited. Its BFS note also says to use a double-ended queue rather than a Python list, because dequeuing from a deque is O(1).

Drill these three, in this order:

• Rotten Oranges / Grid Infection BFS. Linked from 16 write-ups at Uber, Amazon and Lyft. It is a multi-source BFS: seed the queue with every rotten cell, process one level per minute, and finish by checking for fresh cells that were never reached.
• Number of Islands (Plain and Streaming). Filed under 7 big-tech companies, including Uber, Amazon, Google and Microsoft. The plain half is a flood fill that counts components. The streaming half, where land appears cell by cell, is the bridge to stage three.
• Shortest Path in a Binary Matrix with Obstacles. Filed under 4 big-tech companies and linked from 8 write-ups. The cp-algorithms BFS article explains that in an unweighted graph the path BFS finds to any node is the one with the fewest edges, in O(n + m) time. The same article describes storing each vertex's parent so the path itself can be restored.

Our take: write the template once with a deque, a direction array, a bounds check and a visited set, then reuse it without thinking. A candidate who spends ten minutes on bounds checks has no time left for the follow-up, and at senior level the follow-up is the part being scored.

Stage two: why does topological sort come second?

Because dependency ordering recurs across companies, and its two most-linked titles draw at least their share of senior links. Course Schedule was reported in an Apple phone screen as recently as 2026-10, and Alien Dictionary is filed under 5 big-tech companies, including Uber, Apple and ByteDance. Alien Dictionary draws more senior than junior links, 6 against 4, and Course Schedule's 13 senior-or-above links out of 33 sit slightly above the one-in-three baseline described in the senior section.

Two reported variants push past the plain version. Snapchat's Course Schedule Cycle Detection and ByteDance's Print Execution Order in a DAG and Detect Cycles were both reported in phone screens as recently as 2026-10. Both titles put cycle detection in the task itself, so treat a cycle as an expected outcome to report, not an error path.

The cp-algorithms topological sort article states the condition plainly: "It only exists, if the directed graph contains no cycles." Its DFS method orders vertices by descending exit time, and the list built as each vertex finishes is the reversed topological order. The Tech Interview Handbook's graph guide notes that topological sorting is most commonly used to schedule jobs that depend on other jobs, which is exactly how these prompts are framed.

Learn both methods and know what each gives you:

• In-degree queue (Kahn's algorithm). Push every node with in-degree zero, pop, decrement neighbours, and push any that reach zero. If you pop fewer nodes than exist, a cycle remains. Processing level by level also tells you which tasks can run in parallel.
• DFS with exit times. Colour nodes unvisited, in progress and done. Reaching an in-progress node means a cycle, and the recursion stack at that moment holds the cycle itself.

For Alien Dictionary, the edges come from the first differing character of each adjacent word pair. The edge case to name before the interviewer does is a longer word placed before its own prefix, which makes the input invalid.

Our take: default to Kahn's algorithm. It is iterative, cycle detection falls out of a count, and the level structure answers the parallel-execution follow-up. Switch to the DFS version if the prompt asks you to return the cycle itself, which the cycle-detection titles suggest you may be asked to do.

Stage three: when does union-find earn its own slot?

When the question asks about connectivity while edges arrive over time, union-find beats rerunning a search. The Earliest Moment When Everyone Become Friends is linked from 14 write-ups at Uber and Google. Number of Islands II is linked from 5 write-ups by senior-or-above candidates and 3 by junior, new-grad or intern candidates. Neither is solved well by a fresh BFS after every event.

The cp-algorithms article on Disjoint Set Union says of the structure: "Often it is also called Union Find because of its two main operations." Two elements share a set exactly when find returns the same representative for both. The cp-algorithms article warns that in the naive version each find call can take O(n) time, because trees degenerate into chains.

The fix is two optimisations used together. Union by size and union by rank attach the smaller tree under the larger one, and the cp-algorithms article says the two are equivalent in time and space. Combined with path compression, the article says, "we will reach nearly constant time queries".

How the two reported problems use it:

• The Earliest Moment When Everyone Become Friends. Sort the friendship events by time, union each pair, and keep a running count of components. The answer is the timestamp at which the count drops to one, or a sentinel if it never does.
• Number of Islands II. Add land cells one at a time, union each with its land neighbours, and record the island count after every addition. This is the streaming half of stage one's island problem.

Our take: pick union by size over union by rank. The complexity is the same, and the size array answers the common follow-up about the largest component without extra work. Write find iteratively so a long chain cannot hit the recursion limit, and be ready to say why deletions break the structure.

Stage four: how do you handle shortest paths over modelled state?

Treat the state, not the cell, as the vertex, and the BFS from stage one still works. The cp-algorithms BFS article lists finding the fewest-moves solution to a game as a BFS use, when each state is a vertex and each transition an edge. Databricks' Find Optimal Commute, linked from 13 write-ups, was reported in a phone screen as recently as 2026-09. The claims give only its title, link count and round, so placing it in this stage is our inference.

The same cp-algorithms article builds an auxiliary graph whose states are a vertex plus the current parity to find shortest even-length walks. That is the move these prompts reward: add exactly the extra dimension the rules need, such as keys held or obstacles removed, and nothing more. Amazon's Delivery-Center Grid — Minimum Inconvenience, reported in an OA as recently as 2026-10, is another grid prompt worth a timed attempt at this stage.

Staff-plus write-ups link Shortest Path in a Grid with at Most K Cells per Move and Nearest Supply Point in a Map, but each has a single such link. Use them as extra practice if you have time; one link is not a pattern.

Our take: learn one Dijkstra template with a heap as an extension of BFS for when edge weights appear, and stop there. For senior follow-ups, state the size of the state space as your complexity bound, since cells times the extra dimension is what the interviewer will ask you to justify.

Stage five: what do applied simulations add for senior loops?

They test whether you can model state cleanly and extend a working solution, which in our view is where senior evaluation moves. Infection Spread Simulation, the most-linked question in the set, was reported in an OpenAI phone screen as recently as 2026-09. Anthropic's Web Crawler was reported in a phone screen the same month. If either company is on your list, move this stage up to second place.

Dependency Version Check is linked from 5 write-ups by senior-or-above candidates, and 4 of its links come from machine-learning, AI, research or data-science candidates. The claims give only its link counts, so the description below is inferred from the title: a dependency graph combined with version checks, the same modelling skill the simulations test.

How to approach each:

• Infection Spread Simulation. Separate the step function from the loop. Advance one generation at a time from a frontier queue, or write the next state into a second buffer, so changes made during a step cannot leak into the same step. Stop when a step changes nothing.
• Web Crawler. A crawl is a BFS over URLs with a visited set and a filter on which hosts to follow. Get the single-threaded version correct first, then be ready to make fetches concurrent with a worker pool, guarding the visited set with a lock or a single owner thread.
• Dependency Version Check (likely shape, inferred from the title). Model each package as a node and each requirement as an edge carrying a version range, walk the graph from the root package, compare the installed version against every range on the way, and reuse stage two's three-colour cycle check for circular requirements.

Our take: for senior candidates and AI-lab loops, these problems deserve more of your time than any textbook algorithm beyond Dijkstra. The traversal inside them is stage-one material. What gets evaluated is whether your state model survives the second and third extension without a rewrite.

Where are these questions reported, by round and company?

Mostly in phone screens, so speed and correctness on the core patterns matter more than breadth. The questions were reported in phone-screen (176), onsite (105) and OA (21) rounds, and one question can be reported in more than one round. Collection is uneven, so this split does not prove onsites ask fewer of them; it does make the first technical call the place an unpractised traversal is most likely to cost you.

The secondary topics shift by round. Phone-screen questions lean on matrix (25), hashing (16) and backtracking (16). Onsite questions carry matrix (20), trees (18) and hashing (12). If your next round is an onsite, keep tree problems warm alongside the graph stages.

Below those six, the bank files 22 graph questions under Snowflake, 18 under Apple, and 10 each under OpenAI and LinkedIn.

Decision rule: if your loop is at OpenAI or Anthropic, put the applied simulations right after grid BFS. If it is at Uber or Google, add union-find before shortest paths. At Amazon, weight grid problems more heavily. At Google, Meta or Microsoft, keep tree problems in the rotation, and at ByteDance add backtracking. Except for AI-lab loops, cover topological sort with cycle detection before anything else beyond BFS and DFS.

Worked example, a senior engineer preparing for Uber. The bank files 40 graph questions under Uber, with trees and matrix tied as its top secondary topics. In the first week, drill Rotten Oranges / Grid Infection BFS, which is reported at Uber, and Number of Islands, which is filed under Uber. In the second week, do Course Schedule and Alien Dictionary, both filed under Uber, with explicit cycle detection. In the third week, solve The Earliest Moment When Everyone Become Friends, reported at Uber and Google, plus Number of Islands II. Add Lowest Common Ancestor of a Binary Tree, which was reported in an Uber phone screen as recently as 2026-09.

How has the mix shifted over the last four quarters?

Grid problems dipped and recovered while tree problems lost ground, measured as shares of write-up links. Matrix questions took 24% of links in 2025-Q4, 12% in 2026-Q1, 16% in 2026-Q2 and 19% in 2026-Q3. Tree questions fell from 22% to 13% across the same quarters.

Quarterly link totals grew from 59 to 194, but that mostly reflects how many write-ups were collected, so compare shares rather than totals. Treat the matrix swing as noise. The tree decline is steadier, yet tree problems still lead the secondary topics at Google, Meta and Microsoft, so do not drop them if one of those companies is on your list.

What changes at senior and staff level?

Several dependency-ordering, incremental and applied problems draw more senior than junior links, though the counts are small, and a grid problem leans senior too. Write-ups link these questions 207 times from candidates who reported a senior, staff-plus or manager level and 419 times from junior, new-grad or intern candidates. Against that roughly one-in-three baseline, any problem with more senior than junior links stands out.

Alien Dictionary and Web Crawler (in the first table), Number of Islands II (stage three) and Dependency Version Check (stage five) all clear that bar. Maze Problem does too: 5 senior-or-above links, one of them staff-plus or manager, against 2 junior ones. At the other end, Lowest Common Ancestor draws few senior links, and by topic, dynamic-programming and two-pointers had no senior-or-above links at all against 10 and 8 junior-or-below ones.

Staff-plus write-ups also link Robot Navigation in an Unknown Grid and Binary Tree Right Side View, each with a single link. Most of the staff examples are grid navigation, alongside that one tree problem; with one link each they are too few to generalise from.

Our take: at senior level, expect the base solution to be a checkpoint, not the finish. Rehearse these four follow-ups on every problem in the plan.

The cp-algorithms BFS article describes the disconnected case directly: start a search from each vertex not already visited, which finds every connected component in O(n + m).

Down-leveling note (our view): on a graph question, the level signal sits in the follow-up table above, not in the base solution. If you spend the session reaching a correct traversal and never get to disconnected input or a streaming extension, the round shows mid-level work even when the code passes. Outside coding, we expect system design depth and the project deep dive to weigh more on level.

Which mistakes cost the most on traversal questions?

Visited-state errors cost more than slow code, because a cell enqueued twice wastes work and can overwrite a correct distance, and a node revisited in a cycle never lets the loop finish. The Tech Interview Handbook's graph guide warns: "A tree-like diagram could very well be a graph that allows for cycles and a naive recursive solution would not work." The same guide says that failing to track visited nodes correctly can leave your code in an infinite loop.

The mistakes worth a checklist, in our view:

• Marking a cell visited when you dequeue it rather than when you enqueue it, which lets the same cell enter the queue several times.
• Dropping the bounds check on one of the four directions.
• Using a plain list as the BFS queue, which stage one covers.
• Returning a topological order without checking that every node was processed.
• Mutating the input grid to mark visits without saying so, and without asking whether that is allowed.

How we counted

Counts come from TrueInterview's question bank as of 2026-11-02 and cover graph-tagged coding questions filed under 25 big-tech companies. Every question in the set carries the graph tag by construction, so the graph share is always 100% and is not a finding. Level splits count write-up links by the level each candidate reported, not people, and none of the counts say how often a company asks a topic. Quarterly comparisons use shares of links, not totals.

FAQ

Do I need Dijkstra, Bellman-Ford or minimum spanning trees for interviews?

Learn Dijkstra as an extension of BFS, as stage four describes, and treat the others as optional. The Tech Interview Handbook's graph guide places Bellman-Ford, Floyd-Warshall, Prim's and Kruskal's in its almost-never tier, and none of the most-linked titles in our set needs them. With three weeks of evenings, the hours go further on topological sort, union-find and state modelling, where several of the most-linked titles sit.

How should I represent a graph in an interview?

Use whatever the input already gives you, and build a dictionary of neighbours only when it does not. The Tech Interview Handbook's graph guide calls a hash table of hash tables "the simplest approach during algorithm interviews", and the same guide says you will rarely need an adjacency matrix or list. For grids, the matrix is the graph: generate neighbours on the fly with a direction array instead of building edges.

Should I write DFS recursively or iteratively?

Write it recursively when the input is small and the recursion makes the logic clearer, such as the exit-time version of topological sort, which the cp-algorithms article builds on depth-first search. Switch to an explicit stack or to BFS when the grid or chain can be large, because recursion depth then equals the longest path. At senior level, mention the trade-off before the interviewer asks; it is one of the four follow-ups worth rehearsing.

Do machine-learning candidates get different graph questions?

Slightly. By share of write-up links, machine-learning, AI, research and data-science candidates link matrix questions 7% of the time against 18% for software engineers, while topological sort is close at 17% against 15%. Infection Spread Simulation draws 12 of its links from that group and 37 from software engineers. If you are interviewing for an ML or AI role, give dependency ordering and the applied simulations a little more time than extra grid drills.

How long does graph preparation take for an experienced engineer?

Plan on three weeks of evenings if you already know BFS and DFS. The first week rebuilds grid traversal until it is automatic, the second covers topological sort with both cycle-detection methods, and the third adds union-find, one state-space shortest path and the applied problems for your target company. If your loop is at OpenAI or Anthropic, move the simulations into the second week, right after grid BFS, and push topological sort and union-find back accordingly. If you have not written a traversal in years, add a warm-up week of plain BFS and DFS on adjacency lists rather than compressing the stages.

Your practice plan

A three-week plan for someone working full time. TrueInterview says its coding questions are judged "Server-side, on hidden tests", so submit each solution rather than eyeballing it.

1. First week, weekdays. Write a grid BFS template with a deque, a bounds check and a visited set, then solve Rotten Oranges / Grid Infection BFS against a phone-screen-length timer.
2. First week, weekend. Solve Number of Islands (Plain and Streaming) with an iterative flood fill, then Shortest Path in a Binary Matrix with Obstacles with a parent array that restores the path.
3. Second week, first half. Solve Course Schedule twice, once with in-degree counting and once with DFS exit times, and explain aloud how each detects a cycle. Then solve Course Schedule Cycle Detection, adding your own extension that returns the cycle itself.
4. Second week, second half. Solve Alien Dictionary with the invalid-prefix check, and Print Execution Order in a DAG and Detect Cycles, then extend it yourself to group tasks into parallel batches.
5. Third week, opening days. Implement union-find with path compression and union by size from memory, then solve The Earliest Moment When Everyone Become Friends and the streaming half of the island problem.
6. Third week, midweek. Attempt Find Optimal Commute as a state-space BFS (the claims give only its title, so that framing is our inference), then write a heap-based Dijkstra template for grids with weighted moves as your stage-four extension.
7. Third week, weekend. Pick by target: Infection Spread Simulation and Web Crawler for OpenAI or Anthropic (move these to the second week if either is your target), Dependency Version Check for a senior ML or AI role, and Lowest Common Ancestor of a Binary Tree for Google, Meta or Microsoft.
8. Every session. Close each problem by stating its complexity and answering one senior follow-up out loud: recursion depth, disconnected input, or an input that grows.

Sources

• TrueInterview question bank — graph at big-tech companies — counted 2026-11-02
• Graph cheatsheet for coding interviews | Tech Interview Handbook — checked 2026-11-02
• Breadth First Search - Algorithms for Competitive Programming — checked 2026-11-02
• Topological Sorting - Algorithms for Competitive Programming — checked 2026-11-02
• Disjoint Set Union - Algorithms for Competitive Programming — checked 2026-11-02
• Real FAANG Interview Questions by Company · TrueInterview — checked 2026-11-02

Last reviewed: 2026-11-02.