Caches: LRU, LFU, and What They Are Really Testing
The LRU cache turns up at several major trading firms and is close to universal outside them. It endures as an interview question for a good reason: it is the simplest problem that cannot be solved with one data structure, so it tests whether you can hold an invariant across two.
The requirement that forces the design
Get and put must both be , and on eviction the least recently used key must go. Take those one at a time.
Constant-time lookup by key means a hash map. Constant-time identification of the least recently used item means an ordering you can read the end of without searching, and constant-time promotion of any item to the most recent means removing a node from the middle of that ordering without walking to it. An array cannot do the last one. A doubly linked list can, in constant time, provided you already hold the node.
The rest of this lesson is for subscribers
Unlock every lesson in Programming for Quantitative Developers, and every other premium course.
Subscribe to continueTest your knowledge
Keep reading Programming for Quantitative Developers
25 lessons in this course, and every other premium course, on one subscription.
- Every lesson in every course, with the worked examples and interactive simulators
- Graded questions on every lesson, with explanations for the wrong answers as well as the right one
- The trainers, timed assessments and brainteaser library that go with them