Katkat
Back

LRU Cache with Fewer Recency Writes and Concurrent Access

AppleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

Implement a fixed-capacity least-recently-used cache with constant-time get and put, then discuss two follow-ups: cutting the shared-state writes that every read causes when it updates recency, and making the cache safe and fast under concurrent access, including how eviction order changes.

Implement a least-recently-used (LRU) cache with a fixed capacity. It supports get(key), which returns the value stored for the key or reports a miss, and put(key, value), which inserts the key or updates its value. Both operations count as a use of the key. When inserting a new key would exceed the capacity, the cache first evicts the least recently used key.

After the base implementation, the interviewer discussed two follow-ups: reducing the write traffic that recency tracking causes, and making the cache concurrent.

Clarifying Questions

  • What should get return on a miss: a sentinel such as -1, a null value, or an exception?
  • What should happen with a capacity of 0?
  • Are keys and values arbitrary objects, or fixed types such as integers?
  • Is the cache used by a single thread in the base version?

Part 1 — Base implementation

Implement the cache so that get and put both run in constant time on average.

What This Part Should Cover

  • Data structures that give constant-time lookup, recency update and eviction
  • Correct handling of updates to existing keys, eviction order and capacity edge cases
  • Clean code with the complexity of each operation

Part 2 — Reduce write throughput

In the base design, every get changes the recency order, so a read-heavy workload turns every read into a write to shared state. How would you reduce those recency writes, and what does each option cost?

What This Part Should Cover

  • Why recency updates are writes, and where those writes hurt
  • At least two concrete techniques that cut recency writes, with how each one works
  • The effect of each technique on eviction accuracy and hit rate

Part 3 — Make it concurrent

Many threads now call get and put at the same time. Make the cache thread-safe while keeping its throughput high.

Clarifying Questions for this Part

  • Must eviction follow the exact global LRU order, or is an approximate order acceptable under concurrency?
  • What is the read-to-write ratio, and roughly how many threads use the cache?

What This Part Should Cover

  • The correctness and the bottleneck of a single global lock
  • A finer-grained scheme, and how it divides keys and capacity
  • How eviction order changes once the state is split, and when that is acceptable
  • How the concurrency design combines with the write reduction from Part 2

Hints

Hint 1

Two questions per operation: Every operation must find the key's entry quickly and also know which entry is the oldest. Ask whether a single structure can answer both questions in constant time.

Hint 2

How exact must recency be: Ask whether the cache must evict exactly the least recently used key, or whether a key that is nearly the least recently used would do.

Hint 3

Reads are writes too: Before reaching for a read-write lock, check whether `get` really leaves the shared state unchanged in your design.

Hint 4

Split the state: Think about what you would gain, and what you would lose, if different keys were managed by independent pieces of state.

Follow-up questions

  • How would you add a time-to-live per entry on top of LRU eviction?
  • A scan reads a million keys once each and flushes your hot entries. How would you protect them?
  • With sixteen shards, one shard ends up holding all the hot keys. What happens, and how would you respond?
  • How would you measure whether an approximate policy costs hit rate in production?