Coding

graph question

Asked at

Deliveroo

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

Stuck? Show a way to structure it+

01Clarify whether edges are directed, weighted, static, and whether a path or traversal is required
02Choose adjacency lists for sparse graphs and state the visited invariant
03Use BFS for unweighted shortest paths and DFS for reachability or component exploration
04Switch to Dijkstra only for non-negative weighted shortest paths and name the negative-edge limitation
05Validate disconnected vertices, cycles, duplicate edges, self loops, and recursion depth

Reference answer

The stored prompt only says “graph question”, so begin by clarifying the vertices, edge direction, weights, and objective instead of inventing a particular problem. Model sparse input with an adjacency list and state the invariant: mark a vertex when it is scheduled so it is processed once. Use DFS to explore reachability, detect components, or build a traversal; use BFS when each edge has equal cost and the first visit gives an unweighted shortest distance. If weights are non-negative, explain Dijkstra with a min-heap and stale-entry checks; if negative edges are possible, Dijkstra is invalid and the algorithm must change. Discuss how you would reconstruct a path with parent pointers. Test isolated vertices, disconnected components, parallel edges, self loops, cycles, and a graph too deep for recursive DFS. BFS and DFS take O(V + E); heap-based Dijkstra takes O((V + E) log V).

Then expect these follow-ups

What constraint would change your chosen approach?
Tests: constraint adaptation
How would you test the edge cases before implementation?
Tests: implementation extension

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question