PPractick

The problem

A maze-solving robot explores corridors by going as deep as possible down one path before backing up to try the next branch. That's depth-first search. Starting at vertex 0, visit a vertex, then recursively visit its first unvisited neighbour, going all the way down, then its next unvisited neighbour, and so on. The recursion (or an explicit stack) remembers where to back up to, and a visited array stops the robot from going round in circles.

Example: adjacency [[2,3,1], [0], [0,4], [0], [2]] → [0, 2, 4, 3, 1].

Function signature

vector<int> dfsOfGraph(const vector<vector<int>>& adj);  // start at vertex 0

Test cases

Input (adjacency list)	Output	Explanation
[[2,3,1], [0], [0,4], [0], [2]]	[0, 2, 4, 3, 1]	4 is reached through 2 before 3 is tried
[[1,2], [0,2], [0,1,3,4], [2], [2]]	[0, 1, 2, 3, 4]
[[1], [0]]	[0, 1]
[[1,2], [0], [0]]	[0, 1, 2]	Back up to 0, then 2
[[]]	[0]

(Confirm: neighbours are tried in list order; only vertices reachable from 0 appear.)

How interviewers phrase it

• "Given a graph as an adjacency list, return its DFS traversal starting from vertex 0" (GeeksforGeeks "DFS of Graph").

Clarifying questions to ask

1. Recursive or iterative? (Recursive is natural; iterative avoids stack overflow on deep graphs.)
2. Does the neighbour order matter? (Yes: take them in list order.)
3. How many vertices? (Up to about 10⁴, so the recursion depth could be large.)

Follow-ups to expect

1. "How do you make it iterative with the same order?"
2. "Why is a visited array essential?"
3. "What is DFS used for?"
4. "DFS vs BFS for shortest paths?"
5. "Complexity?"

Related questions

• Maximum Depth in BT Medium
• Check for balanced binary tree Medium
• Check if two trees are identical or not Medium
• Symmetric Binary Tree Medium
• Connected Components Medium
• Traversal Techniques Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in