Free Low-level design lessonsLow-level design · Stage 1 · Case studies · Step 1
Case study: LRU cache
A cache that evicts the least recently used entry, with O(1) get and put: the data structure design and why it is two structures. About 13 minutes.
Why does each node in the linked list store its key as well as its value?
- AWhen the tail node is evicted, the key is needed to delete its entry from the map
- BSo it can compute its hash
- CTo sort the list
Show the answer
When the tail node is evicted, the key is needed to delete its entry from the map. The map is keyed by key; the node is found from the list.
4 questions on this idea
Short questions that apply the idea to new cases: trace it, work out a number, put steps in order. A wrong answer explains itself.
Answer them in your browserFree account, no card. Your progress is saved, and the idea comes back in a quick review later.
Sign up free to solve