Amazon·Software Engineer·Onsite - System Design / Architecture·Senior

SeniorPrefer not to say

May 2026

Summary

Amazon system design round focused entirely on a single meaty problem about high-volume click stream processing. The question kept expanding with follow-ups and I felt like I was playing whack-a-mole with requirements the whole time.

Questions Asked (1)

Design a data structure that handles a high-volume stream of click events (each with a timestamp in milliseconds and a URL). It needs to support inserting events and querying the top-K most-clicked URLs and the count of distinct URLs within a sliding time window. Requirements include near real-time performance, bounded memory via time-based eviction, out-of-order event handling with a max lateness bound, and idempotent inserts via event deduplication.

System DesignAlgorithms & Data StructuresTechnical Trade-offs

Author's notes

This one kept growing.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements (window size, K, lateness bound, throughput) and then propose a composite design: a time-bucketed ring buffer for eviction, a hash map for per-URL counts, a min-heap or sorted structure for top-K, and a deduplication set with TTL. Explain how out-of-order events are handled by assigning them to the correct bucket and updating counts, and how idempotency is achieved via event IDs.

Pro tip: Emphasize the trade-offs between exact and approximate solutions (e.g., using Count-Min Sketch for memory efficiency) and discuss how to handle late events that fall outside the window—either drop them or update historical aggregates if needed. Also, mention that you would validate the design with back-of-the-envelope calculations for memory and throughput.

1. Clarify Requirements and Constraints

Ask about window size, K, event rate, max lateness, memory limits, and whether exact counts are required. This scopes the problem and informs design choices.

2. Design Core Data Structures

Propose a time-bucketed ring buffer (e.g., per-second buckets) for sliding window eviction, a hash map for URL counts per bucket, and a global top-K structure (e.g., min-heap or sorted list) that merges bucket counts.

3. Handle Out-of-Order and Late Events

Use event timestamps to assign events to the correct bucket. For events within the max lateness bound, update the corresponding bucket; for older events, either drop or update a separate late-arrival buffer if needed.

4. Implement Idempotency and Deduplication

Maintain a set of recently seen event IDs with a TTL equal to the window plus lateness bound. On insert, check and skip duplicates to ensure idempotent processing.

5. Discuss Performance and Trade-offs

Analyze time/space complexity, memory bounds, and throughput. Mention alternatives like approximate counting (Count-Min Sketch) for memory-constrained scenarios and how to handle top-K updates efficiently.

Key Points to Mention

Time-bucketed sliding window with ring buffer for O(1) eviction and bounded memory.
Per-bucket URL count maps and a global top-K structure (e.g., min-heap) for efficient queries.
Out-of-order handling: assign events to buckets by timestamp, with a max lateness bound to limit updates.
Idempotency via event ID deduplication set with TTL matching window + lateness.
Trade-offs: exact vs. approximate counting (Count-Min Sketch) for memory vs. accuracy.
Complexity analysis: O(1) amortized insert, O(K) or O(log K) top-K query, and memory proportional to window size and distinct URLs.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.