Katkat
Back

Compute suffix sums over waypoints

TeslaMachine Learning Engineer · Technical Screen
HardMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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.