Hash Map Design

LFU Cache

Like LRU, but evict the LEAST FREQUENTLY used item. Track access counts for each key. Among items with the same frequency, evict the least recently used one. Requires a more complex bookkeeping structure.

O(1) per op

O(capacity)

How It Works

An LFU cache evicts the least frequently used key, breaking frequency ties by least recent use. Achieving O(1) for both operations takes three coordinated structures: a map from key to (value, frequency), a map from frequency to a doubly-linked list of keys at that frequency ordered by recency, and a running minimum frequency. Accessing a key removes it from its current frequency list and appends it to the (frequency + 1) list.

Eviction pops the least recent key from the minFreq list. The minimum frequency only needs adjusting in two cases: it resets to 1 when a new key is inserted, and increments when the last key leaves the current minFreq bucket — which is what keeps every operation constant time.

Step-by-Step Visualization

LFU Cache: evict LEAST FREQUENTLY used

put(1,A)

put(2,B)

get(1)

put(3,C)

Freq Mapempty

1/3

Code

Java

class LFUCache {
  int cap, minFreq;
  Map<Integer, Integer> keyToVal = new HashMap<>();
  Map<Integer, Integer> keyToFreq = new HashMap<>();
  Map<Integer, LinkedHashSet<Integer>> freqToKeys = new HashMap<>();

  LFUCache(int cap) { this.cap = cap; }

  int get(int key) {
    if (!keyToVal.containsKey(key)) return -1;
    updateFreq(key);
    return keyToVal.get(key);
  }

  void put(int key, int val) {
    if (cap <= 0) return;
    if (keyToVal.containsKey(key)) {
      keyToVal.put(key, val);
      updateFreq(key);
      return;
    }
    if (keyToVal.size() >= cap) evict();
    keyToVal.put(key, val);
    keyToFreq.put(key, 1);
    freqToKeys.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
    minFreq = 1;
  }
}

Tips & Gotchas

1Track frequency of each key and a list per frequency

2Maintain the minimum frequency for O(1) eviction

3On access, move key from freq list to freq+1 list

Practice Problems

1LFU Cache
2LRU Cache
3Design In-Memory File System

About the Hash Map Design Pattern

Some problems ask you to build data structures that combine a hash map with other structures to achieve specific performance guarantees.

Key insight

If brute force is O(n²) because of a nested search, a hash map usually drops it to O(n). The tradeoff is O(n) extra space.

Common Hash Map Interview Problems

Two Sum
Subarray Sum Equals K
Top K Frequent Elements
LRU Cache
Group Anagrams
Longest Consecutive Sequence

Frequently Asked Questions

How does LFU decide between two keys with equal frequency?

The standard specification falls back to LRU order among keys tied at the minimum frequency, evicting the least recently used of them. That is why each frequency bucket is kept as a recency-ordered doubly-linked list rather than an unordered set.

Why is tracking minFreq safe without scanning all frequencies?

Frequencies only change by +1 on access, so the minimum can never silently jump downward except when a brand-new key arrives at frequency 1. It rises only when the current minimum bucket empties, and both events are detectable in O(1) at the moment they happen.

When would LFU be preferred over LRU in practice?

LFU suits workloads with stable popularity skew, where a few hot items dominate long-term, because a one-time burst cannot flush them out. LRU adapts faster to shifting access patterns and is simpler, which is why it is the more common default.