CSE Roadmap

Core tier · about 4 hours · 6 parts

Part 1 of 6 · 1 min read

Why this page comes first in Level 7

In this module you will

  • Build a least-recently-used cache with constant-time get and put.
  • Explain why a map alone, or a list alone, is not enough.
  • Make the cache thread-safe, and say why even get needs the lock.
  • Swap the eviction rule using a policy interface (LRU, FIFO, LFU).
  • Load missing values without computing the same value twice.

The LRU cache is the most asked data-structure design question, and the shortest. It tests whether you can combine two simple structures to meet a cost target, and then whether you can extend the design. Level 6 modules were mostly about modelling. This one is about cost. This page uses the five steps of Level 0, module 4. The source for the cache ideas is the "System Design Interview" book (eviction policies) and "Java Concurrency in Practice" (JCIP) section 5.6 (a result cache). The rest is common practice. The Java code was compiled and run before it was written here. Numbers marked "made up" only show the idea.