Design A Least Recently Used (LRU) Cache (Hard)
Good evening! Here's our prompt for today.
You may see this problem at Indeed, Stripe, Wework, Square, Uber, Quora, Tesla, Gusto, Zynga, and Akamai.
A cache (pronounced cash) is a place of storage that allows for faster data retrieval. Separate from the main data storage, it's usually faster memory that houses frequently accessed values.
With a cache in place, when a client application needs to access data, it'll check the cache first before going to main memory. As an example, web browsers will typically download a page once, and refer to its cached assets in future calls to help speed up the experience.
To determine whether something should be cached, a few eviction strategies are used. IBM refers to eviction as "a feature where file data blocks in the cache are released when fileset usage exceeds the fileset soft quota, and space is created for new files". The process of releasing blocks is called eviction.
One of the most common is LRU, or Least Recently Used. It's exactly as it sounds-- we keep track of usage so that we can "evict" the least recently used key.
Can you implement a LRU Cache where the following code would properly work with some constraints?
1# initialize with a capacity of 3 keys
2cache = Cache(3)
3cache.put(1, 1)
4cache.put(2, 4)
5cache.put(3, 9)
6cache.get(1) # returns 1
7cache.put(4, 16) # evicts key 2
8cache.get(2) # returns -1The put and get methods should have a time complexity of O(1).
Constraints
- The cache size will be <=
100000 - The
keyandvaluewill have values between-1000000000and1000000000
xxxxxxxxxxclass Cache: def __init__(self, capacity): self.count = 0 self.capacity = capacity def get(self, key): # fill in return def put(self, key, value): # fill in returnimport unittestclass Test(unittest.TestCase): def test_1(self): cache = Cache(3) cache.put(1, 1) cache.put(2, 4) cache.put(3, 9) assert cache.get(1) == 1 print("PASSED: Initialize a cache of size 3, and add/get items")