Shortest-Path Interview Questions by Company (2026)

As of 2026-10-19, TrueInterview's bank holds 33 shortest-path questions reported at 14 big-tech companies, and 31 of them were last reported in the 12 months before that date. Most surface early in the loop: they were reported in phone screens 23 times, onsite 9 times and in OAs 3 times. Google's reported set is general graphs with no matrix tag, while Apple and Meta each tag matrix on 2 of their 4. Our view: these questions get harder by adding state, such as removals left or stops used, rather than by demanding a fancier algorithm. Train two skills: defining the search state, and choosing the algorithm from the edge weights.

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 companies report shortest-path questions, and what does each lean on?

Uber and Google lead with 7 questions each, ByteDance follows with 5, and Apple and Meta have 4 each. The tag profiles separate a company with no matrix tag from companies that mix graphs and grids. The table pairs each company's count and tags with its named titles and the drill we would start with. Tags describe the reported questions only, not what a company never asks.

Our take: Google is the one profile that should change your first week. Its tags carry no matrix count, only graphs and one strings tag, and its named titles include an explicit Dijkstra implementation, so a Google candidate should rehearse Dijkstra on an adjacency list before any grid drill. A zero matrix count is not proof that Google skips grids, though: one of its titles, Shortest Distance to Taxi in a Grid, names a grid outright.

For Meta, Snowflake, Amazon and Snapchat, the shared title is Shortest Path in a Binary Matrix with Obstacles, so plain grid BFS is the first drill for those loops. Apple and ByteDance both file the obstacle-removal grid, which makes BFS with extra state their second drill, and ByteDance adds a weighted grid that calls for Dijkstra. Uber is the mixed case: its tags spread across five topics and its OA example is not a graph problem, so split Uber preparation between graph BFS and window problems.

Which titles do candidates report, and which family does each belong to?

The graph titles fall into four families in our reading: grid BFS, implicit graphs, weighted search and constrained state. The most-linked title is Shortest Path in a Binary Matrix with Obstacles, with 4 write-ups from Meta and Snowflake candidates. Wiki Page Shortest-Click Path follows with 3, all from Snowflake. Microsoft, Databricks and Airbnb enter through single examples.

Shortest Path in a Binary Matrix with Obstacles. Going by the title, every move between open cells costs the same, which makes this plain breadth-first search: the first time the queue reaches the target, that distance is the answer. Mark a cell visited when you enqueue it, keep the bounds and obstacle check in one helper, and handle a blocked start or target before the loop. It is filed under four companies, the most of any title whose company count we report, so it is the one to make automatic.

Wiki Page Shortest-Click Path. Read as a graph problem, pages are nodes and links are edges, and you discover neighbours as you go instead of receiving an adjacency list. Breadth-first search from the start page still gives the fewest clicks. In our view the follow-up worth preparing is cost: fetching a page's links is the slow step, so be ready to discuss a depth cap or searching from both ends.

Shortest Bridge. If it matches the well-known problem of that name, you connect two islands by flipping the fewest water cells. The standard approach collects the first island with a flood fill, then starts one BFS from all of its cells at once. PracHub's Dijkstra guide describes the same move for weighted graphs: initialise every source to zero, which it calls "equivalent to adding a zero-cost super-source."

When in the loop do these questions show up?

Mostly in phone screens, as the opening counts show. Among the 23 phone-screen questions, graphs lead the tags with 15, then matrix and greedy with 3 each. For a phone screen, the target is a correct BFS written from a blank editor without hesitation, including the queue, the visited set and the boundary checks.

The phone-screen titles in the tables run from plain to stateful. Meta's Find Shortest Path in Matrix sits on the plain end, while Microsoft's at Most K Cells per Move and the Databricks time-and-cost grid sit on the stateful end. A phone screen can therefore still carry extra state, and you should not assume the screen is the easy version.

The two onsite titles named in this sample are Apple's obstacle-removal grid and Airbnb's maze score. Our take: spend onsite-depth time on the constrained titles, because those are where a correct plain BFS stops being enough. The only OA example is Uber's Shortest Subarray with At Least K Distinct, which is not a graph problem at all. If your next step is an Uber OA, rehearse a sliding window as well as a graph search.

Why does added state make these questions harder?

Each limit turns a BFS over cells into a search over (cell, constraint) pairs. Obstacle removal, stops used, cells per move and a second cost all work this way. The reported titles carry these limits: obstacle removal at ByteDance and Apple, K stops at Uber, Apple and Snowflake, and K cells per move at Microsoft. Say the state tuple and the visited rule out loud before you write the loop.

Obstacle removal. The state is (row, column, removals left), and two visits to the same cell with different budgets are different states. Key the visited set on the triple, or keep the best remaining budget per cell and re-enter a cell only with more removals left. The second form uses less memory and is the one worth explaining at senior level. Practise obstacle removal.

At most K cells per move. Going by the title, one move can travel several cells in a straight line, so each move still costs one and BFS still applies. Our approach: walk each direction step by step, stop at a wall or at a cell already reached with a smaller distance, and keep walking past a cell reached at the same distance. Stopping at the first visited cell is the bug to rule out in your head before you code. Practise K cells per move.

Time and cost. Princeton's Algorithms text states, "The weights are not necessarily distances." Going by the Databricks title, a move carries both a time and a cost, so ask first which one is primary and whether the other only breaks ties. A strict order fits Dijkstra keyed on a (time, cost) pair; a budget on one measure puts that measure into the state. Practise the time-and-cost grid.

K stops. CP-Algorithms' Bellman-Ford page says that after each phase the algorithm "correctly finds all shortest paths whose number of edges does not exceed" the phase count. Run one phase per allowed edge, which is the stop limit plus one, and copy the distance array at the start of each phase so a phase never chains two edges. A Dijkstra over (city, stops used) works too; pick the version you can prove correct fastest. Practise Cheapest Flights Within K Stops.

How should you choose between BFS, Dijkstra and Bellman-Ford?

Choose from the edge weights, not from habit. Equal weights mean BFS, zero-or-one weights mean a deque-based BFS, nonnegative weights mean Dijkstra, and negative weights rule Dijkstra out. PracHub's Dijkstra guide puts it as "Choose from the weight domain rather than reaching for a heap automatically." Name the weights and the algorithm in your first sentence of every answer.

Our take: a heap on a unit-weight grid is correct but signals that you did not look at the weights. Going by their titles, most graph problems named in this sample are equal-weight searches, with or without added state, which is why BFS with state deserves more of your hours than Dijkstra variants. The extra minute spent naming the weights is the cheapest judgement signal you can give an interviewer.

What do interviewers check when Dijkstra does come up?

Correctness details more than the heap. The one named title that asks for Dijkstra by name is Google's phone-screen implementation. PracHub's guide frames the topic bluntly: "Dijkstra interview questions are proof questions disguised as heap questions." Prepare the invariant, the stale-entry rule and the path checks, and the heap code takes care of itself.

• The invariant. CP-Algorithms states that once a vertex is marked, its current distance "is the shortest, and will no longer change." PracHub's guide adds that the greedy selection "is safe only when edge weights are nonnegative".
• Stale entries. PracHub's guide notes that Python's heapq has no decrease-key, so the clean implementation pushes a new pair after each improvement and skips stale pairs later.
• Mark on pop. PracHub's guide shows that marking a node visited when it is pushed freezes a non-optimal distance.
• Early exit. PracHub's guide says to stop only when the target is popped with its current distance, because discovery or push is too early. CP-Algorithms adds that unreachable vertices keep an infinite distance, so the loop can stop once the selected vertex is infinite.
• The path. CP-Algorithms restores the path by recording a predecessor on each successful relaxation. PracHub's guide says to verify the endpoints, that every edge exists and that the weights sum to the returned distance, and to ask whether any shortest path is acceptable.
• Cost. Princeton's Algorithms text gives the worst-case running time as proportional to E log V.
• Tests. PracHub's guide lists one vertex, an unreachable target, parallel edges, a zero-weight edge, a cycle, the stale-entry graph and a negative edge as the cases to run.

Our take: if Google is on your list, write lazy-deletion Dijkstra with parent pointers this week and run it against those cases. For the other companies, one clean implementation is enough, because their named titles spend the difficulty on state. PracHub's guide also advises holding bidirectional Dijkstra until the baseline is correct.

Which titles with shortest in the name are not graph problems?

Graphs tag 22 of the 33 questions, so a third of the set carries no graph tag, and several titles with shortest in the name never use a queue. Prepare these with their own technique so that graph practice time goes to graph problems.

• Shortest Subarray with At Least K Distinct (Uber OA). Going by the title, this is a sliding window over an array with a hash map of counts, shrinking from the left while the condition still holds. It is linked from 2 write-ups, none from senior-or-above candidates. Practise it.
• Stack Items into the Shortest Column (Min-Heap Load Balancing) (Pinterest phone screen). The title names the technique: a min-heap keyed on column height, popping the shortest column for each item. It is linked from 2 write-ups. Practise it.
• Shortest Word Distance. It is filed under 2 companies with no write-up links. Going by the title, one pass over the word list that tracks the last position of each target word is enough. Practise it.

What changes at senior and staff level?

The overall split is close to even, but the grid and constrained titles draw mostly senior links. Write-ups link these questions 20 times from candidates who reported a senior, staff-plus or manager level and 22 times from junior, new-grad or intern candidates. Levels are what candidates reported on their own write-ups, so the split also reflects who writes reports.

These are small counts per title, so read them as what candidates linked rather than as a trend. Our take: at senior level the algorithm is unlikely to change, and the scrutiny is likely to rise. Expect to state the search state before coding, justify BFS or Dijkstra from the weights, and adapt when a follow-up changes the constraints. TrueInterview's compare page quotes one candidate, on a different problem, who reported a scaling follow-up: "Sliding window at first, then he asked what happens across three app servers and made me redo it with a shared store."

Down-leveling note (our view): a shortest-path round rarely sets your level on its own. Where it contributes, the signal is in the reasoning around the search: why the visited rule is correct for your state, what happens to memory when the budget grows, and how you would answer many queries on the same grid. A silent, correct BFS reads as mid-level; the same BFS with those trade-offs stated reads as senior.

Worked example: three reported titles, one ladder

Take Snowflake's phone-screen title, Shortest Path in a Binary Matrix with Obstacles, last reported in 2026-08. Solve it as plain grid BFS, since every move costs the same. Then climb two more reported titles in the same session, adding state first and weights second, so one practice block covers the whole progression the reports show.

Next, take Apple's onsite title, Shortest Path in a Grid with Obstacle Removal. Keep the grid BFS and change only the state, to (row, column, removals left), so the same cell with a different budget is a new state. Finally, take Cheapest Flights Within K Stops, filed under Uber, Apple and Snowflake. It adds weights and an edge-count limit, which is where the phase-limited Bellman-Ford from the state section fits. Three titles, one ladder: equal weights, then added state, then weights plus a limit.

How we counted

Counts come from TrueInterview's question bank as of 2026-10-19 and cover the questions filed under the shortest-path topic, including a few whose titles use the word shortest but are not graph problems. TrueInterview says reports are "Written up right after the interview and checked against other reports of the same round." These are candidate-reported questions reconstructed for practice, not any company's official question list, so counts show what candidates wrote up rather than how often a company asks a problem. Tags, rounds and levels come from the reports; family labels and drill picks are our reading of the titles, and one question can be filed under several companies and rounds.

FAQ

Do I need to implement Dijkstra from scratch in an interview?

For Google, plan on it: its named title in this sample is an implementation question from a phone screen. For the other companies, the named titles lean on BFS with added state, so one clean version is enough. Write lazy-deletion Dijkstra with parent pointers once in your interview language, run it against the test cases listed above, and keep it ready for weighted grids such as ByteDance's minimum-time title. If you can explain why stale entries are safe to skip, you have covered most of what the Dijkstra follow-ups probe.

When does Bellman-Ford come up?

In two situations: negative edge weights, and a limit on the number of edges, such as K stops. CP-Algorithms' Bellman-Ford page says the algorithm can be modified to signal a negative-weight cycle or even deduce it. The same page notes that you can stop early when a full phase changes nothing. For a K-stops limit, copy the distance array at the start of each phase so that one phase never chains two edges, and say that rule out loud before you code it.

How recent are these reports?

Recent. The opening gives the share last reported within the past year, and the tables carry each example's last-reported month. TrueInterview says questions are "Dated when the report gives a month." Use the month to set your order: a title reported in a phone screen this summer is a better first drill than a classic with no recent report. Treat any list, including this one, as candidate-reported practice material that shows which shapes to expect, not as a promise that a specific question will appear.

Do senior candidates get harder shortest-path variants?

Not harder algorithms, in our reading of the bank. The senior section shows the grid and constrained titles drawing most of their links from senior-or-above candidates, but those titles still use BFS, Dijkstra and Bellman-Ford. What rises with level, in our view, is the scrutiny: whether you state the search state, justify the algorithm from the weights and adapt when a follow-up changes the constraints. Spend your extra senior preparation time on the constrained titles and on explaining why your visited rule is correct.

Your practice plan

A three-week plan for someone working full time, about an hour on most weekdays. The target is narrow: a short ladder from grid BFS to added state to Dijkstra to an edge-limited search.

1. Week one. Solve Find Shortest Path in Matrix and Shortest Path in a Binary Matrix with Obstacles from a blank editor, writing the queue, the visited set and the bounds check without notes.
2. Week one. Solve Shortest Bridge as a multi-source BFS, then Wiki Page Shortest-Click Path, and say how you would cut the number of page fetches.
3. Week two. Solve Shortest Path in a Grid with Obstacle Removal and Shortest Path in a Grid with at Most K Cells per Move. Before coding each, say the state tuple and the visited rule out loud.
4. Week two. Write Dijkstra's Algorithm Implementation with lazy deletion and parent pointers, and test it on an unreachable target, a zero-weight edge, a cycle and a stale heap entry. If Google is your target, move this step to week one.
5. Week three. Solve Minimum Time to Reach Bottom-Right in a Grid and Grid pathfinding with time & cost optimality, naming the edge weights and the algorithm in your first sentence.
6. Week three. Solve Cheapest Flights Within K Stops twice, once with phase-limited Bellman-Ford and once as a search over (city, stops used). If Uber is on your list, add Shortest Subarray with At Least K Distinct as a sliding-window drill.

Sources

• TrueInterview question bank — shortest-path at big-tech companies — counted 2026-10-19
• Dijkstra Interview Questions: Stale Heap Entries, Negative Edges, and Path Reconstruction | PracHub Knowledge Hub — checked 2026-10-19
• Shortest Paths — checked 2026-10-19
• Bellman-Ford - finding shortest paths with negative weights - Algorithms for Competitive Programming — checked 2026-10-19
• Dijkstra - finding shortest paths from given vertex - Algorithms for Competitive Programming — checked 2026-10-19
• Interview prep compared: your application, end to end · TrueInterview — checked 2026-10-19
• Real FAANG Interview Questions by Company · TrueInterview — checked 2026-10-19

Last reviewed: 2026-10-19.