K-th Element on a Streaming Time Window

Onsite coding round. Base problem is the standard "k-th element" (quickselect / heap). The follow-up is the actual round: extend it to a streaming setting where queries are over the **last N seconds** of a value stream, under a hard memory bound. Expected approach uses a queue for the time window plus value-bucketed counts. Requirements Base: given an array, return the k-th smallest (or largest) element. Follow-up (the real round): A continuous stream emits (timestamp, value) tuples. For each query, return the k-th element among values whose timestamps fall inside the most recent time window [now − W, now]. Memory must remain bounded: storing every value forever is rejected. Discuss complexity in terms of stream rate, window length, and value range. Notes The interviewer was explicit that the question was "made up on the spot" from a recent project, so do not expect a clean reference solution — the round rewards a thoughtful walkthrough. The expected sketch: A FIFO queue of (timestamp, value) pairs for the time window; pop expired entries on each tick. A bucket array indexed by value range (works when values are bounded integers), with a count_per_bucket. Increment on enqueue, decrement on dequeue. Query in O(B) by walking buckets until cumulative count reaches k, where B is the number of buckets. For unbounded value ranges, fall back to an order-statistics tree (SortedList) with O(log n) insert / delete / k-th lookup. Watch the dequeue ordering: if multiple entries share a timestamp, define the eviction tie-break (FIFO is fine). Preparation Implement quickselect once for the warm-up. Implement the streaming + bucket version: queue of timestamps, int[] bucket array, sliding eviction on tick. Be able to discuss the order-statistics tree fallback (SortedList from sortedcontainers) and its O(log n) cost vs. the bucket's O(B). The reporter ran out of time on the follow-up — budget at most 10 minutes on the base problem. The base half is the canonical "k-th largest in array" — quickselect with Lomuto/Hoare partition runs in expected O(n) average / O(n²) worst; a size-k min-heap is O(n log k). Pick quickselect when interviewers explicitly ask for sub-O(n log n); otherwise the heap version is shorter to write and harder to bug. The streaming follow-up's two-data-structure pattern (FIFO time window + value-bucketed counts) is the canonical answer to "k-th element on a sliding window". The narrower textbook variant, sliding-window median, is solved with two heaps (max-heap of lower half + min-heap of upper half) with lazy deletion — same shape applies if k is fixed at ⌈window/2⌉.