- System design: Top-K trending URLs
Design a system that surfaces the top K most-visited URLs over a time window.
Clarify first: the window (last hour vs. last 24h), how fresh results need to be, exact vs. approximate counts, and read vs. write volume.
Ingestion: click or visit events go to a stream (Kafka), partitioned by URL hash.
Counting: stream processors keep per-URL counts in tumbling or sliding windows. Count-Min Sketch is a good approximate option if memory matters.
Top-K: each partition keeps a local top-K heap, and a merge step combines them into the global top-K.
Serving: cache the precomputed results in Redis, so reads never touch the counting path.
Deep dives: hot keys and skew, late or out-of-order events, and exact vs. approximate trade-offs.
- Coding: HTML parser
The prompt was intentionally vague on input and output.
Tip: ask for concrete examples early, then write down input, output and edge cases before coding.
Approach: model the HTML as a tree, then use DFS to traverse it and solve the task.
Takeaway: be ready to model nested structure as a tree quickly.
- Coding and design: LRU cache
Implement an LRU cache, then discuss follow-ups.
Base solution: a hash map plus a doubly linked list gives O(1) get and put.
Follow-up 1, reduce write throughput: every read updates recency, which creates many writes. Options include batching or buffering recency updates, sampling, or approximate LRU such as CLOCK.
Follow-up 2, make it concurrent:
- A single global lock is correct but a bottleneck.
- Better options are sharding into segments with per-segment locks (lock striping) or read-write locks.
- Eviction ordering gets looser as you shard, so be ready to discuss that trade-off.
- Behavioral
The focus was on the work itself rather than generic STAR questions:
- walking through your projects end to end
- the trade-offs you made and why
- how you communicate technical decisions to others
Prepare two or three projects you can go deep on, including the alternatives you rejected and what you'd change.
Discussion
Loading comments…