Waymo·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

May 2026

Summary

Waymo SWE interview with a tricky in-place matrix copy problem. The overlap handling is where things get interesting and where I definitely stumbled a bit before finding my footing.

Questions Asked (1)

Given a 2D matrix and two rectangular regions (each defined by a top-left corner, height, and width), copy the source rectangle into the destination rectangle in place using O(1) extra memory. The rectangles may overlap. How do you handle the iteration order to avoid corrupting source data before it's read, and what do you do about out-of-bounds destinations?

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

My first instinct was just to loop top-to-bottom, left-to-right and copy each cell.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First clarify the problem constraints and edge cases, then determine the safe iteration order based on the relative positions of the source and destination rectangles. Explain how to handle out-of-bounds destinations by either clipping or validating, and discuss the trade-offs of each approach.

Pro tip: Mention that you would confirm whether the destination can be partially outside the matrix and whether clipping is acceptable, as this often reflects real-world constraints and shows attention to detail.

1. Clarify constraints and assumptions

Ask about matrix dimensions, rectangle bounds, overlap possibilities, and whether the destination can extend beyond the matrix. Confirm if in-place modification is required and if O(1) extra memory is strict.

2. Determine safe iteration order

Compare the relative positions of source and destination. If destination starts above or to the left of source, iterate top-left to bottom-right; if below or to the right, iterate bottom-right to top-left. This prevents overwriting unread source data.

3. Handle out-of-bounds destinations

If the destination rectangle extends outside the matrix, either clip the copy to the valid region or reject the operation. Clipping requires adjusting the iteration bounds and possibly the source offsets.

4. Implement the copy with adjusted bounds

Iterate over the valid region of the destination, compute the corresponding source indices, and copy element by element. Ensure the iteration order respects the overlap condition.

5. Test with edge cases

Verify with cases like no overlap, partial overlap, destination out-of-bounds, and source equals destination. Discuss time complexity O(area) and space complexity O(1).

Key Points to Mention

Overlap handling: iterate in the direction that avoids overwriting source data before it's read.
Direction rules: if dest is above/left of source, go forward; if below/right, go backward.
Out-of-bounds: clip destination to matrix boundaries or validate and reject.
Clipping requires adjusting source indices and iteration bounds accordingly.
Time complexity O(area of copied region), space complexity O(1).
Edge cases: no overlap, full overlap, source equals destination, destination partially outside.

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