Interview prompt
Explain representing a graph before traversing it to an engineer who understands the surrounding system but has not used this technique. Walk from its contract to a concrete operation, then discuss where it fails or becomes expensive.
A strong answer
A graph models entities as vertices and relationships as edges. Before choosing an algorithm, decide whether edges are directed, weighted, duplicated, or allowed to change. Those choices affect both the meaning of a path and the representation needed to answer queries efficiently.
An adjacency list stores each vertex with its outgoing neighbors, so scanning all neighbors costs in proportion to the degree. Breadth-first search uses a queue and discovers vertices in increasing edge distance for an unweighted graph. Depth-first search follows one branch until it must backtrack, which is useful for reachability and cycle reasoning.
A complete answer also calls out the assumptions that control correctness. An adjacency matrix uses quadratic space but makes edge existence checks constant time and can be effective for dense graphs. BFS does not find a minimum-cost path when edge weights differ; Dijkstra requires nonnegative weights, while negative edges need other methods. Marking a node visited at the right time prevents duplicate queue growth.
Close by describing one representative test or measurement. For a directed graph with an unreachable component, describe how you would count components and why one traversal from a single start node is insufficient.
Follow-up questions
Answer the follow-ups in the frontmatter. Use the linked article for the concept and the trace to make the explanation concrete.