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.
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.
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.