FunctionRacerProblemsRace

Two-Tier Cache

HardClassesPython, JavaScript, TypeScript, Java, C++

Implement a class TwoTierCache, a key-value cache with two tiers. A key enters the trial tier when it is first stored, and it moves up to the core tier when it is read while in the trial tier. Each tier keeps its keys in order of use, from least recently used to most recently used. Write these methods:

- TwoTierCache(trial, core) makes an empty cache whose trial tier holds at most trial keys and whose core tier holds at most core keys.
- get(key) returns the value stored under key, or -1 if key is not in the cache (then nothing changes).
- A key in the core tier becomes the most recently used key of the core tier.
- A key in the trial tier moves up: it leaves the trial tier and becomes the most recently used key of the core tier. If the core tier now holds more than core keys, its least recently used key moves down to become the most recently used key of the trial tier. A get never evicts anything.
- put(key, value) stores value under key and returns the key that was evicted from the cache, or -1 if no key was evicted.
- If key is already in the cache, its value is replaced and it becomes the most recently used key of the tier it is in. It does not change tiers, and nothing is evicted.
- Otherwise key becomes the most recently used key of the trial tier. If the trial tier now holds more than trial keys, its least recently used key is evicted from the cache.
- tier_of(key) returns "trial" or "core" for the tier that holds key, or "none" if key is not in the cache. It does not count as a use.
- keys_in(tier) returns the keys of the tier named tier ("trial" or "core"), from least recently used to most recently used. It does not count as a use.

An evicted key that is stored again enters the trial tier like a new key. The tests call the methods in sequence and compare every return value. The expected list holds null for the constructor.

Example 1

TwoTierCache(2, 1)
put(1, 10) returns -1
put(2, 20) returns -1
get(1) returns 10
put(3, 30) returns -1
get(2) returns 20
tier_of(1) returns "trial"
put(4, 40) returns 3
keys_in("trial") returns [1,4]
get(3) returns -1
keys_in("core") returns [2]

Reading 1 moves it up to the core tier. Reading 2 moves it up too, which overfills the one-key core tier, so 1 moves back down to the newest end of the trial tier, after 3. Storing 4 then overfills the trial tier and evicts its least recently used key, 3.

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