Find Global and Rolling Top-K URLs Under a Memory Limit
Company: Oracle
Role: Software Engineer
Category: System Design
Difficulty: medium
Interview Round: Onsite
# Find Global and Rolling Top-K URLs Under a Memory Limit
Design a system that consumes a very large stream of URL access records and answers two questions:
1. Which `K` URLs have the highest counts across all retained history?
2. Which `K` URLs have the highest counts in the trailing 24 hours?
The number of distinct URLs can exceed the memory of one machine. Explain exact and approximate options, their error or storage contracts, partitioning, event-time behavior, tie ordering, pseudocode for the main aggregation path, and how results are served.
### Clarifying Questions to Ask
- Must both answers be exact, or is a bounded approximation acceptable for either one?
- What are the event rate, distinct-URL count, query frequency, and retention period?
- Are events ordered, and how late may an event arrive?
- How should ties in counts be ordered?
### What a Strong Answer Covers
- Canonical URL identity and durable ingestion before aggregation.
- Hash partitioning so all counts for one URL reach a consistent owner.
- A disk-backed or distributed exact global count, plus an explicit approximate alternative.
- Expiring time buckets for the trailing window rather than retaining every raw event in memory.
- Local candidate extraction and a deterministic global top-K merge.
- Checkpointing, replay, deduplication, late data, hot keys, and result freshness.
### Follow-up Questions
- How would a count-min sketch change the memory and accuracy guarantees?
- What bucket width would you use for the 24-hour window, and what error can bucket boundaries introduce?
- How would you rebuild the result after discovering that URL canonicalization changed?
Overview: Design memory-bounded global and trailing-24-hour top-K URL analytics over a massive access stream. The solution compares exact disk-backed counts with sketches, uses partitioned time buckets and deterministic merges, and addresses late data, replay, hot keys, checkpoints, and result freshness.
Read the full Oracle Software Engineer interview experience this question came from