Katkat
Back

Fastest 500-Unit Stretch on a Conveyor Belt From Tick Logs

OptiverSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

Given how many units of material a conveyor belt moves during each fixed-length tick, find the maximum average speed over any continuous time stretch covering exactly 500 units, where the stretch may start or end mid-tick.

A factory conveyor belt's sensor logs how many units of material pass a checkpoint during each tick. Tick i covers the time from second 4 * i to second 4 * i + 4, and the list ticks gives ticks[i], the units moved during tick i. Within a single tick the belt is assumed to move at a constant speed, so after t seconds into tick i (with 0 <= t <= 4), ticks[i] * t / 4 units of that tick's material have passed.

Find the belt's fastest 500-unit stretch: the maximum average speed, in units per second, over any continuous time span during which exactly 500 units passed the checkpoint. The span may start and end partway through a tick.

Function Signature

def fastest_stretch_speed(ticks: list[int], tick_seconds: int, target_units: int) -> float:

Rules

  • A valid stretch is [a, b] with 0 <= a < b <= tick_seconds * len(ticks), during which exactly target_units units pass, under the constant-speed-per-tick model.
  • Average speed of a stretch is target_units / (b - a).
  • A stretch may lie entirely inside a single tick if that tick alone moves at least target_units.
  • Return the maximum average speed over all valid stretches. A returned value within 1% relative error of the true optimum is accepted.

Constraints

  • 1 <= len(ticks) <= 10^5, 1 <= tick_seconds <= 60, 0 <= ticks[i] <= 10^5.
  • sum(ticks) >= target_units, so at least one valid stretch exists.
  • sum(ticks) can reach 10^10; use 64-bit or arbitrary-precision arithmetic for running totals.

Examples

Example 1

Input:  ticks = [200, 200, 200, 200, 200], tick_seconds = 4, target_units = 1000
Output: 50.0

The only way to reach exactly 1000 units is the entire 20-second run: 1000 / 20 = 50.

Example 2

Input:  ticks = [33, 46, 4], tick_seconds = 2, target_units = 52
Output: 22.0

The fastest window starts partway through tick 0 (the fast tick) and ends exactly at the boundary between tick 1 and tick 2 (just before the slow tick), giving roughly 52 / 2.364 ≈ 22.0 units/sec — faster than starting the window exactly at a tick boundary.

Edge Case to Handle

A single tick can move more than target_units by itself — the fastest window may be entirely interior to one tick and never touch a boundary at all (though in that case sliding it to either edge of that tick gives the same speed, since speed is constant within a tick).

Hints

Hint 1

First assume the best window always starts exactly at a tick boundary and interpolate only the end — check this against Example 2 by hand; it gives the wrong (slower) answer, which tells you something about where the true optimum can sit.

Hint 2

Think about nudging a candidate window's start earlier or later by an instant while shrinking or growing the end to keep the total units fixed at target_units — work out when that nudge makes the window shorter.

Hint 3

That nudging argument shows the optimal window always has at least one of its two endpoints sitting exactly on a tick boundary — but it might be the end, not the start.

Hint 4

Run the two-pointer scan twice: once assuming the start is pinned to each boundary (interpolating the end), and once on the reversed sequence (which is the same as pinning the end and interpolating the start). Take the best of both.

Follow-up questions

  • How would the algorithm change if speed within a tick weren't constant, but instead linearly ramped from one known value to another?
  • How would you answer many different target_units queries efficiently against the same ticks array?
  • What's the smallest change to this approach to instead find the *slowest* valid stretch?
  • How would you validate this against a brute-force checker, given the answer only needs to be correct within 1%?