Problem 40.2 · Designing Data StructuresHard

LFU Cache

What it teaches: Frequency buckets with a minimum-frequency pointer; ties broken by recency.

Practise it on judges as “LFU Cache”.

In plain words

A shop shelf has room for only a few products. Each product keeps a tally of how often it was picked up. When a new product needs space, the one picked up the fewest times leaves; if two are tied, the one that was picked up longest ago leaves. The trick is to keep products grouped in "used once", "used twice" … boxes, each box in time order, and remember which box is the lowest.

Return the value for get (or −1 if it isn't there). Example: capacity 2: put(1,1), put(2,2), get(1), put(3,3), get(2), get(3) → 1, −1, 3.

The problem

Design LFUCache(capacity) with O(1) get and put. Evict the least frequently used key; on a tie, the least recently used among them.

Example 1

Input: cap 2: put(1,1), put(2,2), get(1), put(3,3), get(2), get(3)
Output: 1, -1, 3

Constraints

1 ≤ capacity ≤ 10⁴

Pattern clues in the wording

→ Evict by use count, then by age

These clues point to Combine Structures to Design: Pair a hash map (fast lookup) with a list, heap or tree (fast ordering) to meet every operation's time limit.

Stuck? Take one hint at a time

LFUCache · starter

import java.util.*;

class LFUCache {
    public LFUCache(int capacity) {}
    public int get(int key) { return -1; }
    public void put(int key, int value) {}
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	ops = ["LFUCache","put","put","get","put","get","get","put","get","get","get"] args = [[2],[1,1],[2,2],[1],[3,3],[2],[3],[4,4],[1],[3],[4]]	[null,null,null,1,null,-1,3,null,-1,3,4]

From slow to fast

Approaches

1. Frequency buckets · O(1) per operation

Frequency buckets

Time O(1) per operation Space O(capacity)

vals, freqs, buckets(freq → LinkedHashSet), minFreq. touch(key) moves a key to freq + 1. Evict the first key of buckets[minFreq].

▶ Dry run: Frequency buckets + minFreqcapacity 2: put(1,1), put(2,2), get(1), put(3,3), get(2), get(3)

vals(map)

1: 12: 2

freqs(map)

1: 12: 1

buckets (oldest first)(map)

1: [1, 2]

state(vars)

minFreq: 1

Step 1/5put(1,1) and put(2,2): both keys are new, so each gets count 1 and joins bucket 1 in arrival order.

Approach 1

import java.util.*;

class LFUCache {
    private final int capacity;
    private final Map<Integer, Integer> vals = new HashMap<>(), freqs = new HashMap<>();
    private final Map<Integer, LinkedHashSet<Integer>> buckets = new HashMap<>();
    private int minFreq = 0;

    public LFUCache(int capacity) { this.capacity = capacity; }

    public int get(int key) {
        if (!vals.containsKey(key)) return -1;
        touch(key);
        return vals.get(key);
    }

    public void put(int key, int value) {
        if (capacity == 0) return;
        if (vals.containsKey(key)) { vals.put(key, value); touch(key); return; }
        if (vals.size() == capacity) {
            int evict = buckets.get(minFreq).iterator().next();
            buckets.get(minFreq).remove(evict);
            vals.remove(evict);
            freqs.remove(evict);
        }
        vals.put(key, value);
        freqs.put(key, 1);
        buckets.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
        minFreq = 1;
    }

    private void touch(int key) {
        int f = freqs.get(key);
        buckets.get(f).remove(key);
        if (f == minFreq && buckets.get(f).isEmpty()) minFreq++;
        freqs.put(key, f + 1);
        buckets.computeIfAbsent(f + 1, k -> new LinkedHashSet<>()).add(key);
    }
}

Verdict: LinkedHashSet gives O(1) insert, delete and oldest.

Before you submit

Edge cases and common mistakes

Test these inputs

Capacity 0
Updating an existing key's value counts as a use

Mistakes people make

Not resetting minFreq when inserting a new key.

Interview

Follow-up questions

When is LFU worse than LRU in practice?

Connect the dots

Where this shows up in real systems

System Design · Topic 10.6 — Eviction Policies: LRU, LFU, TTLLFU keeps frequency buckets and a pointer to the smallest frequency.

Command Palette