Design rolling-window top-K click tracker

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

1. record(event) inserts one event;
2. 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.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

You receive a high-volume stream of click events (timestamp in ms, url). Implement a data structure with two operations: 1) record(event) inserts one event; 2) 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 win...

Recommended Approach

For one-time top-K, use a size-K min-heap or quickselect plus sorting the selected K. For streaming windows, maintain counts in a hash map plus a heap with lazy deletion or bucketed frequency structures when updates must be near O(1). Define deterministic tie-breaking.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

One-time heap: O(n log k) time and O(k) space. Quickselect: expected O(n) plus O(k log k) to order output. Streaming complexity depends on window eviction and tie-breaking.

Edge Cases and Tests

k = 0, k > n, duplicate values, ties, negative values, stale heap entries, and deterministic output ordering.