Coding

Graph Based Problem

Asked at

Uber

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 Based Problem”, 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

Hiring now

Get the Uber interview, not just the prep

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Or practice this question first

Next question