Heap Operations for Streaming Statistics and Medians Questions
Master using two heaps (max-heap for lower half, min-heap for upper half) to maintain running median or percentiles from streaming data efficiently. Understand insertion, deletion, heap balancing, and O(log n) retrieval. Know when to choose max-heap vs min-heap and how to maintain invariants. Practice implementing and debugging heap operations in Python.
HardSystem Design
58 practiced
Given a data stream where items can arrive out of order up to a bounded lateness L (seconds), how would you adjust your sliding-window median implementation to handle late arrivals while maintaining correctness for the time window? Discuss complexity and state management.
Sample Answer
Requirements and constraints:- Event-time sliding window of width W (seconds), items may arrive out-of-order up to bounded lateness L (seconds).- Maintain correct median for each time-window bucket; allow updates when late events arrive within L; drop/side-output events arriving > L.- Throughput and memory must scale with stream rate and time window, and support durable recoverable state.High-level approach:1. Use event-time processing with watermarks. Watermark = max-event-time-seen - allowed-lateness (L). Advance watermark to emit “finalized” results; accept late events if event_time >= watermark - L.2. Divide time into sliding window buckets (e.g., hop size h). For each bucket maintain a median data structure keyed by bucket id (event-time based).3. For median per bucket use a balanced two-heap approach with lazy/deferred deletions or an indexed balanced BST / order-statistics tree / augmented skip-list to support O(log n) insert/delete and O(1) median access. For streams with very high cardinality, use count-min or TDigest for approximate median (trade-off).State management and late arrivals:- Keep buckets whose time range intersects [current_watermark - L, current_time]. Concretely, retain buckets for W + L time span beyond watermark to accept late updates.- On event arrival: - Map to affected sliding buckets (event may belong to multiple overlapping windows). For each bucket: - Insert value into that bucket’s median structure. - If value corresponds to a previously-emitted bucket that was not yet finalized (watermark hasn’t passed bucket_end + L), recompute median and emit an update (or diff).- When watermark passes bucket_end + L, mark bucket finalized: emit final median and evict bucket state (persist final metric if needed).- For out-of-order events with timestamp < watermark - L: route to a late/side output (log or special correction pipeline) and do not update finalized buckets.Durability, correctness and consistency:- Use checkpointing / persistent keyed state (e.g., Flink state backend, Kafka compacted topics) to ensure exactly-once semantics for state updates.- Emit incremental updates (value change or full median) so downstream consumers can apply corrections. Optionally include sequence/versioning per bucket.Complexity:- Per insertion/deletion into a bucket median: O(log m) where m is number of items in that bucket (two-heaps with lazy deletions or order-stat tree).- Each event maps to up to W/h buckets (sliding overlap): worst-case per-event cost O((W/h) * log m).- Memory: O(R * (W + L)) where R = event-rate per second (roughly number of items retained equals rate * (W+L)). Also number of active buckets = (W + L)/h.- If using approximate structures (TDigest), insertion ~ amortized O(log k) with much lower memory and mergeability.Trade-offs:- Exact median per window = higher memory and CPU; approximate algorithms reduce state and CPU but give probabilistic error.- Choosing bucket hop h trades per-event processing vs storage: larger hop -> fewer buckets but coarser updates.- Emitting updates vs final only: updates increase downstream traffic but provide timely corrections; final-only reduces traffic but loses intermediate accuracy.- Handling extremely late data (>L): decide to drop, side-output, or run a separate backfill pipeline.Operational notes:- Tune L conservatively using measured event skew; monitor late-event rates and watermark lag.- Use metrics: state size, update rate per bucket, fraction of late events, watermark lag.This design maintains correctness by keeping per-window state until lateness bound L passes, supporting in-window corrections while bounding memory and latency.
HardTechnical
55 practiced
Explain how to support deletion of arbitrary elements (not just the oldest) in a two-heap median structure when building features that retract user actions. Outline data structures and complexity implications for real-time processing.
Sample Answer
Approach summary- The classic two-heap median (max-heap L for lower half, min-heap R for upper half) supports insert and get-median in O(log n). To support arbitrary deletions (retractions), use either (A) lazy/deferred deletion with auxiliary hash maps, or (B) indexable heaps (heap + position map) or (C) a balanced BST/multiset. I recommend lazy deletion for high-throughput streaming because it’s simple, robust, and amortizes cost.A. Lazy deletion (recommended for streaming)- Data structures: - max-heap L, min-heap R (store values) - deleted_count map (value -> count) or deleted_id map if values not unique - total sizes tracked (logical size = heap.size - deleted_count applied)- Algorithm: - Insert: push into appropriate heap, rebalance (O(log n)) - Delete(x): increment deleted_count[x]; decrement logical size of whichever side x would be in (track counts or attempt to compare to top). If x equals top of a heap, pop and physically discard while top is marked deleted (cleanup). - Rebalance: after ops, call cleanup(top) on both heaps to lazily remove marked items; then ensure |size(L)-size(R)| ≤ 1 by moving tops (each move O(log n)).- Complexity: - Amortized insert/delete: O(log n). Physical removals happen when deleted elements reach the heap top — cost is charged to earlier deletions (amortized).- Notes: - Use unique IDs for identical values (timestamp or sequence id) to delete exact element. - Memory: extra map O(k) where k = number of outstanding deletions not yet cleaned. - Real-time: predictable latency except when many deletions cluster and force repeated pop/cleanup; mitigate by bounding cleanup work per request or doing background cleanup threads.B. Indexable/positioned heaps- Data structures: - heap array + map id -> index- Delete arbitrary element: look up index in map, swap with last, pop, then sift-up/sift-down to restore heap (O(log n)).- Complexity: worst-case O(log n) per delete and insert, no lazy overhead.- Downside: more complex to maintain when moving items between L and R (must update maps), and memory overhead for maps. Better for workloads with frequent deletions by id.C. Balanced BST / order-stat tree (e.g., treap, AVL with subtree sizes, or C++ multiset + order statistics)- Supports insert, delete, find-kth (median) in O(log n). Clean semantics and exact deletions.- Good if you need rank queries or many arbitrary deletes and fewer concurrency constraints.- Downside: higher constants vs. binary heaps, more complex implementation.Production concerns and trade-offs- Uniqueness: assign stable IDs for actions so retractions reference exact items.- Concurrency: use locks/atomic counters or partition streams by key (sharding) to avoid contention.- Real-time SLA: lazy deletion risks bursts of cleanup — mitigate by incremental background cleaning, batching retractions, or using indexable heaps for consistent bounded latency.- Memory and GC: periodically compact deleted_count map; use TTL for stale IDs.- Fault tolerance: persist minimal state (counts, heap tops) or use changelog so you can rebuild.Example pattern- Streaming feature store: maintain two-heap per user-shard; on retraction event carry action_id → increment deleted_count[action_id]; async background task pops marked tops and rebalances; on read return median from cleaned tops.This gives O(log n) amortized per operation with simple implementation (lazy) or strict O(log n) with indexable heaps/BST depending on latency and delete-rate requirements.
EasyTechnical
51 practiced
Design an interview question (with solution outline) to test a candidate's understanding of two-heap median implementations and lazy deletion. The question should be suitable for a 45-minute onsite coding interview for an ML engineer role.
Sample Answer
Question (Prompt for candidate):You need to implement a data structure MedianTracker that supports:- add(num): insert a number- remove(num): remove one occurrence of num (if present)- get_median(): return current median (float)The operations should be efficient for streaming data. Describe your design and implement add, remove, and get_median using two heaps plus lazy deletion. Discuss complexity, edge cases, and how you'd test and deploy this in an ML feature-pipeline (brief).Hints for candidate: Use a max-heap for lower half, min-heap for upper half. For remove, you may not be able to delete arbitrary elements from heap efficiently—use lazy deletion via a hash map of "to-delete" counts.Solution outline (what to expect in an ideal candidate answer):1. Data structures:- max_heap (lower half, Python: invert sign)- min_heap (upper half)- delayed = hashmap<int, count> to track deleted values- sizes: valid sizes for each heap (exclude delayed elements)2. Invariants:- len(max_heap) == len(min_heap) or len(max_heap) == len(min_heap) + 1- All elements in max_heap <= all in min_heap3. add(num):- push into appropriate heap (compare with top)- rebalance heaps (move top between heaps to maintain invariant)4. remove(num) (lazy deletion):- increment delayed[num]++- if num <= top(max_heap) then decrease valid size of max_heap else decrease valid size of min_heap- if top of a heap is marked in delayed, pop and decrement delayed count until top is clean- rebalance if necessary5. get_median():- clean tops of both heaps from delayed entries before reading- if sizes equal -> average of tops- else -> top(max_heap)6. Complexity:- add: O(log n)- remove: amortized O(log n) (extra pops due to lazy deletion)- get_median: O(1) amortized (with occasional O(log n) to clean)Explain correctness: lazy deletion avoids expensive arbitrary-heap removal while keeping amortized bounds.Edge cases & tests:- remove non-existent element (no-op)- duplicates- single element median- even/odd countsProvide simple test cases.Evaluation rubric (leadership/ML-engineer focus):- Clear invariants and correctness reasoning- Correct lazy-deletion bookkeeping and heap rebalancing- Handles duplicates and edge cases- Discusses integration: how this supports streaming feature stats, memory limits, and monitoring in production (e.g., bounded window, persistence).
EasyTechnical
41 practiced
Implement an exercise where you generate a random stream of integers and validate your two-heap running median against a ground truth median computed by maintaining a sorted container. Outline how you'd measure correctness and performance across varying stream lengths.
Sample Answer
Approach:- Generate random integer streams of varying lengths (e.g., [10^2, 10^3, 10^4, 10^5]).- For each stream, maintain two implementations: 1) two-heap running median (max-heap for lower, min-heap for upper) 2) ground-truth: sorted container (bisect insertion into list)- At each insertion compare medians; log mismatches and timings.Example implementation (core loop):Correctness measurement:- For each stream and RNG seed, assert elementwise equality (or float tolerance).- Run many seeds (fuzz-testing) and random distributions (uniform, normal, skewed, duplicates).- Record and report number of failures and example counterexamples.Performance measurement:- Time-to-compute using time.perf_counter for each method per stream length; average over runs.- Memory: track peak process memory (psutil) or approximate sizes (len(list)+heap sizes).- Plot median runtime vs stream length; compute throughput (elements/sec).Reporting:- Table/plots: correctness pass rate, avg latency per insertion, total runtime, memory.- Discuss trade-offs: two-heaps O(log n) per insert vs sorted-list O(n) per insert; expect two-heaps to scale linearly overall while sorted becomes quadratic.Edge cases & best practices:- Test empty stream, all-equal elements, monotonic streams.- Use deterministic seeds and CI job to catch regressions.
python
import heapq, bisect, random, time
def running_median_two_heaps(stream):
lo, hi = [], [] # lo: max-heap (store negatives), hi: min-heap
medians = []
for x in stream:
if not lo or x <= -lo[0]:
heapq.heappush(lo, -x)
else:
heapq.heappush(hi, x)
# rebalance
if len(lo) > len(hi) + 1:
heapq.heappush(hi, -heapq.heappop(lo))
elif len(hi) > len(lo):
heapq.heappush(lo, -heapq.heappop(hi))
# median
if len(lo) == len(hi):
med = (-lo[0] + hi[0]) / 2
else:
med = -lo[0]
medians.append(med)
return medians
def running_median_sorted(stream):
s, medians = [], []
for x in stream:
bisect.insort(s, x)
n = len(s)
med = (s[n//2] if n%2==1 else (s[n//2-1]+s[n//2])/2)
medians.append(med)
return mediansMediumTechnical
53 practiced
Explain trade-offs between using a two-heap exact median and using reservoir sampling plus selection for approximate median estimation in streaming ML preprocessing. Which is more suitable for constant memory and why?
Sample Answer
Brief answer first: Two-heaps give an exact median but require storing essentially all seen elements (O(n) memory). Reservoir sampling + selection uses fixed-size memory O(k) and yields an approximate median whose accuracy depends on k. For strict constant-memory streaming preprocessing where an approximate median suffices, reservoir sampling (or better, streaming quantile sketches) is more suitable.Details and trade-offs:- Two-heap exact median: - Mechanism: max-heap for lower half, min-heap for upper half; keep sizes balanced. - Memory: O(n) (you keep every item seen), update time O(log n). - Pros: exact median at any time; deterministic. - Cons: not feasible when memory must be constant or tiny relative to stream size.- Reservoir sampling + selection: - Mechanism: maintain fixed reservoir of k uniformly sampled items; at query time run selection (or compute median of reservoir). - Memory: O(k) constant if k fixed; per-item update O(1) amortized. - Accuracy: unbiased sample; median estimate error decreases with k. Use Dvoretzky–Kiefer–Wolfowitz (DKW) bounds to relate k to quantile error δ: k = O((1/ε^2) log(1/α)) to guarantee |F_hat − F| ≤ ε with prob ≥1−α. - Pros: predictable memory and CPU; suitable for very large streams and constrained environments. - Cons: approximate; rare-distribution tails or multimodal data can make reservoir median misleading unless k large.Practical note: For quantile/median approximation there are better streaming algorithms (GK sketch, t-digest, q-digest) that give deterministic/error-bounded quantile estimates with memory O(1/ε) and often better accuracy than plain reservoir for same memory. Recommendation: if you truly need constant (fixed) memory and can tolerate approximation, use reservoir sampling for simplicity or a quantile sketch (t-digest/GK) for tighter error guarantees. If you need exact medians and have memory, use two-heaps.
Unlock Full Question Bank
Get access to hundreds of Heap Operations for Streaming Statistics and Medians interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.