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.

Hints

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

Loading coding console...