PracHub
QuestionsPremiumLearningGuidesCheatsheetNEWCoaches

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.

  • easy
  • Waymo
  • Coding & Algorithms
  • Data Scientist

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.

Solution

def solution(cars):
    import math
    import heapq

    EPS = 1e-10
    n = len(cars)
    if n < 2:
        return None

    def round_time(t):
        t = round(t, 6)
        if abs(t) < 5e-7:
            t = 0.0
        return t

    def earliest_adjacent_collision(c1, c2):
        x1, v1, a1, r1 = c1
        x2, v2, a2, r2 = c2

        qc = (x2 - x1) - (r1 + r2)
        if qc <= EPS:
            return 0.0

        qb = v2 - v1
        qa = 0.5 * (a2 - a1)

        if abs(qa) <= EPS:
            if qb >= -EPS:
                return None
            t = -qc / qb
            return t if t >= -EPS else None

        disc = qb * qb - 4.0 * qa * qc
        if disc < -EPS:
            return None
        disc = max(disc, 0.0)
        s = math.sqrt(disc)
        r1t = (-qb - s) / (2.0 * qa)
        r2t = (-qb + s) / (2.0 * qa)
        if r1t > r2t:
            r1t, r2t = r2t, r1t

        if qa > 0:
            if r1t >= -EPS:
                return max(0.0, r1t)
            return None
        else:
            if r2t >= -EPS:
                return max(0.0, r2t)
            return None

    def lex_smallest_overlapping_pair(t):
        intervals = []
        for idx, (x, v, a, r) in enumerate(cars):
            pos = x + v * t + 0.5 * a * t * t
            intervals.append((pos - r, pos + r, idx))

        intervals.sort(key=lambda z: (z[0], z[1], z[2]))

        right_heap = []
        idx_heap = []
        active = [False] * n
        uid = 0
        best = None

        for left, right, idx in intervals:
            while right_heap and right_heap[0][0] < left - 1e-9:
                _, old_uid = heapq.heappop(right_heap)
                active[old_uid] = False
            while idx_heap and not active[idx_heap[0][1]]:
                heapq.heappop(idx_heap)

            if idx_heap:
                other = idx_heap[0][0]
                pair = (other, idx) if other < idx else (idx, other)
                if best is None or pair < best:
                    best = pair

            active[uid] = True
            heapq.heappush(right_heap, (right, uid))
            heapq.heappush(idx_heap, (idx, uid))
            uid += 1

        return best

    pair0 = lex_smallest_overlapping_pair(0.0)
    if pair0 is not None:
        return (0.0, pair0)

    order = sorted(range(n), key=lambda i: (cars[i][0], i))
    best_t = float('inf')

    for k in range(n - 1):
        i = order[k]
        j = order[k + 1]
        t = earliest_adjacent_collision(cars[i], cars[j])
        if t is not None and t < best_t - 1e-9:
            best_t = t

    if math.isinf(best_t):
        return None

    pair = lex_smallest_overlapping_pair(best_t)
    return (round_time(best_t), pair)

Time complexity: O(n log n). Space complexity: O(n).

Hints

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

Solution

def solution(cars):
    import math

    EPS = 1e-10
    n = len(cars)
    if n < 2:
        return None

    def round_time(t):
        t = round(t, 6)
        if abs(t) < 5e-7:
            t = 0.0
        return t

    def cbrt(x):
        if x == 0:
            return 0.0
        return math.copysign(abs(x) ** (1.0 / 3.0), x)

    def quadratic_roots(a, b, c):
        if abs(a) <= EPS:
            if abs(b) <= EPS:
                return []
            return [-c / b]
        disc = b * b - 4.0 * a * c
        if disc < -EPS:
            return []
        disc = max(disc, 0.0)
        s = math.sqrt(disc)
        r1 = (-b - s) / (2.0 * a)
        r2 = (-b + s) / (2.0 * a)
        if abs(r1 - r2) <= 1e-8:
            return [r1]
        return [r1, r2]

    def cubic_roots(a, b, c, d):
        if abs(a) <= EPS:
            roots = quadratic_roots(b, c, d)
            roots.sort()
            return roots

        A = b / a
        B = c / a
        C = d / a

        p = B - A * A / 3.0
        q = 2.0 * A * A * A / 27.0 - A * B / 3.0 + C
        disc = (q * q) / 4.0 + (p * p * p) / 27.0

        roots = []
        if disc > EPS:
            sd = math.sqrt(disc)
            u = cbrt(-q / 2.0 + sd)
            v = cbrt(-q / 2.0 - sd)
            roots = [u + v - A / 3.0]
        elif disc >= -EPS:
            u = cbrt(-q / 2.0)
            roots = [2.0 * u - A / 3.0, -u - A / 3.0]
        else:
            m = 2.0 * math.sqrt(-p / 3.0)
            denom = math.sqrt(-(p * p * p) / 27.0)
            arg = (-q / 2.0) / denom
            arg = max(-1.0, min(1.0, arg))
            phi = math.acos(arg)
            roots = [
                m * math.cos((phi + 2.0 * math.pi * k) / 3.0) - A / 3.0
                for k in range(3)
            ]

        roots.sort()
        dedup = []
        for x in roots:
            if not dedup or abs(x - dedup[-1]) > 1e-7:
                dedup.append(x)
        return dedup

    def pair_time(c1, c2):
        x1, y1, vx1, vy1, ax1, ay1, r1 = c1
        x2, y2, vx2, vy2, ax2, ay2, r2 = c2

        ax = 0.5 * (ax2 - ax1)
        ay = 0.5 * (ay2 - ay1)
        bx = vx2 - vx1
        by = vy2 - vy1
        cx = x2 - x1
        cy = y2 - y1
        R = r1 + r2

        def f(t):
            dx = ax * t * t + bx * t + cx
            dy = ay * t * t + by * t + cy
            return dx * dx + dy * dy - R * R

        if f(0.0) <= 1e-9:
            return 0.0

        aa = ax * ax + ay * ay
        ab = ax * bx + ay * by
        ac = ax * cx + ay * cy
        bb = bx * bx + by * by
        bc = bx * cx + by * cy

        crit = cubic_roots(2.0 * aa, 3.0 * ab, bb + 2.0 * ac, bc)
        points = []
        for t in crit:
            if t > 1e-10 and (not points or abs(t - points[-1]) > 1e-7):
                points.append(t)

        left = 0.0
        fl = f(left)

        for right in points:
            fr = f(right)
            if fl <= 1e-9:
                return max(0.0, left)
            if fr <= 1e-9:
                lo, hi = left, right
                for _ in range(80):
                    mid = (lo + hi) / 2.0
                    if f(mid) <= 0.0:
                        hi = mid
                    else:
                        lo = mid
                return hi
            left = right
            fl = fr

        if fl <= 1e-9:
            return max(0.0, left)
        return None

    best_t = float('inf')
    best_pair = None

    for i in range(n):
        for j in range(i + 1, n):
            t = pair_time(cars[i], cars[j])
            if t is None:
                continue
            if t < best_t - 1e-7:
                best_t = t
                best_pair = (i, j)
            elif abs(t - best_t) <= 1e-7 and (best_pair is None or (i, j) < best_pair):
                best_pair = (i, j)

    if best_pair is None:
        return None
    return (round_time(best_t), best_pair)

Time complexity: O(n^2), with constant-time algebra and fixed-iteration binary search per pair. Space complexity: O(1) extra space beyond the input.

Hints

  1. 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.
  2. 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.
Last updated: May 10, 2026

Loading coding console...

PracHub

Master your tech interviews with 7,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Expand Nested Repetition Expressions - Waymo (medium)
  • Find Shortest Paths to Target Nodes - Waymo (medium)
  • Implement Safe Average Function - Waymo (medium)
  • Serialize Expression Tree Minimizing Parentheses - Waymo (medium)
  • Find Shortest Knight Path - Waymo (medium)