How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Zoox.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Zoox during technical interviews.

Can a Car Meet a Truck? | Zoox Coding Question

Can a Car Meet a Truck?

Company: Zoox

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

Quick Answer: This question evaluates a candidate's ability to reason about grid-based movement and time-indexed reachability, testing competencies in algorithmic analysis, discrete geometry, and distance metrics.

A truck's position on a 2D grid is known at each second. You are given an array `positions` where `positions[i] = [x_i, y_i]` is the truck's location at time `i + 1`. Another car starts at `(0, 0)` at time `0`. Every second the car may move one unit up, down, left, or right, or stay in place. Return `true` if the car can occupy the same grid cell as the truck at the same time at any point, and `false` otherwise. **Example:** - `positions = [[1, 0], [2, 0], [2, 1]]` - Output: `true` — the car can reach `(1, 0)` at time `1`. **Key insight:** At time `t = i + 1`, the car can be at any cell whose Manhattan distance from the origin is at most `t` (it can always burn extra moves by staying in place, so every distance `<= t` is reachable). Thus the answer is `true` iff there exists an index `i` with `|x_i| + |y_i| <= i + 1`.

Constraints

1 <= positions.length <= 10^5 (the array may also be empty, in which case the answer is false)
positions[i].length == 2
-10^9 <= x_i, y_i <= 10^9
The car starts at (0, 0) at time 0 and may move 1 unit up/down/left/right or stay each second.

Examples

Input: ([[1, 0], [2, 0], [2, 1]],)

Expected Output: True

Explanation: At time 1 the car can reach (1, 0) since |1|+|0| = 1 <= 1, matching the truck's first position.

Input: ([[2, 0]],)

Expected Output: False

Explanation: At time 1 the truck is at (2, 0), but the car can be at most Manhattan distance 1 from the origin, so 2 > 1 — it cannot reach it.

Input: ([[1, 0]],)

Expected Output: True

Explanation: At time 1, |1|+|0| = 1 <= 1, so the car steps right to (1, 0) and meets the truck.

Input: ([],)

Expected Output: False

Explanation: There are no truck positions, so the car can never share a cell with it.

Input: ([[3, 0], [3, 0], [3, 0]],)

Expected Output: True

Explanation: At time 3 (index 2), |3|+|0| = 3 <= 3, so the car can be at (3, 0) by stepping right three times.

Input: ([[5, 5], [5, 5]],)

Expected Output: False

Explanation: The truck stays at Manhattan distance 10, but the car can reach distance at most 2 by time 2, so no meeting occurs.

Input: ([[-1, 0], [0, -2], [-2, -1]],)

Expected Output: True

Explanation: At time 1, |-1|+|0| = 1 <= 1, so the car can move to (-1, 0) and meet the truck immediately.

Input: ([[10, 10], [11, 0]],)

Expected Output: False

Explanation: Distance 20 at time 1 and distance 11 at time 2 both exceed the time elapsed, so the car can never catch up.

Hints

What is the largest Manhattan distance the car can be from the origin after t seconds, given it moves at most one unit per second?
Because the car can always stay in place to burn extra time, every cell with Manhattan distance <= t is reachable at time t — parity is not an obstacle.
The truck is at positions[i] at time t = i + 1. The car can meet it there iff |x_i| + |y_i| <= i + 1. Scan once and check this condition.
No BFS over the grid is needed; the reachable set at each second is exactly a Manhattan-distance ball, so a single linear pass with a closed-form check suffices.

Quick Overview

This question evaluates a candidate's ability to reason about grid-based movement and time-indexed reachability, testing competencies in algorithmic analysis, discrete geometry, and distance metrics.