FunctionRacerProblemsRace

Cache That Evicts the Least Read

MediumClassesPython, JavaScript, TypeScript, Java, C++

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

ReadCountCache(2)
put(1, 10) returns -1
put(2, 20) returns -1
get(1) returns 10
put(3, 30) returns 2
get(2) returns -1
read_count(1) returns 1
put(4, 40) returns 3
get(4) returns 40
get(4) returns 40
put(5, 50) returns 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

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Classes problems