← Waymo Interview InsightsSoftware Engineer

Waymo·Software Engineer·Onsite - Coding / Algorithms·Senior

SeniorPrefer not to say
Jun 2026

Summary

Waymo SWE interview, coding round. One meaty in-place matrix copy problem that seemed straightforward until the overlap case came up and I realized I hadn't thought it through.

Questions Asked (1)

Q1

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 been read, and what do you do about out-of-bounds destinations?

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

My first instinct was just nested loops top-to-bottom, left-to-right and I coded it up pretty confidently.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First clarify the problem constraints and assumptions, especially about out-of-bounds behavior. Then explain the core algorithm: determine the correct iteration order based on the relative positions of the source and destination rectangles to avoid overwriting unread source data. Finally, discuss how to handle out-of-bounds destinations, such as clipping or error handling, and analyze time and space complexity.

Pro tip: Mention that you would test with overlapping rectangles in all four relative positions (source above-left, above-right, below-left, below-right) to ensure the iteration order logic is correct. Also, proactively ask whether the matrix should be extended or the copy should be clipped for out-of-bounds destinations, showing attention to requirements.

1. Clarify requirements and constraints

Ask about out-of-bounds destination behavior: should it be clipped, error, or extend the matrix? Confirm that rectangles are defined by top-left corner, height, and width, and that the matrix is mutable and stored in row-major order.

2. Determine iteration order

Compare the relative positions of source and destination. If destination starts above or to the left of source, iterate forward (top-left to bottom-right); if destination starts below or to the right, iterate backward (bottom-right to top-left). This prevents overwriting source cells before they are read.

3. Handle out-of-bounds destinations

If the destination rectangle extends beyond matrix boundaries, either clip the copy to the valid region or raise an error, depending on requirements. Adjust the iteration range accordingly to avoid invalid indices.

4. Implement the copy

Loop over the source rectangle in the chosen order, copying each element to the corresponding destination cell. Use O(1) extra memory by only using loop variables and temporary values.

5. Analyze complexity and edge cases

State that time complexity is O(m*n) where m and n are the dimensions of the source rectangle, and space is O(1). Discuss edge cases: non-overlapping rectangles, identical source and destination, and partial out-of-bounds.

Key Points to Mention

  • Iteration order depends on relative positions: forward if destination is above/left of source, backward if below/right.
  • Overlap handling: copying in the wrong order corrupts source data.
  • Out-of-bounds: clip, error, or extend based on requirements; adjust loops accordingly.
  • O(1) extra memory: only use loop variables and temporary storage.
  • Time complexity: O(m*n) where m and n are source rectangle dimensions.
  • Edge cases: non-overlapping, identical rectangles, partial out-of-bounds.

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