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

What role is this question designed for?

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

Detect earliest collision among moving cars

Quick Overview

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.

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.

Input: ([5.0, 5.0, 7.0], [1.0, -2.0, 0.0], [0.0, 1.0, 0.0])

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

Explanation: Vehicles 0 and 1 already occupy the same position at t = 0.

Input: ([0.0, 5.0], [1.0, 2.0], [0.0, 0.0])

Expected Output: None

Explanation: The second vehicle starts ahead and is also faster, so the gap never closes.

Input: ([3.0], [1.0], [0.0])

Expected Output: None

Explanation: With fewer than two vehicles, no collision pair exists.

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.

Input: ([(0.0, 0.0), (0.0, 5.0)], [(1.0, 0.0), (1.0, 0.0)], [1.0, 1.0])

Expected Output: None

Explanation: The relative velocity is zero, so the distance between the disks stays 5, which is greater than 2.

Input: ([(0.0, 0.0), (3.0, 0.0)], [(1.0, 0.0), (0.0, 0.0)], [0.0, 0.0])

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

Explanation: These are moving points. The first point reaches x = 3 at t = 3 and meets the second point.

Input: ([(2.0, 2.0)], [(0.0, -1.0)], [0.5])

Expected Output: None

Explanation: With only one disk, there is no pair to test.

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.

Quick Overview