Apple·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Apr 2026

Summary

Apple SWE interview that leaned pretty heavily on graph traversal. The main problem was a flood fill implementation, but they wanted three separate versions of it back to back, which I wasn't expecting.

Questions Asked (1)

Implement a flood fill algorithm on a 2D pixel grid using BFS with a queue, then recursive DFS, then iterative DFS with an explicit stack. For each version, explain the time and space complexity.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I got through BFS fine and the recursive DFS was pretty mechanical.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem: flood fill replaces a connected region of the same color starting from a given pixel. Implement BFS with a queue, recursive DFS, and iterative DFS with a stack, then compare their time and space complexities, noting trade-offs like recursion depth limits and queue/stack memory overhead.

Pro tip: Mention that recursive DFS can cause stack overflow on large grids, so iterative approaches are safer in production; also note that BFS and DFS have the same time complexity but different space usage patterns.

1. Clarify and define the problem

Confirm the grid dimensions, starting pixel, new color, and that flood fill changes all connected pixels of the same original color. Handle edge cases like starting pixel already having the new color.

2. Implement BFS with a queue

Use a queue to explore neighbors level by level, marking visited pixels by changing their color. Explain that each pixel is enqueued at most once, giving O(N) time and O(N) space in the worst case.

3. Implement recursive DFS

Recursively visit each neighbor, changing color as you go. Note that recursion depth can be O(N) in the worst case, leading to stack overflow for large grids; time is O(N), space is O(N) due to call stack.

4. Implement iterative DFS with an explicit stack

Use a stack to simulate recursion, pushing neighbors onto the stack. This avoids recursion depth limits but still uses O(N) space in the worst case; time remains O(N).

5. Compare complexities and trade-offs

Summarize that all three have O(N) time where N is the number of pixels. Space: BFS uses queue (O(N)), recursive DFS uses call stack (O(N) but risk of overflow), iterative DFS uses explicit stack (O(N) but safer). Discuss when to choose each.

Key Points to Mention

Time complexity is O(N) for all three approaches, where N is the number of pixels in the grid.
Space complexity is O(N) in the worst case for all, but BFS queue and iterative DFS stack can be more memory-heavy than recursion for shallow regions.
Recursive DFS risks stack overflow for large grids; iterative DFS with explicit stack avoids this.
BFS explores level by level and is optimal for finding shortest path in unweighted graphs, but flood fill doesn't require shortest path.
Marking visited pixels by changing color immediately prevents infinite loops and avoids a separate visited set.
Edge cases: starting pixel already new color, empty grid, single row/column, and large grids.

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