Explain Depth-First Search (DFS). What data structure does it use?

0-2 years experience

1. 1We have a simple undirected graph represented as an adjacency list. How would you implement a function to list all nodes reachable from node A using DFS, and which data structure would you use to manage the traversal?
2. 2If you run DFS on a tree but mistakenly use a queue instead of a stack, what order will the nodes be visited and why does that differ from DFS?

2-5 years experience

1. 1Our feature needs to find all connected components in a social‑network graph that can have up to a million nodes. Walk me through how you'd apply DFS here and any concerns about recursion depth or memory usage.
2. 2We recently added one‑way edges and our DFS‑based cycle detection started missing cycles. How would you debug this problem and what adjustments might you make to the algorithm or its data structures?

5-8 years experience

1. 1We're building a microservice that processes user‑recommendation graphs in real time. The graph can be very deep and may not fit entirely in memory. How would you design a DFS traversal that scales, and what trade‑offs would you consider between recursive and iterative approaches?
2. 2Our system currently uses a recursive DFS for path finding, but under heavy load we see stack overflow errors. Propose a redesign, including any auxiliary data structures, to make the traversal safe and performant.

8+ years experience

1. 1Our company is migrating a legacy monolith that uses recursive DFS for dependency analysis to a distributed platform. What architectural changes would you recommend to handle graph traversal across nodes while preserving correctness and minimizing data movement?
2. 2Imagine you need to expose a graph‑exploration API that lets clients request depth‑first walks with custom filters. How would you design the service layer, caching strategy, and contract to ensure low latency and avoid exposing internal stack or recursion details?