Waymo·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Apr 2026

Summary

Waymo SWE interview with an array problem that sounds trivial until you actually think about the constraints. Single round, coding focused, left me second-guessing my linear scan logic the whole way through.

Questions Asked (1)

Given an integer array with only the values 0, 1, and 2, find the minimum absolute difference |i - j| across all index pairs where one index holds a 1 and the other holds a 2. Return -1 if no such pair exists. You must solve it in a single linear pass.

Algorithms & Data Structures

Author's notes

The single-pass constraint is what makes this non-trivial.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a single pass to track the most recent index of 1 and 2. At each step, if the current element is 1 or 2, update the minimum difference if the other value has been seen, then update the last seen index for the current value. This ensures O(n) time and O(1) space.

Pro tip: Clarify that the array can contain only 0, 1, and 2, and that we only care about pairs of 1 and 2. Mention that the single pass is possible because we only need the closest pair, which must be adjacent in the sequence of non-zero elements.

1. Understand the problem and constraints

Restate the problem: find minimum |i-j| where one index has 1 and the other has 2. Note the single linear pass requirement and that 0s are irrelevant.

2. Initialize tracking variables

Set last1 and last2 to -1 (or None) to track the most recent indices of 1 and 2. Initialize min_diff to a large value (e.g., infinity).

3. Iterate through the array

For each index i and value v: if v is 1, check if last2 is set, update min_diff with i - last2, then set last1 = i. If v is 2, check if last1 is set, update min_diff with i - last1, then set last2 = i. Ignore 0s.

4. Return the result

After the loop, if min_diff is still infinity, return -1; otherwise return min_diff.

Key Points to Mention

Single pass O(n) time complexity and O(1) space complexity.
Only need to track the most recent index of 1 and 2 because the closest pair must be adjacent in the sequence of non-zero elements.
Handling edge cases: no 1 or no 2, or only one of each, return -1.
The algorithm works because any pair with a smaller difference would have been detected when the later element was encountered.
0s can be ignored as they don't contribute to any valid pair.
Use of variables to track last seen indices and update min_diff conditionally.

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