LRU Cache
Track: Data structures. 6 stages. Languages: Go, Python, JavaScript, Rust.
Build a cache that stores integer keys and values. A key is the number you use to look up a value. The cache's capacity is the number of keys it can hold. When it is full and you add a new key, remove the key you have not used for the longest time. Implement New(capacity), Get(key) -> (value, found), and Put(key, value) using your language's names. Use only the standard library, not a ready-made LRU cache. Your cache receives one call at a time. For help with the ideas, read the notes.
Where it is used
- Redis and Memcached sit in front of slower databases. When they reach their memory limit, they can drop the least recently used keys to make room.
- A database keeps recently read disk pages in memory, because memory is much faster than disk. When the memory is full, the page nobody has read for the longest time is the cheapest to lose.
- A web server or a CDN keeps popular pages and files close to users. Without a rule for what to drop, the cache either stops taking new items or runs out of memory.
Stages
lc1: Store and read values (very easy)
Use Put to store a value, then return that value with Get. Keys and values can be zero or negative. Example: Put(0, 0), Get(0) -> value 0, found true. Put(-3, -7), Get(-3) -> value -7, found true.
The tester will verify: Get returns the value you stored and reports that it found the key.
lc2: Make room for a new key (easy)
When the cache is full, remove the oldest key to make room for a new one. If a key is missing, report that it was not found. Capacity 3: Put(1, 1), Put(2, 2), Put(3, 3), Put(4, 4) -> Get(1) reports not found, and Get(2) returns 2. Keys 2 to 4 remain.
The tester will verify: Get reports not found for missing or removed keys and returns the values of the keys still in the cache.
lc3: Keep recently read keys (medium)
Reading a key with Get also counts as using it, so it stays in the cache longer. When you need room, remove the key you have not used for the longest time. Capacity 2: Put(1, 1), Put(2, 2), Get(1), Put(3, 3) -> Get(2) reports not found and Get(1) returns 1.
The tester will verify: A key you just read stays in the cache when a less recently used key must be removed.
lc4: Update a stored value (medium)
When you store a new value for an existing key, replace its old value. This also counts as using the key. The update must not take up more space or remove another key. Capacity 2: Put(1, 1), Put(2, 2), Put(1, 99), Put(3, 3) -> Get(2) reports not found and Get(1) returns 99.
The tester will verify: Get returns the updated value, and the updated key stays when a less recently used key must be removed.
lc5: Handle small and large values (hard)
Keep returning the right answers after many reads, updates, and removals. Values can range from -2147483648 to 2147483647. Example: Put(1000, -2147483648), Put(1000, 2147483647), Get(1000) -> value 2147483647, found true.
The tester will verify: Get returns the right value or reports not found, even with negative keys and large values.
lc6: Make Get and Put fast (L2, hard)
Make Get and Put fast even when the cache holds many keys. Your answers must still be correct. Example: if our solution takes 100 ms, the limit is 150 ms. Your solution takes 140 ms, so it passes.
The tester will verify: Your code takes at most 1.5 times as long as our solution in the same language and returns correct answers.