Detect earliest collision among moving cars
Company: Meta
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given **n vehicles** with kinematics parameters. A “collision” means two vehicles occupy the same position at the same time.
Assume continuous time, **t ≥ 0**.
## Part A (1D)
Each vehicle i moves on a line with **constant acceleration**:
- Inputs (arrays of length n):
- `x0[i]` (float): initial position
- `v0[i]` (float): initial velocity
- `a[i]` (float): constant acceleration
- Motion model:
- `x_i(t) = x0[i] + v0[i] * t + 0.5 * a[i] * t^2`
**Task:** Write a function that returns the **earliest collision time** `t*` and one pair `(i, j)` that collides at `t*`, or report **no collision**.
Notes/assumptions:
- Vehicles are treated as **points** (ignore length).
- A collision between i and j occurs if there exists some `t ≥ 0` such that `x_i(t) = x_j(t)`.
- If multiple collisions happen at the same earliest time, returning any one is fine.
- Discuss time complexity; give a baseline approach and at least one optimization idea.
## Part B (2D extension)
Now each vehicle moves in 2D (you may assume **constant velocity** for this part to keep the math tractable):
- Inputs:
- `p0[i] = (x0[i], y0[i])`
- `v[i] = (vx[i], vy[i])`
- `r[i]` (radius)
- Motion model:
- `p_i(t) = p0[i] + v[i] * t`
**Task:** Determine the earliest time `t*` when any pair of disks intersects, i.e. when `||p_i(t) - p_j(t)|| ≤ r[i] + r[j]`, or report **no collision**.
State clearly how you handle edge cases like already-overlapping vehicles at t = 0 and floating-point precision.
Quick Answer: Evaluates continuous kinematics and collision-detection concepts—solving quadratic and linear motion intersections, numerical robustness, and algorithmic time-complexity trade-offs—within the Coding & Algorithms domain for a Data Scientist role at a medium-to-advanced abstraction level.
Part 1: Earliest Collision Time on a Line with Constant Acceleration
You are given n point vehicles moving on a 1D line. Vehicle i starts at x0[i], has initial velocity v0[i], constant acceleration a[i], and follows x_i(t) = x0[i] + v0[i] * t + 0.5 * a[i] * t^2 for continuous time t >= 0. Return the earliest time when any two vehicles occupy the same position. If several pairs collide at the same earliest time, return the lexicographically smallest pair (i, j) with i < j so the result is deterministic. Return None if no collision exists. A baseline O(n^2) pair scan is acceptable; as a follow-up, think about pruning or event-based methods under restricted motion patterns.
Constraints
- 0 <= n <= 2000
- len(x0) == len(v0) == len(a)
- -1e6 <= x0[i], v0[i], a[i] <= 1e6
- Continuous time with t >= 0
- Use a floating-point tolerance of about 1e-9
Examples
Input: ([0.0, 10.0], [2.0, -3.0], [0.0, 0.0])
Expected Output: (2.0, (0, 1))
Explanation: The positions are x0(t) = 2t and x1(t) = 10 - 3t. They meet at t = 2.
Input: ([0.0, 4.0, 100.0], [0.0, 0.0, 0.0], [2.0, 0.0, 0.0])
Expected Output: (2.0, (0, 1))
Explanation: Vehicle 0 follows x(t) = t^2, so it reaches x = 4 at t = 2 and collides with vehicle 1 first.
Hints
- For a fixed pair (i, j), subtract the two motion equations. You get at most a quadratic equation in t.
- Be careful with degenerate cases: the quadratic term may disappear, and sometimes two vehicles share the exact same trajectory, which means the earliest collision is t = 0.
Part 2: Earliest Intersection Time for Moving Disks in 2D
You are given n vehicles modeled as disks in 2D. Vehicle i starts at p0[i] = (x0, y0), moves with constant velocity v[i] = (vx, vy), and has radius r[i]. Its center follows p_i(t) = p0[i] + v[i] * t for continuous time t >= 0. Return the earliest time when any two disks intersect, meaning the distance between centers is at most r[i] + r[j]. If several pairs intersect at the same earliest time, return the lexicographically smallest pair (i, j) with i < j so the result is deterministic. Return None if no intersection ever happens. Count already-overlapping disks as colliding at t = 0, and use a floating-point tolerance around 1e-9.
Constraints
- 0 <= n <= 2000
- len(p0) == len(v) == len(r)
- -1e6 <= coordinates and velocity components <= 1e6
- 0 <= r[i] <= 1e6
- Continuous time with t >= 0
- Use a floating-point tolerance of about 1e-9
Examples
Input: ([(0.0, 0.0), (10.0, 0.0)], [(1.0, 0.0), (-1.0, 0.0)], [1.0, 1.0])
Expected Output: (4.0, (0, 1))
Explanation: The centers start 10 units apart and close at relative speed 2. They first touch when the center distance becomes 2, which happens at t = 4.
Input: ([(0.0, 0.0), (1.0, 0.0), (10.0, 0.0)], [(0.0, 0.0), (0.0, 0.0), (0.0, 0.0)], [1.0, 1.0, 1.0])
Expected Output: (0.0, (0, 1))
Explanation: Disks 0 and 1 already overlap at time 0 because their centers are 1 unit apart and their radii sum to 2.
Hints
- For one pair of disks, switch to relative motion: treat one disk as stationary and let the other move with the relative velocity.
- After squaring the distance condition, you get a quadratic inequality A*t^2 + B*t + C <= 0. Already-overlapping disks correspond to C <= 0 at t = 0.