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 easy difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Waymo.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Waymo during technical interviews.

Determine earliest collision among moving cars

Company: Waymo

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

You are given **n cars** moving over time. Each car has known initial state at time \(t=0\): - 1D case (straight road): - initial position \(x_i\) (meters) - initial velocity \(v_i\) (m/s) - constant acceleration \(a_i\) (m/s²) - physical size represented as a radius \(r_i\) (meters). (Cars collide when their intervals overlap, i.e., when center distance \(\le r_i + r_j\).) - 2D case (flat plane): - initial position \((x_i, y_i)\) - initial velocity \((v_{xi}, v_{yi})\) - constant acceleration \((a_{xi}, a_{yi})\) - radius \(r_i\) A car’s position evolves as: - 1D: \(x_i(t) = x_i + v_i t + \tfrac{1}{2} a_i t^2\) - 2D: \(\mathbf{p}_i(t) = \mathbf{p}_i + \mathbf{v}_i t + \tfrac{1}{2} \mathbf{a}_i t^2\) ### Tasks 1. **1D:** Determine whether **any collision occurs** for \(t \ge 0\). If yes, return the **earliest collision time** and the pair of cars involved. 2. **2D:** Same as (1), but in 2D (cars collide when Euclidean distance between centers \(\le r_i + r_j\)). ### Requirements - Provide an algorithm and implementable approach. - Discuss time complexity and how you would **optimize** beyond the naive \(O(n^2)\) pairwise checking. - Handle edge cases such as: - collisions at \(t=0\) - cars with identical trajectories (overlapping for an interval) - numerical precision when solving for collision times You may assume \(n\) can be large (e.g., up to \(10^5\)), so a brute-force all-pairs solution may be too slow.

Quick Answer: This question evaluates proficiency in kinematics, computational geometry, numerical root-finding, and scalable algorithm design for collision detection among moving objects, including attention to numerical precision and overlapping trajectories.

Part 1: Earliest collision on a straight road

You are given a list of cars moving on a 1D road. Car i starts at position x, has velocity v, constant acceleration a, and radius r. Its center is at x(t) = x + v*t + 0.5*a*t^2, and it occupies the interval [x(t)-r, x(t)+r]. Two cars collide when their occupied intervals overlap. Return the earliest collision time for any pair with t >= 0, together with the pair of original 0-based indices. If multiple pairs collide at the same earliest time, return the lexicographically smallest pair. Return None if no collision ever occurs. Round the time to 6 decimal places.

Constraints

1 <= n <= 200000
-10^6 <= x, v, a <= 10^6
0 <= r <= 10^6
Inputs may be integers or floats
Cars move independently; you only need the first collision time, not post-collision dynamics

Examples

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

Expected Output: (0.8, (0, 1))

Explanation: The center distance is 10 - 10t. Collision starts when it becomes 2, so t = 0.8.

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

Expected Output: (0.0, (0, 1))

Explanation: Cars 0 and 1 already overlap at t = 0 because their center distance is 3 and their radii sum is 4.

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

Expected Output: (2.0, (0, 1))

Explanation: Their center distance is 10 - 2t^2. Collision starts when it becomes 2, so t = 2.

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

Expected Output: None

Explanation: The second car accelerates away, so the gap never closes.

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

Expected Output: None

Explanation: A single car cannot collide with anything.

Hints

If there is no overlap at t = 0, the left-to-right order of car centers cannot change before the first collision. That means only initially adjacent cars can create the first collision.
For two adjacent cars, write the gap between their occupied intervals as a quadratic in t and solve for the earliest time when the gap becomes <= 0.

Part 2: Earliest collision on a plane

You are given a list of cars moving in 2D. Car i starts at (x, y), has velocity (vx, vy), constant acceleration (ax, ay), and radius r. Its center is p(t) = p + v*t + 0.5*a*t^2. Two cars collide when the Euclidean distance between centers is at most the sum of their radii. Return the earliest collision time for any pair with t >= 0, together with the pair of original 0-based indices. If multiple pairs collide at the same earliest time, return the lexicographically smallest pair. Return None if no collision ever occurs. Round the time to 6 decimal places. For this coding version, n is small enough for pairwise checking; in a follow-up, discuss broad-phase pruning for much larger n.

Constraints

1 <= n <= 250
-10^4 <= x, y, vx, vy, ax, ay <= 10^4
0 <= r <= 10^4
Inputs may be integers or floats
An O(n^2) pair check is acceptable for this version

Examples

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

Expected Output: (3.0, (0, 1))

Explanation: The moving car reaches center distance 2 from the stationary car at t = 3.

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

Expected Output: (0.0, (0, 1))

Explanation: The cars already overlap at t = 0 because the distance is 3 and the radii sum is 4.

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

Expected Output: (2.828427, (0, 1))

Explanation: The x-distance is 10 - t^2, so collision starts when it becomes 2, giving t = sqrt(8).

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

Expected Output: (2.0, (0, 1))

Explanation: This is a tangential collision: the moving car just touches the stationary car at t = 2.

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

Expected Output: None

Explanation: Their relative position stays constant at vertical distance 10, so they never meet.

Hints

For one pair of cars, the squared distance minus (r1 + r2)^2 is a quartic function of time. You do not need a direct quartic formula if you can reason about monotone intervals.
Find the real critical points of the distance function by solving its derivative cubic, then binary-search the earliest root on the first interval where the function can cross zero.

Quick Overview

This question evaluates proficiency in kinematics, computational geometry, numerical root-finding, and scalable algorithm design for collision detection among moving objects, including attention to numerical precision and overlapping trajectories.