Daily bit(e) of C++ | LRU cache
Daily bit(e) of C++ #133, Common interview problem: Implement an LRU cache.
Today we will look at a common C++ interview problem: LRU cache.
Implement a cache with the least-recently-used eviction policy; when inserting a new key and the cache is at capacity, the least recently used key should be evicted.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/8nferf1GG.
Solution
To build the data structure, we need the following operations:
lookup value by key in O(1)
move a key ahead of other keys in O(1)
insert and erase in O(1)
Unordered containers provide key lookup in O(1). Lists provide splicing, which we can utilize to move a key across multiple other keys in O(1).
Unordered containers provide a natural insert and erase in O(1); lists provide O(1) insertion and erase at the front/back of the list.
Putting this together, we can implement our LRU cache:
