Q: A sliding window limiter allows 10 requests per second. Under load it lets through 12 in a second. What is the likely bug?prune(log, now - 1.0) if len(log) < 10: log.append(now) return True return False

The prune, count and append run without one lock, so several threads pass the check before any appends The decision reads the count and then writes it in separate steps; concurrent callers all see 9 and all append. The whole prune, check and append must be one critical section (or a CAS on a token count). Shrinking the window hides the race rather than fixing it. A set drops requests with equal timestamps, which miscounts. Threads on one machine share the same monotonic clock.

Question 1

You build a thread safe LRU cache from a concurrent hash map plus a linked list for recency. Is that enough?

Accepted Answer

No: get moves a node in the list, so map and list updates need one lock (or a design that batches recency updates) The invariant spans two structures: the map entry and the node position must change together, and get itself mutates recency. A concurrent map protects only map operations, so list reorders still race and corrupt the list. A read lock for get is wrong because get writes. Volatile only gives visibility of single fields, not atomic multi pointer updates. Real caches use one lock, striped segments, or buffered recency (as Caffeine does).

Question 2

When does replacing a mutex with a read write lock clearly help?

Accepted Answer

Many concurrent readers, rare writes, and read critical sections long enough to matter A read write lock costs more per acquire than a mutex, so it only wins when many readers truly overlap and hold the lock long enough. A slight read majority with tiny critical sections is often slower than a plain mutex. Frequent writes serialise everything and can starve readers or writers. Readers do block when a writer is waiting or holding the lock, so it is not free.

Question 3

Two threads each hold the read lock of a non upgradable read write lock and both try to acquire the write lock to update the entry they read. What happens?

Accepted Answer

Deadlock: each waits for the other to release its read lock A writer needs all readers gone, and each would be writer is itself a reader that will not let go, so both wait forever. Most read write locks (Java ReentrantReadWriteLock, pthread rwlock) do not upgrade. Release the read lock, take the write lock, and re-check the state, or use a lock with an explicit single upgrader mode.

Question 4

A counter uses compare and swap: read v, compute v + 1, CAS(v, v + 1). What must happen when the CAS fails?

Accepted Answer

Re-read the current value and retry the computation CAS fails because the value changed, so the computation must restart from the fresh value. Retrying with the stale value fails every time, because the counter has already moved past it. Giving up loses this thread's increment. Writing v + 1 under a lock that other CAS users ignore overwrites concurrent updates.

Question 5

A lock free stack pops with CAS(head, old, old.next). Thread 1 reads old = A and A.next = B, then stalls. Others pop A, pop B, push A back. Thread 1 resumes. What happens?

Accepted Answer

The CAS succeeds and head becomes B, a node that was already removed This is the ABA problem: CAS only compares the pointer, head is A again, so it succeeds and installs the stale next pointer B. Head changing in between is invisible to CAS. The result is corrupt because B was popped. Fixes are tagged pointers or version counters, hazard pointers, or garbage collected memory that prevents A from being reused while referenced.

Question 6

An in memory key value store with one global lock shows heavy contention on 32 cores, with operations spread across many keys. Which change reduces contention without breaking single key atomicity?

Accepted Answer

Lock striping: hash each key to one of many locks Striping lets operations on different keys proceed in parallel while each key is still guarded by exactly one lock. Removing the lock corrupts the map on concurrent resize or insert. A spinlock is still one global lock and burns CPU under contention. Taking a read lock for a write lets concurrent puts mutate the map at the same time.

Question 7

A striped key value store adds transfer(k1, k2) that must update both keys atomically. How should it lock?

Accepted Answer

Lock both stripes in a fixed global order, such as by stripe index, skipping the second if equal Acquiring stripes in a global order makes cycles impossible, and checking for the same stripe avoids locking one non reentrant lock twice. Argument order deadlocks when one call does (a, b) and another (b, a). Locking separately lets readers see half a transfer. Immediate try lock retries avoid deadlock but can livelock under contention without backoff.

Question 8

A shared counter is declared volatile (Java) or atomic load and store only. Two threads each run count = count + 1 a thousand times. What is the final value?

Accepted Answer

Anywhere up to 2000, because read and write are separate steps Volatile guarantees visibility and ordering of each read and each write, but the read, add and write are three steps, so updates are lost when they interleave. Use an atomic increment or a lock. Always 2000 confuses visibility with atomicity. Always 1000 assumes perfect interleaving that rarely happens. Volatile does not turn off CPU caches; coherence handles that.

Question 9

Design a thread safe LRU cache with per entry TTL that serves a hot read path on many cores. Walk through locking and expiry.

Accepted Answer

Baseline: hash map plus doubly linked list under one mutex; get moves to front, put inserts and evicts the tail, both O(1). Expiry: store an expiry timestamp per entry and treat expired entries as misses on get (lazy), plus a background sweeper or a timer wheel to free memory for entries never read again. Scaling reads: shard into N independent LRUs by key hash (approximate global LRU, much less contention), or record accesses in a per thread buffer and apply recency updates in batches under the lock. Pitfalls: read lock for get (get writes), checking expiry outside the lock, and doing loads on miss while holding the lock (use a per key future so only one loader runs).

Question 10

A sliding window limiter allows 10 requests per second. Under load it lets through 12 in a second. What is the likely bug?prune(log, now - 1.0)
if len(log) < 10:
 log.append(now)
 return True
return False

Accepted Answer

The prune, count and append run without one lock, so several threads pass the check before any appends The decision reads the count and then writes it in separate steps; concurrent callers all see 9 and all append. The whole prune, check and append must be one critical section (or a CAS on a token count). Shrinking the window hides the race rather than fixing it. A set drops requests with equal timestamps, which miscounts. Threads on one machine share the same monotonic clock.

Question 11

A token bucket for many keys needs to refill at r tokens per second. Which refill approach scales best?

Accepted Answer

On each request, add (now minus last refill) times r, capped at capacity, then try to take a token Lazy refill computes tokens from elapsed time when needed, so idle keys cost nothing and no timers exist. A thread per key does not scale past a few thousand keys. A global sweep each millisecond is O(keys) work even when nothing happens. Resetting each second is a fixed window and allows 2x bursts across the boundary.

Question 12

A fixed window limiter allows 100 requests per minute, with the window reset on the minute. What is the most a client can send in any 60 second span?

Accepted Answer

200, by sending 100 at the end of one window and 100 at the start of the next Two adjacent windows each allow 100 and nothing stops a client clustering them around the boundary, so a sliding 60 seconds can see 200. That is why sliding log, sliding window counter or token bucket are used when bursts matter. 100 assumes a sliding window. 150 and 101 are not derived from the rule.

Question 13

A limiter keeps a map from user id to sliding window state. Under load, one global lock is the bottleneck. Which design keeps per user decisions exact and removes the bottleneck?

Accepted Answer

A concurrent map from user id to state, with a lock or atomic update per user entry Users are independent, so per entry locking (computeIfAbsent then lock the entry, or a CAS on the entry) keeps each user's decision atomic while different users proceed in parallel. Dropping the lock lets bursts through and can corrupt the map. Shrinking the critical section to the append separates check from act, which is the race. Per thread maps let a user use the full limit on every thread.

Thread safety and rate limiter interview questions

Thread safe data structures

Concurrent rate limiting

More operating systems topics

Practise these on your commute