Cache Design LRU and LFU

Opening scenario

Design an LRU cache (LC 146). Implement get(key) and put(key, value) so that both run in O(1) average time, with a fixed capacity. When the cache is full and a new key is inserted, evict the least recently used entry. Follow-up you should expect: LFU cache (LC 460) — evict the least frequently used entry instead, breaking ties by least recently used.

get returns the stored value or -1 when a key is absent; put inserts a key or updates its value. Successful reads and writes refresh recency. For LFU, a new entry starts with frequency 1, and each successful get or update increments it. The LRU example assumes positive capacity; the LFU example also handles zero capacity. Start by listing the information needed to choose an eviction without scanning. LC numbers identify LeetCode problems.

Question progression

Q1 — Why can't a single dictionary solve this?

Question: A Python dict already gives O(1) get and put.…