LFU Cache

Track: Data structures. 6 stages. Languages: Go, Python, JavaScript, Rust.

Build a cache that holds a fixed number of keys. When it is full and a new key arrives, it must drop the key you have used the least, not the one you added longest ago. That is the whole difference from a plain recency cache: here, how often a key was touched matters more than when. Implement New(capacity), Get(key) -> (value, found), Put(key, value), and Len() -> int using your language's names.

Here is how uses are counted:

• Get on a key that is there counts as one more use of it, and a miss touches nothing.
• Put always counts as a use too, whether the key is brand new or already there.
• A use count never drops on its own. It only grows, and it never resets on a timer.
• Updating a key that is already in the cache never makes another key leave, even if the cache is completely full.
• A key that leaves is forgotten completely. If you add it again later, it starts over at one use, as if it had never been there.

key:   1    2    3
uses:  2    1    1

Here keys 2 and 3 are tied for the fewest uses. When the cache needs to drop one of them, the tie-break rule is: whichever of the two was touched less recently leaves first.

A tiny example of that tie-break: capacity 2.

Put(1, 1)   -> key 1 now has 1 use
Put(2, 2)   -> key 2 now has 1 use (tied with key 1)
Put(3, 3)   -> the cache is full. Keys 1 and 2 are tied at 1 use each.
               Key 1 was touched longer ago than key 2, so key 1 leaves.
Get(2) -> (2, true)
Get(1) -> (0, false)

Build the structure yourself. No ready-made LFU or cache type from a library. Your cache receives one call at a time. For help with the ideas, read the notes.

Where it is used

• Redis can keep the keys that are read most often and drop the rarely read ones when its memory is full. This helps when a few keys stay popular for hours.
• Caffeine, a popular Java cache library, counts how often each key is asked for and uses that count to decide which keys may stay.
• A CDN or an image cache keeps the files that many users ask for again and again. A file that one user opened once should leave before a file that thousands open every day, even if that one user opened it a moment ago.

Stages

lf1: hello: put then get (very easy)

Store a couple of keys, then read them back. A stored value of 0 still counts as found, it is not a missing-key signal. Example: Put(1, 10), Get(1) -> value 10, found true. Put(2, 0), Get(2) -> value 0, found true.

The tester will verify: Get returns the value you stored and reports that it found the key, even when that value is 0.

lf2: fill the cache, then make room for one more (easy)

Fill the cache to its capacity without reading any of the keys back, then add one more key. Since all the original keys are tied on uses, the one that has been sitting there longest leaves. Capacity 3: Put(1, 1), Put(2, 2), Put(3, 3), Put(4, 4) -> key 1 leaves, Len() stays at 3.

The tester will verify: capacity is never exceeded, and Len() matches the number of keys really in the cache, including right after a key leaves.

lf3: drop the key used least, not the oldest one (medium)

Reading a key counts as a use. Capacity 2: read key 1 once before two more keys force a key out. Key 1 now has more uses than key 2, so key 2 leaves even though key 1 has been there longer. Example: Put(1, 1), Get(1), Put(2, 2), Put(3, 3) -> Get(2) reports not found, Get(1) returns 1.

The tester will verify: the cache drops the key with the fewest uses, never just the oldest one, even when the key that was just used is also the one sitting there the longest.

lf4: updating a key counts as a use, ties go by recency (medium-hard)

Storing a new value for a key you already have counts as a use too, just like reading it, and it must never make anything leave, even when the cache is completely full. When two keys end up truly tied on uses, the one touched less recently leaves. Capacity 2: Put(1, 1), Put(2, 2) (tied at 1 use each), Get(2) (key 2 now at 2 uses), Put(1, 10) (updates key 1's value and bumps it to 2 uses too, Len() must still read 2). Now Put(3, 3) needs room: both key 1 and key 2 are at 2 uses, but key 2 was touched less recently, so key 2 leaves.

The tester will verify: updating an existing key bumps its use count and never makes another key leave, however full the cache already is. A genuine tie on uses is broken by recency, never by which key was added first.

lf5: keep the coldest key straight as keys come and go (hard)

After many puts and gets, keys leave and come back, and the cache must always know which key currently has the fewest uses, even as that keeps changing. A key that comes back after leaving starts fresh at one use, like a brand new key. Example: a key leaves the cache, then is added again, then is checked again, followed by a long run of puts and gets checked call by call against our own solution.

The tester will verify: every answer matches our own solution exactly, including right after a key has left and been added back, across a long run of calls.

lf6: get and put speed (L2, hard)

Keep Get and Put fast even when the cache holds thousands of keys and keeps dropping old ones to make room. Keep every answer correct too. 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 every answer stays correct.

Rules

• Build the structure yourself. No ready-made LFU or cache type from a library:
• Go: no third-party package.
• Rust: no lfu or lru crate, standard library only.
• Python: no cachetools.LFUCache and no functools.lru_cache.
• JS: no npm LFU or cache package.
• Grouping keys by their use count with an ordered map is fine, the same trick lru-cache allows, but you still build the use-count tracking and the lowest-count lookup yourself.
• Standard library only.

Read the LFU Cache notes in the wiki