Cache That Evicts the Least Read
Implement a class ReadCountCache that stores up to capacity key-value pairs. When it has to make room, it throws out the pair that has been read the fewest times. Write these methods:
- ReadCountCache(capacity) makes an empty cache.
- get(key) returns the value stored under key and adds one to that key's read count. If key is not stored, it returns -1 and nothing changes.
- put(key, value) stores value under key.
- If key is already stored, only its value is replaced: its read count and its place in the order of storing stay the same. Returns -1.
- Otherwise, if the cache already holds capacity pairs, one pair is evicted first: the one with the lowest read count, and among those the one that was stored earliest. Then key is stored with a read count of 0. Returns the evicted key, or -1 if nothing had to be evicted.
- read_count(key) returns how many times key has been read since it was stored, or -1 if key is not stored. Asking does not count as a read.
A key that was evicted and is stored again starts over: its read count is 0 and it counts as stored at that moment. The tests call the methods in sequence and compare every return value. The expected list holds null for the constructor.
Example 1
Key 1 was read once and key 2 never, so storing 3 evicts 2. Storing 4 evicts 3, which has no reads. Key 4 is then read twice, so storing 5 evicts 1, the pair with only one read.
Constraints
1 <= capacity <= 40 <= key <= 9and0 <= value <= 99- Each test makes
1to40method calls after the constructor.
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.