LFU Cache solution and explanation
9 more videos on this problem
Imlement LFU Cache | Leetcode(Hard)take U forward · 19:27 · 217K views
LFU Cache - Leetcode 460 - PythonNeetCodeIO · 14:45 · 69K views
LFU Cache - (Microsoft) : Explanation➕Live CodingcodestorywithMIK · 49:29 · 27K views
LeetCode 460. LFU Cache Explanation and Solutionhappygirlzt · 17:55 · 9K views
LeetCode 460. LFU Cache | Least Frequently Used Cache Implementation | Solution ExplainedJava2Novice · 15:49 · 5K views
[Java] Leetcode 460. LFU Cache [Design #4]Eric Programming · 33:38 · 3K views
Least Frequently Used Cache Design | #FAANG | LeetCode 460code Tree · 26:14 · 1K views
LeetCode - 460. LFU Cache | JavaOrkhan Gasanov · 33:38 · 951 views
460. LFU Cache LFU 缓存【LeetCode 力扣题解】LeetCode 力扣 · 10:50 · 796 views
Daily Leetcode #1034: Jan 29, 2023 - 460. LFU CacheProgramming Live with Larry · 31:49 · 706 views
The problem
Design and implement a data structure for a Least Frequently Used (LFU) cache.
Implement the LFUCache class:
LFUCache(int capacity)Initializes the object with thecapacityof the data structure.int get(int key)Gets the value of thekeyif thekeyexists in the cache. Otherwise, returns-1.void put(int key, int value)Update the value of thekeyif present, or inserts thekeyif not already present. When the cache reaches itscapacity, it should invalidate and remove the least frequently used key before inserting a new item. For this problem, when there is a tie (i.e., two or more keys with the same frequency), the least recently usedkeywould be invalidated.
To determine the least frequently used key, a use counter is maintained for each key in the cache. The key with the smallest use counter is the least frequently used key.
When a key is first inserted into the cache, its use counter is set to 1 (due to the put operation). The use counter for a key in the cache is incremented either a get or put operation is called on it.
The functions get and put must each run in O(1) average time complexity.
Example 1:
Input
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]
Explanation
// cnt(x) = the use counter for key x
// cache=[] will show the last used order for tiebreakers (leftmost element is most recent)
LFUCache lfu = new LFUCache(2);
lfu.put(1, 1); // cache=[1,_], cnt(1)=1
lfu.put(2, 2); // cache=[2,1], cnt(2)=1, cnt(1)=1
lfu.get(1); // return 1
// cache=[1,2], cnt(2)=1, cnt(1)=2
lfu.put(3, 3); // 2 is the LFU key because cnt(2)=1 is the smallest, invalidate 2.
// cache=[3,1], cnt(3)=1, cnt(1)=2
lfu.get(2); // return -1 (not found)
lfu.get(3); // return 3
// cache=[3,1], cnt(3)=2, cnt(1)=2
lfu.put(4, 4); // Both 1 and 3 have the same cnt, but 1 is LRU, invalidate 1.
// cache=[4,3], cnt(4)=1, cnt(3)=2
lfu.get(1); // return -1 (not found)
lfu.get(3); // return 3
// cache=[3,4], cnt(4)=1, cnt(3)=3
lfu.get(4); // return 4
// cache=[4,3], cnt(4)=2, cnt(3)=3
Constraints:
1 <= capacity <= 1040 <= key <= 1050 <= value <= 109- At most
2 * 105calls will be made togetandput.
Approach overview
Problem Overview: Design a cache that evicts the Least Frequently Used (LFU) key when capacity is full. Each operation get(key) and put(key, value) must run in constant time. When multiple keys share the same frequency, the least recently used among them is removed.
Approach 1: HashMap + Frequency Doubly Linked Lists (O(1) time, O(n) space)
The optimal design groups cache entries by their access frequency. Maintain a hash table mapping keys to nodes, and another map from frequency to a doubly linked list that stores nodes with that frequency. Each node stores key, value, and freq. When you call get, look up the node in O(1), remove it from its current frequency list, increment its frequency, and insert it into the next list. Track the current minimum frequency so eviction is constant time: remove the least recently used node from the list representing that frequency. This structure keeps frequency updates and eviction both O(1).
This approach relies on two invariants: (1) nodes are always stored in a list matching their current frequency, and (2) within each frequency list, order represents recency. Because insertion and removal in a linked list are constant time, both cache operations stay O(1). This is the standard interview solution and the one most production-grade LFU implementations follow.
Approach 2: OrderedDict Based LFU (O(1) average time, O(n) space)
Python provides OrderedDict, which maintains insertion order and allows efficient deletion from both ends. You can maintain a dictionary mapping frequencies to OrderedDicts of keys. Another map stores key → (value, frequency). When a key is accessed, remove it from its current OrderedDict, increment its frequency, and insert it into the next one. Eviction happens by removing the first key from the OrderedDict corresponding to the minimum frequency.
This version avoids implementing your own doubly linked list and is easier to code in Python. The tradeoff is less explicit control over the underlying structure, but operations remain O(1) on average because OrderedDict internally uses a hash table and linked list.
Recommended for interviews: Interviewers usually expect the HashMap + frequency doubly linked list design. It demonstrates understanding of system design style data structures, constant-time eviction strategies, and careful state tracking. Mentioning the OrderedDict variation in Python is useful, but implementing the full structure shows deeper mastery.
Approach 1: HashMap and Double Linked List Approach
In this approach, we use a combination of a HashMap (or Dictionary) and a double linked list to ensure O(1) operations for both get and put. The HashMap stores keys and values as well as a reference to the corresponding node in the double linked list, effectively allowing for quick updates and removals. The double linked list maintains the order of keys based on use frequency and recency to guarantee the correct eviction policy.
class Node:
def __init__(self, key, value):
self.key = key
self.value = value
self.freq = 1
self.prev = None
self.next = None
class DoubleLinkedList:
def __init__(self):
self.head = Node(None, None)
self.tail = Node(None, None)
self.head.next = self.tail
self.tail.prev = self.head
def add(self, node):
p = self.head.next
self.head.next = node
node.prev = self.head
node.next = p
p.prev = node
def remove(self, node):
p, n = node.prev, node.next
p.next = n
n.prev = p
def pop_tail(self):
if self.tail.prev is self.head:
return None
tail = self.tail.prev
self.remove(tail)
return tail
class LFUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.size = 0
self.node_map = {}
self.freq_map = {}
self.min_freq = 0
def update_freq(self, node):
freq = node.freq
self.freq_map[freq].remove(node)
if not self.freq_map[freq].head.next != self.freq_map[freq].tail:
del self.freq_map[freq]
if freq == self.min_freq:
self.min_freq += 1
node.freq += 1
freq = node.freq
if freq not in self.freq_map:
self.freq_map[freq] = DoubleLinkedList()
self.freq_map[freq].add(node)
def get(self, key: int) -> int:
if key not in self.node_map:
return -1
node = self.node_map[key]
self.update_freq(node)
return node.value
def put(self, key: int, value: int) -> None:
if self.capacity == 0:
return
if key in self.node_map:
node = self.node_map[key]
node.value = value
self.update_freq(node)
else:
if self.size == self.capacity:
list_to_remove = self.freq_map[self.min_freq]
tail = list_to_remove.pop_tail()
del self.node_map[tail.key]
self.size -= 1
new_node = Node(key, value)
self.node_map[key] = new_node
if 1 not in self.freq_map:
self.freq_map[1] = DoubleLinkedList()
self.freq_map[1].add(new_node)
self.min_freq = 1
self.size += 1class Node {
constructor(key, value) {
this.key = key;
this.value = value;
this.freq = 1;
this.prev = null;
this.next = null;
}
}
class DoubleLinkedList {
constructor() {
this.head = new Node(null, null);
this.tail = new Node(null, null);
this.head.next = this.tail;
this.tail.prev = this.head;
}
add(node) {
const nextNode = this.head.next;
this.head.next = node;
node.prev = this.head;
node.next = nextNode;
nextNode.prev = node;
}
remove(node) {
const prevNode = node.prev;
const nextNode = node.next;
prevNode.next = nextNode;
nextNode.prev = prevNode;
}
popTail() {
if (this.tail.prev === this.head) return null;
const nodeToRemove = this.tail.prev;
this.remove(nodeToRemove);
return nodeToRemove;
}
}
class LFUCache {
constructor(capacity) {
this.capacity = capacity;
this.size = 0;
this.nodeMap = new Map();
this.freqMap = new Map();
this.minFreq = 0;
}
updateFreq(node) {
const freq = node.freq;
const list = this.freqMap.get(freq);
list.remove(node);
if (!list.head.next !== list.tail) {
this.freqMap.delete(freq);
if (freq === this.minFreq) {
this.minFreq++;
}
}
node.freq++;
const newFreq = node.freq;
if (!this.freqMap.has(newFreq)) {
this.freqMap.set(newFreq, new DoubleLinkedList());
}
this.freqMap.get(newFreq).add(node);
}
get(key) {
if (!this.nodeMap.has(key)) return -1;
const node = this.nodeMap.get(key);
this.updateFreq(node);
return node.value;
}
put(key, value) {
if (this.capacity === 0) return;
if (this.nodeMap.has(key)) {
const node = this.nodeMap.get(key);
node.value = value;
this.updateFreq(node);
} else {
if (this.size === this.capacity) {
const list = this.freqMap.get(this.minFreq);
const toRemove = list.popTail();
this.nodeMap.delete(toRemove.key);
this.size--;
}
const newNode = new Node(key, value);
this.nodeMap.set(key, newNode);
if (!this.freqMap.has(1)) {
this.freqMap.set(1, new DoubleLinkedList());
}
this.freqMap.get(1).add(newNode);
this.minFreq = 1;
this.size++;
}
}
}The Python solution involves two custom classes: Node and DoubleLinkedList. The Node class holds key-value pairs, frequency counts, and pointers to previous and next nodes. The DoubleLinkedList class is used to maintain the order based on frequency and recency of use.
The LFUCache class maintains two dictionaries: node_map which maps keys to nodes, and freq_map which maps frequencies to linked lists. The cache operations (get/put) are implemented to update the frequency of nodes appropriately and handle cache capacity by removing the least frequently and recently used nodes when needed.
Time Complexity: O(1) for get and put operations due to the use of HashMap and Doubly Linked List.
Space Complexity: O(capacity) due to storage of nodes and frequency mappings.
Approach 2: OrderedDict Based Approach
The OrderedDict based approach uses Python's built-in OrderedDict to efficiently track keys while maintaining the insertion order. By managing the dictionary's order, we can track the frequency of access and modify it when performing get or put operations. This may not offer the theoretical O(1) complexity for all operations but is a practical solution with simplicity in Python.
from collections import defaultdict, OrderedDict
class LFUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.min_freq = 0
self.key_freq_map = {}
self.freq_map = defaultdict(OrderedDict)
def get(self, key: int) -> int:
if key not in self.key_freq_map:
return -1
freq = self.key_freq_map[key]
value = self.freq_map[freq].pop(key)
if not self.freq_map[freq]:
del self.freq_map[freq]
if self.min_freq == freq:
self.min_freq += 1
self.key_freq_map[key] = freq + 1
self.freq_map[freq + 1][key] = value
return value
def put(self, key: int, value: int) -> None:
if self.capacity == 0:
return
if key in self.key_freq_map:
self.key_freq_map[key] = self.get(key)
self.freq_map[self.key_freq_map[key]][key] = value
else:
if len(self.key_freq_map) == self.capacity:
k, v = self.freq_map[self.min_freq].popitem(last=False)
del self.key_freq_map[k]
self.key_freq_map[key] = 1
self.freq_map[1][key] = value
self.min_freq = 1The OrderedDict solution keeps track of keys and their frequencies in separate dictionaries. key_freq_map maps the key to its frequency, while freq_map has OrderedDicts keyed by frequency with keys as their values. This way, we can update both frequency and recency of accesses.
With the built-in nature of Python's OrderedDict, the implementation remains concise and takes advantage of existing functionality to manage ordering effectively, even if all operations might not run in strict O(1) time.
Time Complexity: Average O(1) for both get and put, due to the effectiveness of OrderedDict for these operations.
Space Complexity: O(capacity) for storing nodes and their frequency mappings.
Approach 3: Default Approach
class LFUCache {
private final Map<Integer, Node> map;
private final Map<Integer, DoublyLinkedList> freqMap;
private final int capacity;
private int minFreq;
public LFUCache(int capacity) {
this.capacity = capacity;
map = new HashMap<>(capacity, 1);
freqMap = new HashMap<>();
}
public int get(int key) {
if (capacity == 0) {
return -1;
}
if (!map.containsKey(key)) {
return -1;
}
Node node = map.get(key);
incrFreq(node);
return node.value;
}
public void put(int key, int value) {
if (capacity == 0) {
return;
}
if (map.containsKey(key)) {
Node node = map.get(key);
node.value = value;
incrFreq(node);
return;
}
if (map.size() == capacity) {
DoublyLinkedList list = freqMap.get(minFreq);
map.remove(list.removeLast().key);
}
Node node = new Node(key, value);
addNode(node);
map.put(key, node);
minFreq = 1;
}
private void incrFreq(Node node) {
int freq = node.freq;
DoublyLinkedList list = freqMap.get(freq);
list.remove(node);
if (list.isEmpty()) {
freqMap.remove(freq);
if (freq == minFreq) {
minFreq++;
}
}
node.freq++;
addNode(node);
}
private void addNode(Node node) {
int freq = node.freq;
DoublyLinkedList list = freqMap.getOrDefault(freq, new DoublyLinkedList());
list.addFirst(node);
freqMap.put(freq, list);
}
private static class Node {
int key;
int value;
int freq;
Node prev;
Node next;
Node(int key, int value) {
this.key = key;
this.value = value;
this.freq = 1;
}
}
private static class DoublyLinkedList {
private final Node head;
private final Node tail;
public DoublyLinkedList() {
head = new Node(-1, -1);
tail = new Node(-1, -1);
head.next = tail;
tail.prev = head;
}
public void addFirst(Node node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
public Node remove(Node node) {
node.next.prev = node.prev;
node.prev.next = node.next;
node.next = null;
node.prev = null;
return node;
}
public Node removeLast() {
return remove(tail.prev);
}
public boolean isEmpty() {
return head.next == tail;
}
}
}class Node {
public:
int key;
int value;
int freq;
Node* prev;
Node* next;
Node(int key, int value) {
this->key = key;
this->value = value;
this->freq = 1;
this->prev = nullptr;
this->next = nullptr;
}
};
class DoublyLinkedList {
public:
Node* head;
Node* tail;
DoublyLinkedList() {
this->head = new Node(-1, -1);
this->tail = new Node(-1, -1);
this->head->next = this->tail;
this->tail->prev = this->head;
}
void addFirst(Node* node) {
node->prev = this->head;
node->next = this->head->next;
this->head->next->prev = node;
this->head->next = node;
}
Node* remove(Node* node) {
node->next->prev = node->prev;
node->prev->next = node->next;
node->next = nullptr;
node->prev = nullptr;
return node;
}
Node* removeLast() {
return remove(this->tail->prev);
}
bool isEmpty() {
return this->head->next == this->tail;
}
};
class LFUCache {
public:
LFUCache(int capacity) {
this->capacity = capacity;
this->minFreq = 0;
}
int get(int key) {
if (capacity == 0 || map.find(key) == map.end()) {
return -1;
}
Node* node = map[key];
incrFreq(node);
return node->value;
}
void put(int key, int value) {
if (capacity == 0) {
return;
}
if (map.find(key) != map.end()) {
Node* node = map[key];
node->value = value;
incrFreq(node);
return;
}
if (map.size() == capacity) {
DoublyLinkedList* list = freqMap[minFreq];
Node* node = list->removeLast();
map.erase(node->key);
}
Node* node = new Node(key, value);
addNode(node);
map[key] = node;
minFreq = 1;
}
private:
int capacity;
int minFreq;
unordered_map<int, Node*> map;
unordered_map<int, DoublyLinkedList*> freqMap;
void incrFreq(Node* node) {
int freq = node->freq;
DoublyLinkedList* list = freqMap[freq];
list->remove(node);
if (list->isEmpty()) {
freqMap.erase(freq);
if (freq == minFreq) {
minFreq++;
}
}
node->freq++;
addNode(node);
}
void addNode(Node* node) {
int freq = node->freq;
if (freqMap.find(freq) == freqMap.end()) {
freqMap[freq] = new DoublyLinkedList();
}
DoublyLinkedList* list = freqMap[freq];
list->addFirst(node);
freqMap[freq] = list;
}
};
/**
* Your LFUCache object will be instantiated and called as such:
* LFUCache* obj = new LFUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/type LFUCache struct {
cache map[int]*node
freqMap map[int]*list
minFreq int
capacity int
}
func Constructor(capacity int) LFUCache {
return LFUCache{
cache: make(map[int]*node),
freqMap: make(map[int]*list),
capacity: capacity,
}
}
func (this *LFUCache) Get(key int) int {
if this.capacity == 0 {
return -1
}
n, ok := this.cache[key]
if !ok {
return -1
}
this.incrFreq(n)
return n.val
}
func (this *LFUCache) Put(key int, value int) {
if this.capacity == 0 {
return
}
n, ok := this.cache[key]
if ok {
n.val = value
this.incrFreq(n)
return
}
if len(this.cache) == this.capacity {
l := this.freqMap[this.minFreq]
delete(this.cache, l.removeBack().key)
}
n = &node{key: key, val: value, freq: 1}
this.addNode(n)
this.cache[key] = n
this.minFreq = 1
}
func (this *LFUCache) incrFreq(n *node) {
l := this.freqMap[n.freq]
l.remove(n)
if l.empty() {
delete(this.freqMap, n.freq)
if n.freq == this.minFreq {
this.minFreq++
}
}
n.freq++
this.addNode(n)
}
func (this *LFUCache) addNode(n *node) {
l, ok := this.freqMap[n.freq]
if !ok {
l = newList()
this.freqMap[n.freq] = l
}
l.pushFront(n)
}
type node struct {
key int
val int
freq int
prev *node
next *node
}
type list struct {
head *node
tail *node
}
func newList() *list {
head := new(node)
tail := new(node)
head.next = tail
tail.prev = head
return &list{
head: head,
tail: tail,
}
}
func (l *list) pushFront(n *node) {
n.prev = l.head
n.next = l.head.next
l.head.next.prev = n
l.head.next = n
}
func (l *list) remove(n *node) {
n.prev.next = n.next
n.next.prev = n.prev
n.next = nil
n.prev = nil
}
func (l *list) removeBack() *node {
n := l.tail.prev
l.remove(n)
return n
}
func (l *list) empty() bool {
return l.head.next == l.tail
}use std::cell::RefCell;
use std::collections::HashMap;
use std::rc::Rc;
struct Node {
key: i32,
value: i32,
freq: i32,
prev: Option<Rc<RefCell<Node>>>,
next: Option<Rc<RefCell<Node>>>,
}
impl Node {
fn new(key: i32, value: i32) -> Self {
Self {
key,
value,
freq: 1,
prev: None,
next: None,
}
}
}
struct LinkedList {
head: Option<Rc<RefCell<Node>>>,
tail: Option<Rc<RefCell<Node>>>,
}
impl LinkedList {
fn new() -> Self {
Self {
head: None,
tail: None,
}
}
fn push_front(&mut self, node: &Rc<RefCell<Node>>) {
match self.head.take() {
Some(head) => {
head.borrow_mut().prev = Some(Rc::clone(node));
node.borrow_mut().prev = None;
node.borrow_mut().next = Some(head);
self.head = Some(Rc::clone(node));
}
None => {
node.borrow_mut().prev = None;
node.borrow_mut().next = None;
self.head = Some(Rc::clone(node));
self.tail = Some(Rc::clone(node));
}
};
}
fn remove(&mut self, node: &Rc<RefCell<Node>>) {
match (node.borrow().prev.as_ref(), node.borrow().next.as_ref()) {
(None, None) => {
self.head = None;
self.tail = None;
}
(None, Some(next)) => {
self.head = Some(Rc::clone(next));
next.borrow_mut().prev = None;
}
(Some(prev), None) => {
self.tail = Some(Rc::clone(prev));
prev.borrow_mut().next = None;
}
(Some(prev), Some(next)) => {
next.borrow_mut().prev = Some(Rc::clone(prev));
prev.borrow_mut().next = Some(Rc::clone(next));
}
};
}
fn pop_back(&mut self) -> Option<Rc<RefCell<Node>>> {
match self.tail.take() {
Some(tail) => {
self.remove(&tail);
Some(tail)
}
None => None,
}
}
fn is_empty(&self) -> bool {
self.head.is_none()
}
}
struct LFUCache {
cache: HashMap<i32, Rc<RefCell<Node>>>,
freq_map: HashMap<i32, LinkedList>,
min_freq: i32,
capacity: usize,
}
/**
* `&self` means the method takes an immutable reference.
* If you need a mutable reference, change it to `&mut self` instead.
*/
impl LFUCache {
fn new(capacity: i32) -> Self {
Self {
cache: HashMap::new(),
freq_map: HashMap::new(),
min_freq: 0,
capacity: capacity as usize,
}
}
fn get(&mut self, key: i32) -> i32 {
if self.capacity == 0 {
return -1;
}
match self.cache.get(&key) {
Some(node) => {
let node = Rc::clone(node);
self.incr_freq(&node);
let value = node.borrow().value;
value
}
None => -1,
}
}
fn put(&mut self, key: i32, value: i32) {
if self.capacity == 0 {
return;
}
match self.cache.get(&key) {
Some(node) => {
let node = Rc::clone(node);
node.borrow_mut().value = value;
self.incr_freq(&node);
}
None => {
if self.cache.len() == self.capacity {
let list = self.freq_map.get_mut(&self.min_freq).unwrap();
self.cache.remove(&list.pop_back().unwrap().borrow().key);
}
let node = Rc::new(RefCell::new(Node::new(key, value)));
self.add_node(&node);
self.cache.insert(key, node);
self.min_freq = 1;
}
};
}
fn incr_freq(&mut self, node: &Rc<RefCell<Node>>) {
let freq = node.borrow().freq;
let list = self.freq_map.get_mut(&freq).unwrap();
list.remove(node);
if list.is_empty() {
self.freq_map.remove(&freq);
if freq == self.min_freq {
self.min_freq += 1;
}
}
node.borrow_mut().freq += 1;
self.add_node(node);
}
fn add_node(&mut self, node: &Rc<RefCell<Node>>) {
let freq = node.borrow().freq;
match self.freq_map.get_mut(&freq) {
Some(list) => {
list.push_front(node);
}
None => {
let mut list = LinkedList::new();
list.push_front(node);
self.freq_map.insert(node.borrow().freq, list);
}
};
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| HashMap and Double Linked List Approach | Time Complexity: |
| OrderedDict Based Approach | Time Complexity: Average |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap + Frequency Doubly Linked Lists | O(1) for get and put | O(n) | Standard optimal solution for LFU cache design problems and interviews |
| Frequency Map + OrderedDict (Python) | O(1) average | O(n) | Python implementations where built-in ordered dictionaries simplify LRU handling |
| Naive Frequency Tracking | O(n) eviction | O(n) | Conceptual baseline; scan keys to find the least frequently used item |
Frequently asked questions
Is LFU Cache easy or hard?
LFU Cache is classified as a hard problem because it requires designing multiple interacting data structures. The challenge is maintaining both frequency counts and recency order while guaranteeing O(1) operations for get and put.
How to solve LFU Cache in O(1)?
Use two hash maps and frequency-linked lists. One map stores key → node for direct access, and another maps frequency → doubly linked list of nodes with that frequency. On every access, remove the node from its current list, increase its frequency, and insert it into the next list. Eviction removes the least recently used node from the minimum-frequency list.
LFU Cache Python or Java solution
Python solutions often use dictionaries and OrderedDict to track frequency buckets efficiently. Java implementations typically combine HashMap with custom doubly linked list nodes to maintain constant-time insertion and removal. Both approaches implement O(1) get and put operations.
What is the best approach for LFU Cache?
The best approach uses a hash map combined with frequency-based doubly linked lists. A map provides O(1) access to nodes, while lists grouped by frequency maintain recency order for ties. Tracking the minimum frequency allows constant-time eviction. This design keeps both get and put operations O(1).
Is LFU Cache asked at Google Amazon Meta?
LFU Cache is a common hard-level system design style data structure problem. Variants have appeared in interviews at companies such as Google, Amazon, Meta, and Microsoft because it tests hash maps, linked lists, and constant-time data structure design.
What data structure is used in LFU Cache?
The standard implementation uses a hash table combined with doubly linked lists grouped by frequency. The hash map provides O(1) key lookup, while each doubly linked list maintains recency order among keys with the same frequency. Some Python solutions replace custom lists with OrderedDict.
What is the time complexity of LFU Cache?
The optimal LFU cache implementation runs get and put operations in O(1) time. This is achieved using a hash table for key lookups and doubly linked lists to maintain ordering within each frequency bucket. Space complexity is O(n) because every cached key must be stored along with frequency metadata.