DSA interview question

LFU Cache

Hard · Data structures · Topics: hash map, doubly linkedlist, design

The problem

A recommendation service caches model outputs. Unlike LRU, it wants to keep popular entries: when full, it evicts the least frequently used key, and among keys with the same (lowest) use count it evicts the least recently used one. get and put must be O(1). The design keeps one recency list per frequency, a map from each key to its value, frequency and list position, and the current minimum frequency. A use moves the key from its frequency's list to the next frequency's list. Eviction takes the oldest key in the minimum-frequency list.

Example: capacity 2: put(1,1), put(2,2), get(1), put(3,3) evicts key 2 (used once, versus twice for key 1).

Function signature

class LFUCache {
public:
    explicit LFUCache(int capacity);
    int get(int key);               // -1 if absent
    void put(int key, int value);
};

Test cases

Operations (capacity)	Output	Explanation
(2) `put(1,1) put(2,2) get(1) put(3,3) get(2) get(3) put(4,4) get(1) get(3) get(4)`	`1 -1 3 -1 3 4`	LeetCode's example: 4 evicts 1 (tied frequency, older use)
(0) `put(0,0) get(0)`	`-1`	Zero capacity stores nothing
(1) `put(1,1) put(2,2) get(1) get(2)`	`-1 2`
(2) `put(1,1) put(2,2) put(1,5) put(3,3) get(2) get(1)`	`-1 5`	Updating 1 raised its frequency

(Confirm: get and put on an existing key both count as a use; a newly inserted key has frequency 1; ties are broken by least recent use.)

How interviewers phrase it

"Design and implement a data structure for a Least Frequently Used (LFU) cache, with get and put in O(1)" (LeetCode 460).

Clarifying questions to ask

How are frequency ties broken? (Least recently used first.)
Does updating a key's value count as a use? (Yes.)
Can the capacity be 0? (Yes: every put is ignored.)

Follow-ups to expect

"Why not a heap keyed by (freq, time)?"
"How is minFreq maintained?"
"What's inside each frequency bucket?"
"What happens on eviction?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview