← Zoox Interview Insights

Zoox·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

Zoox coding screen for a software engineer role. One algorithmic problem, clean constraints, but the key insight is easy to miss if you're not thinking about reachability geometrically.

Questions Asked (1)

Q1

An ice cream truck moves along a 2D integer grid, and its position at each time step is given to you. A second vehicle starts at the origin and can move one unit in any cardinal direction or stay put each step. Can the second vehicle ever occupy the same cell as the truck at the same time step?

Algorithms & Data Structures
Author's notes

My first instinct was BFS and I started down that path before catching myself.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a reachability check: at each time step, the second vehicle can reach any cell within Manhattan distance t from the origin. The truck is catchable if and only if at some time step t, the Manhattan distance from the origin to the truck's position is ≤ t and the parity of (t - distance) is even. Iterate through the truck's positions and check this condition.

Pro tip: Mention that the parity condition is crucial because the vehicle can only change its Manhattan distance from the origin by ±1 each step (or 0 if staying), so the parity of the distance must match the parity of the time step. This shows attention to detail and avoids a common off-by-one error.

1. Understand the movement constraints

Clarify that the second vehicle starts at (0,0) at time 0 and can move one unit in any cardinal direction or stay put each step. This means after t steps, it can reach any cell (x,y) such that |x| + |y| ≤ t and (t - (|x|+|y|)) is even.

2. Formalize the catch condition

For each time step t and truck position (xt, yt), the second vehicle can be at the same cell if and only if |xt| + |yt| ≤ t and (t - (|xt| + |yt|)) % 2 == 0.

3. Iterate through the truck's path

Loop through the given sequence of truck positions, checking the condition at each time step. If any step satisfies the condition, return true; otherwise, return false after checking all steps.

4. Optimize if needed

If the path is very long, note that the condition can be checked in O(1) per step, so the overall time complexity is O(n), which is optimal. No further optimization is necessary.

5. Consider edge cases

Handle cases where the truck starts at the origin (t=0) or where the truck's path never satisfies the condition. Also, ensure that the parity check is correctly implemented (e.g., using modulo 2).

Key Points to Mention

  • Manhattan distance as the metric for reachability in a grid with cardinal moves.
  • Parity condition: the difference between time and distance must be even because each move changes the Manhattan distance by exactly 1 (or 0 if staying).
  • Time complexity: O(n) where n is the number of time steps, as each step is checked in constant time.
  • Space complexity: O(1) extra space, as we only need to track the current step and position.
  • The ability to stay put allows the vehicle to 'waste' a step, which is why parity matters.
  • Edge case: at t=0, the truck must be at (0,0) for the second vehicle to catch it immediately.

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