Katkat
Back

Sliding-Window Forklift Telemetry: Pings, Shifts, Late Events

OpenAISoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

Build an in-memory telemetry service that counts a forklift's recent pings in a 15-minute window, tracks which forklifts are currently on an active shift, and stays correct when pings arrive late and out of order. Tests bounded-memory eviction and exact window semantics.

You run telemetry for a fleet of warehouse forklifts. Every forklift emits a ping while it operates, with fields:

  • depot: str
  • forklift: int, an id unique only within its depot, so a forklift is identified by the pair (depot, forklift)
  • ts: int, the minute of the ping

Let T be the largest ts seen anywhere in the stream so far, across every depot. "The last 15 minutes" means the closed window [T - 14, T]. When T = 40, the window is [26, 40], and a ping at minute 26 still counts.

Build this service in three parts, each extending the one before. State the time and memory cost of every operation.

Constraints and Clarifications

  • T is global, not per-forklift: a ping from one depot can push the window forward and expire another forklift's pings.
  • Memory must stay bounded by the number of forklifts active in the last 15 minutes, not by total stream history.
  • Ingestion and queries interleave arbitrarily and both run at high volume.

Part 1 — Recent ping count

Implement ping(depot, forklift, ts) and count_recent(depot, forklift) -> int. In this part, ts values arrive in non-decreasing order across the whole stream (never a mix of depots producing out-of-order timestamps), and no ping is ever duplicated.

Because arrivals are non-decreasing, the next ping to expire from any forklift's own history is always its oldest one.

Part 2 — Active shifts

Add clock_in(depot, forklift), clock_out(depot, forklift), and active_shift_count() -> int, returning how many forklifts are currently clocked in (have had a clock_in with no later clock_out). This does not depend on the 15-minute window.

Part 3 — Out-of-order pings

Drop the non-decreasing assumption: ping can now arrive with a ts earlier than one already seen for the same or another forklift (e.g. a delayed network message). count_recent must still reflect the true current window [T-14, T] where T is the maximum ts seen so far across the stream.

A forklift can go quiet for hours and accumulate no queries. Decide when its old pings actually get removed — on every ping globally, or only when that forklift is touched again?

Examples

ping("D1","F1",1); ping("D1","F1",3); ping("D1","F2",5); ping("D1","F1",20)
# T is now 20, window [6,20]; F1's pings at 1 and 3 have expired
count_recent("D1","F1") -> 1
count_recent("D1","F2") -> 0   # the ping at 5 expired too

Hints

Hint 1

For Part 1, keep a deque per (depot, forklift), plus one global deque of every ping in arrival order — evicting from the global deque's front tells you exactly what to drop from the per-forklift deque.

Hint 2

For Part 2, a plain set of currently clocked-in ids answers both clock_in/clock_out and the count in O(1); you don't need timestamps at all for that part.

Hint 3

For Part 3, since a forklift's own pings are no longer sorted as they arrive, keep each forklift's timestamps in a list kept sorted with bisect.insort, and trim the stale prefix with bisect_left whenever that forklift is touched.

Hint 4

Don't try to evict every forklift's stale pings eagerly on each ping in Part 3 — that's unbounded work; only trim the pair being accessed, lazily.

Follow-up questions

  • How would you shard this service across machines if one depot alone generates more pings than a single host can hold in memory?
  • How would you support an arbitrary window length chosen per query instead of a fixed 15 minutes?
  • What changes if a ping can also be retracted (the forklift sent a duplicate and one copy must be removed)?
  • How would you test the out-of-order version against the in-order version to prove they agree whenever the input happens to already be sorted?