Design rolling-window top-K click tracker

Q: Design rolling-window top-K click tracker

This question evaluates a candidate's competency in streaming data processing, sliding-window aggregation, top-K frequency maintenance, deduplication under event lateness, and concurrent, horizontally scalable system design.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You receive a high-volume stream of click events (timestamp in ms, url). Implement a data structure with two operations:

record(event) inserts one event;
queryTopK(T, K, now) returns the K most-clicked URLs in the half-open interval (now − T, now], and queryUnique(T, now) returns the number of distinct URLs in that interval. Requirements: maintain near real-time results with efficient insert and eviction; target O(log K) or better per event for top-K maintenance; ensure memory stays bounded via time-based eviction. Handle out-of-order events with maximum lateness L and deduplicate by an event id for idempotency. Discuss the data structures you would use (e.g., time-bucketed sliding windows, hash maps for counts, heaps for top-K, deques for expirations), analyze time/space complexity, and explain how you would adapt the design for concurrency (multiple producer threads, lock contention minimization, atomicity of updates) and horizontal sharding.

Design rolling-window top-K click tracker

Overview

Comments (0)