Top-K in Time Window - Coding Question, Walmart Labs

Problem summary

You must build a component that records events (item_id, timestamp) and answers frequency-based top‑k queries over a closed interval [t_start, t_end]. You will implement record and query APIs, then extend the design to support explicit eviction of old events, out‑of‑order (late) arrivals, and an optimized version when timestamps come from a bounded discrete domain.

What you'll be asked to do

You should show an implementation that maintains per‑timestamp or per‑bucket counts and can return up to k item IDs with the highest access counts in [t_start, t_end]. Expect to discuss data structures such as hash maps for counts, time buckets (sliding-window aggregates), and a min‑heap (priority queue) to compute top‑k efficiently. You should explain complexity tradeoffs for update and query paths and how tie‑breaking is handled.

Flow & extension stages

1. Basic API: implement record(item_id, timestamp) and query(t_start, t_end, k) with correct closed‑interval semantics.
2. Eviction: add evict_older_than(cutoff) to drop data < cutoff and document correctness guarantees for queries >= cutoff.
3. Out‑of‑order events: introduce an allowed lateness parameter or accept full reaggregation; state whether late arrivals can retroactively change previous query answers.
4. Bounded timestamps: if timestamps lie in a fixed range, switch to array/circular buffer buckets for O(1) eviction and lower memory overhead.

Skill signals interviewers look for

You should demonstrate: time/space complexity analysis, selection of appropriate aggregates vs raw logs, correctness under inclusive intervals, handling late data semantics (bounded lateness vs eventual consistency), and tradeoffs between exact and approximate top‑k (e.g., Space‑Saving / Count‑Min Sketch for high throughput).