Apple·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Apr 2026Remote

Summary

Apple coding screen, one graph traversal question and that was basically it. Pretty straightforward if you're comfortable with DFS but the iterative vs recursive choice felt like it mattered more than I expected.

Questions Asked (1)

Given an unweighted graph represented as an adjacency list or edge list, find any valid path between two given nodes using depth-first search. If no path exists, report that. You can implement it iteratively or recursively.

Algorithms & Data Structures

Author's notes

I went recursive first because it felt cleaner to write under pressure, but then they asked me to redo it iteratively and I fumbled a bit managing the visited set with the explicit stack.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the graph representation and whether the graph is directed or undirected, then choose DFS (iterative or recursive) to explore from the start node while tracking visited nodes and parent pointers. Reconstruct the path from parent pointers if the target is found; otherwise report no path.

Pro tip: Mention that DFS does not guarantee the shortest path, and if the interviewer wants the shortest path, BFS is more appropriate. Also, discuss handling large graphs to avoid recursion depth issues by using an iterative approach.

1. Clarify the problem

Ask about graph type (directed/undirected), input format (adjacency list/edge list), and whether any path is acceptable or if shortest path is needed. Confirm that nodes are labeled and the graph may be disconnected.

2. Choose DFS implementation

Decide between recursive and iterative DFS based on graph size and recursion depth concerns. For iterative, use an explicit stack; for recursive, use a helper function with visited set and parent map.

3. Traverse and track path

Perform DFS from the start node, marking nodes as visited and recording the parent of each visited node. Stop early if the target node is reached.

4. Reconstruct and return path

If target is found, backtrack from target to start using the parent map to build the path. If DFS completes without finding the target, report that no path exists.

5. Analyze complexity and edge cases

State time and space complexity (O(V+E) time, O(V) space) and discuss edge cases: start equals target, disconnected graph, cycles, and large graphs.

Key Points to Mention

Use a visited set to avoid infinite loops in cyclic graphs.
Maintain a parent map (or predecessor array) to reconstruct the path.
DFS can be implemented iteratively with a stack or recursively; mention trade-offs (recursion depth vs. code simplicity).
Time complexity is O(V+E) for adjacency list, space complexity O(V) for visited and parent structures.
DFS does not guarantee the shortest path; if shortest path is required, BFS is preferred.
Handle edge cases: start node equals target node, target unreachable, graph with cycles, and large graphs where recursion may overflow.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.