Problem LeetCode 146. LRU Cache ↗ · NeetCode LRU Cache ↗ · LeetCode 460. LFU Cache ↗ · NeetCode LFU Cache ↗· The solutions on this page are my own.

LRU & LFU Cache Visualizer

How SimpleLRUCache and SimpleLFUCache decide which key to throw out. Every example uses a capacity of 3.

just used just added evicted

lines that run are highlighted

LRU SimpleLRUCache.java

A LinkedHashMap is two structures sharing the same entries: a hash table to find a key fast, and a linked list that remembers order. The cache only ever touches the two ends of the list.

Structure. The hash index finds an entry in one step, and each entry links to the one before and after it. Because the order lives in the links, the cache can drop the front or add at the end without scanning anything.

Two operations. get(1) takes key 1 out and puts it back, so it jumps to the end. That leaves 2 at the front, so the next put on a full cache evicts 2, even though 2 was added after 1.

LFU SimpleLFUCache.java

Three plain maps and one number. values and counts answer questions about a key. keysByCount groups keys into one row per use count, and minCount says which row to evict from.

Structure. The row a key sits in is the same number as its entry in counts. To evict, the cache goes to the minCount row and removes its first key. Keys 5 and 7 are both used once, and 5 has waited longer, so 5 goes first.

One use. get(5) raises key 5's count from 1 to 2, so it leaves row 1 and joins the end of row 2. Row 1 still holds 7, so minCount stays 1. If row 1 had emptied, minCount would have moved up to 2.