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

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Tesla during technical interviews.

Compute suffix sums over waypoints | Tesla Coding Question

Quick Overview

This question evaluates a candidate's ability to compute geometric suffix sums over batched 2D trajectories, testing skills in array manipulation, Euclidean distance computation, and runtime-conscious algorithm design within the Coding & Algorithms domain.

Compute suffix sums over waypoints

Company: Tesla

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

## Problem You are given a batch of 2D waypoint trajectories. - Input: `points` with shape **[B, N, 2]**, where `points[b][i] = (x, y)` is the i-th waypoint for batch item `b`. - Output: `rem` with shape **[B, N]**. For each batch item `b` and waypoint index `i`, define `rem[b][i]` as the **remaining path length** from waypoint `i` to the end, computed as the suffix sum of Euclidean segment lengths: \[ rem[b][i] = \sum_{j=i}^{N-2} \|points[b][j+1] - points[b][j]\|_2 \] Also define `rem[b][N-1] = 0`. ### Requirements - Time complexity: **O(B·N)**. - Handle edge cases such as `N = 1`.

Quick Answer: This question evaluates a candidate's ability to compute geometric suffix sums over batched 2D trajectories, testing skills in array manipulation, Euclidean distance computation, and runtime-conscious algorithm design within the Coding & Algorithms domain.

You are given a batch of 2D waypoint trajectories as `points`, where `points[b][i] = (x, y)` is the `i`-th waypoint in batch item `b`. For each trajectory, compute an array `rem` of the same length such that `rem[b][i]` is the remaining path length from waypoint `i` to the end. This is the suffix sum of Euclidean distances between consecutive waypoints: `rem[b][i] = sum_{j=i}^{N-2} sqrt((x_{j+1}-x_j)^2 + (y_{j+1}-y_j)^2)`. Also, `rem[b][N-1] = 0`. The solution must run in `O(B·N)` time and handle edge cases such as a trajectory with only one waypoint.

Constraints

0 <= B
Each trajectory contains N waypoints, where N >= 1 in the standard case
Each waypoint has exactly 2 coordinates
The algorithm should run in O(B·N) time

Examples

Input: ([[(0, 0), (3, 4), (6, 8)]],)

Expected Output: [[10.0, 5.0, 0.0]]

Explanation: The segment lengths are 5 and 5, so the remaining distances are [10, 5, 0].

Input: ([[(0, 0), (0, 3), (4, 3), (4, 0)], [(1, 1), (4, 5), (7, 9), (7, 9)]],)

Expected Output: [[10.0, 7.0, 3.0, 0.0], [10.0, 5.0, 0.0, 0.0]]

Explanation: First trajectory has segment lengths 3, 4, 3. Second has 5, 5, 0 because the last two points are identical.

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

Expected Output: [[0.0]]

Explanation: A trajectory with one waypoint has no remaining path, so the only value is 0.

Input: ([],)

Expected Output: []

Explanation: An empty batch produces an empty result.

Input: ([[(-1, -1), (-1, 2), (3, 2), (3, 2)]],)

Expected Output: [[7.0, 4.0, 0.0, 0.0]]

Explanation: The segment lengths are 3, 4, and 0, so the suffix sums are [7, 4, 0, 0].

Solution

def solution(points):
    import math

    result = []
    for traj in points:
        n = len(traj)
        if n == 0:
            result.append([])
            continue

        rem = [0.0] * n
        running = 0.0

        for i in range(n - 2, -1, -1):
            x1, y1 = traj[i]
            x2, y2 = traj[i + 1]
            running += math.hypot(x2 - x1, y2 - y1)
            rem[i] = running

        result.append(rem)

    return result

Time complexity: O(B·N). Space complexity: O(B·N) for the returned array.

Hints

For one trajectory, try processing waypoints from right to left instead of recomputing the remaining distance from scratch for every index.
Keep a running suffix total of segment lengths and update it as you move backward.

Quick Overview