Between the Pings

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
mid
Asked in
Zoox

Problem

A robotaxi fleet streams location pings onto a message bus, and you're handed one batch of them in no particular order. For each vehicle, a session is a run of its activity where consecutive pings are no more than gap seconds apart; report how many sessions each vehicle recorded.

The fleet never stops talking. Find where each vehicle paused.

Example 1

Input:

gap = 60, pings = [{"ts":100,"vehicle_id":"AV-1"},{"ts":130,"vehicle_id":"AV-1"},{"ts":400,"vehicle_id":"AV-1"},{"ts":200,"vehicle_id":"AV-2"}]

Output:

{"AV-1":2,"AV-2":1}

Example 2

Input:

gap = 10, pings = [{"ts":500,"vehicle_id":"AV-9"},{"ts":500,"vehicle_id":"AV-9"},{"ts":505,"vehicle_id":"AV-9"}]

Output:

{"AV-9":1}

Worked solution and explanation

Why this problem exists in real interviews

Strip off the fleet-telemetry costume and this is per-key sessionization: bucket an interleaved event stream by vehicle, put each vehicle's events in time order, and count the runs separated by a gap larger than the threshold. Anyone can write the dict-of-lists. The knife that separates candidates is remembering the batch is unordered. The pings come off the bus interleaved and out of sequence, so if you scan them as they arrive you invent gaps that were never there and split one session into three. Sort each bucket first, and the gap test becomes trivial.

Break down the requirements

Step 1: Separate the stream into one timeline per vehicle

One pass over the batch, appending each ping's ts to a list keyed by its vehicle_id. setdefault(vehicle_id, []).append(ts) keeps it to a single line and creates the bucket on first sight. You are pulling the interleaved stream apart into one independent timeline per vehicle.

Step 2: Sort each timeline before you talk about gaps

The batch is unordered, so before the word 'consecutive' means anything you must sort each bucket ascending. Skip this and every difference you compute is against an arbitrary neighbor in insertion order, not the true previous event in time, and the counts are quietly wrong.

Step 3: Count gap-separated runs

Walk the sorted timestamps; each time the difference from the previous one exceeds gap, a new session begins. Sessions equal 1 plus the number of such boundaries, so a vehicle with a single ping is exactly one session and a loop starting at index 1 handles it for free. A difference of exactly gap stays in the same session, because the rule is 'no more than gap'.

The solution

Bucket by vehicle, sort, scan the gaps
def count_sessions(pings, gap):
    by_vehicle = {}
    for p in pings:
        by_vehicle.setdefault(p["vehicle_id"], []).append(p["ts"])
    sessions = {}
    for vehicle_id, times in by_vehicle.items():
        times.sort()
        count = 1
        for i in range(1, len(times)):
            if times[i] - times[i - 1] > gap:
                count += 1
        sessions[vehicle_id] = count
    return sessions

Common follow-up questions