15 system design interview questions on rate limiters, URL shorteners, caches and key value stores, each with the correct answer and a full explanation.
A rate limiter for a 50k QPS API on 40 nodes: limits must be global per user, short bursts allowed. Which design?
Show answer
Answer
Token bucket per user in Redis, updated atomically with a Lua script
A shared token bucket enforces one global limit and allows bursts up to bucket size; Lua keeps refill and take atomic. Per node counters let a user get 40x the limit by spreading requests. Fixed windows allow up to 2x the limit at a window edge. A SQL insert per request at 50k QPS is too slow and grows forever.
A fixed window limiter allows 100 requests per minute, windows starting on the minute. What is the most a client can send in 2 seconds?
Show answer
Answer
200
Send 100 at 0:59 and 100 at 1:00; each window sees exactly 100. Sliding window or token bucket fixes this. 100 assumes windows slide. 101 and 150 have no basis in the window math.
Clients exceed the limit under concurrency. What is wrong?
count = int(redis.get(key) or 0)
if count < LIMIT:
redis.set(key, count + 1, ex=60)
allow()
Show answer
Answer
GET and SET are separate, so concurrent requests read the same count; use INCR or a Lua script
Single threaded means each command is atomic, not a sequence of commands. Two requests can both GET 5 and both SET 6. INCR returns the new value atomically, with EXPIRE on the first increment, or do it in Lua. This code also resets the TTL on every SET. A longer TTL does not fix the race. A local cache makes counts less accurate.
Design a distributed rate limiter for a public API. Give requirements, the algorithm and two deep dives.
Show answer
Answer
Requirements: per user or key limits, global across nodes, low added latency (under a few ms), fail open or closed decided up front, clear 429 with Retry-After.
Algorithm: token bucket (bursts) or sliding window counter (smooth), state in Redis keyed by client, updated in a Lua script.
Placement: API gateway or middleware before business logic.
Deep dive 1, scale: shard Redis by key, local pre-check or batching for hot keys, accept slight overrun.
Deep dive 2, failure: Redis down means fail open for most APIs (availability) or closed for abuse sensitive ones, with local fallback limits.
Mention multi region: per region limits or async sync of counters with tolerance.
A URL shortener creates billions of codes on many writer nodes. Codes must never collide and should be short. How do you generate them?
Show answer
Answer
Hand each node unique counter ranges (or Snowflake style IDs) and base62 encode
Disjoint ranges or Snowflake IDs are unique without coordination per request, and base62 keeps them short. Truncated hashes collide and need a check and retry. A single auto increment database is a bottleneck and single point of failure. A UUID is 36 characters, defeating the short URL.
Your shortener must record every click for analytics. Which redirect status do you return?
Show answer
Answer
302 Found
302 is temporary, so browsers come back to you on every click. 301 and 308 are permanent and cacheable by default, so repeat clicks skip your server and are not counted. A 200 with meta refresh is slower, worse for clients and crawlers, and not a redirect.
Each cache node needs O(1) get, O(1) put and LRU eviction. Which structure?
Show answer
Answer
Hash map plus doubly linked list
The map finds the node, the list moves it to the front and pops the tail, all O(1), which is what OrderedDict gives you. A heap needs O(log n) per access update. A sorted array needs O(n) moves. Scanning on eviction is O(n).
A single node LSM key value store writes to its WAL with fsync, updates the memtable and acks. It crashes before flushing the memtable. Why is no acked data lost?
Show answer
Answer
The WAL is replayed on restart to rebuild the memtable
The write ahead log is the durable copy until the memtable flushes to an SSTable. The memtable is in memory. The question says single node, so there are no replicas. SSTables are written on flush, not per put, which is what makes LSM writes fast.
An LSM store keeps a Bloom filter per SSTable. What does it do on a read?
Show answer
Answer
Skips SSTables that definitely do not contain the key
A Bloom filter has no false negatives and some false positives, so it can rule out SSTables and save disk reads, but a yes is only a maybe. It cannot point to the one table that has the key. Compression and sort order are separate parts of the SSTable format.
A shopping cart store must accept writes during a network partition, and an item added on either side must never be lost. How do you resolve concurrent versions?
Show answer
Answer
Track versions with vector clocks and merge the siblings (union of items)
Vector clocks detect concurrent versions and the application merges them, which is Dynamo's cart design. Last write wins discards one side's item. Rejecting writes or requiring a leader breaks the always writable requirement.
Why do Twitter style Snowflake IDs fit tweet IDs better than UUIDv4?
Show answer
Answer
They are 64 bit and roughly time sortable, generated without coordination
Snowflake packs a timestamp, a worker id and a sequence into 64 bits, so IDs sort by time and fit in a long index column. They are only roughly ordered across machines, not strictly sequential. They depend heavily on the clock. Encoding is not what makes them short, the 64 bit size is.
An NTP adjustment moves a Snowflake worker's clock back 50 ms. What should the generator do?
Show answer
Answer
Refuse to generate (or wait) until the clock passes the last timestamp used
Generating with an earlier timestamp can reproduce IDs already issued in that millisecond, so the generator must wait or error. Keeping on or resetting the sequence risks exact duplicates. Going further back makes it worse.
