Course4all
Join us on telegram
Home/dsa/Design/LFU Cache

LFU Cache

# System & Data Structure Design Design problems in DSA interviews test your ability to translate requirements into a functional, efficient, and maintainable class structure. Unlike standard algorithmic problems, the focus here is on **State Management** and **API Design**. ### Core Principles 1. **Encapsulation:** Keep data private and expose functionality through well-defined methods. 2. **Trade-offs:** Every design choice has a cost. Is it better to have $O(1)$ read and $O(N)$ write, or vice versa? 3. **State Consistency:** Ensure that your internal data structures (e.g., a Map and a List) stay in sync after every operation. ### Common Design Patterns #### 1. HashMap + Doubly Linked List (DLL) The "Gold Standard" for $O(1)$ caching (LRU/LFU). ```text [Head] <-> [Node A] <-> [Node B] <-> [Node C] <-> [Tail] ^ ^ ^ ^ ^ (MRU) (Data) (Data) (Data) (LRU) ``` - **HashMap:** Provides $O(1)$ lookups for keys to their corresponding nodes. - **DLL:** Provides $O(1)$ addition/removal of nodes at both ends, maintaining the order of access. #### 2. Amortized Analysis (Rebalancing) Commonly used in **Queue using Stacks** or **Dynamic Arrays**. - Instead of doing heavy work on every call, we batch it. Pushing to a stack is $O(1)$, and "flipping" elements to another stack happens only when necessary, averaging $O(1)$ per operation. #### 3. Ring Buffers (Circular Arrays) Used for fixed-size memory management (e.g., **Circular Queue**, **Hit Counter**). ```text [0] [1] [2] [3] [4] [5] ^ ^ ^ Head (Data) Tail (Pops) (Next Push) ``` - Use `(index + 1) % capacity` to wrap around the array. #### 4. Concurrency & Thread Safety For "Hard" design problems (e.g., **Bounded Blocking Queue**). - Use **Mutexes** (Locks) to prevent data races. - Use **Condition Variables** (`wait`/`notify`) to manage producer-consumer logic efficiently without busy-waiting. ### How to Approach a Design Problem 1. **Identify the API:** What methods do you need to implement? (`get`, `put`, `push`, etc.) 2. **Define the State:** What variables represent the current state? (Size, Capacity, Pointers). 3. **Choose the Data Structures:** Select the combination that minimizes time complexity for the most frequent operations. 4. **Dry Run:** Trace the state changes through a sequence of operations based on your chosen structure.

LFU Cache

Design a data structure that follows the constraints of a Least Frequently Used (LFU) cache.

Requirement

  1. get(key): Return value if exists, update frequency.
  2. put(key, value): Insert/update value. If at capacity, evict the least frequently used item. If there's a tie, evict the least recently used.
Hard

Examples

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]
Approach 1

Level I: Brute Force Scan

Intuition

Store entries in a List or Map. For every put at capacity, iterate through the entire collection to find the item with the minimum frequency and the oldest access time. This is O(N)O(N) per operation but extremely simple.

⏱ O(N) for get and put.💾 O(Capacity).

Detailed Dry Run

Cache: {(A, f:2, t:1), (B, f:1, t:2)}. Put(C) evicts B because its frequency (1) is lower than A (2).

java
class LFUCache {
    class Node { int k, v, f, t; Node(int k, int v, int f, int t){this.k=k;this.v=v;this.f=f;this.t=t;} }
    Map<Integer, Node> map = new HashMap<>(); int cap, time = 0;
    public LFUCache(int c) { cap = c; }
    public int get(int key) {
        if(!map.containsKey(key)) return -1;
        Node n = map.get(key); n.f++; n.t = ++time; return n.v;
    }
    public void put(int key, int value) {
        if(cap <= 0) return;
        if(map.containsKey(key)) { Node n = map.get(key); n.v = value; n.f++; n.t = ++time; }
        else {
            if(map.size() == cap) {
                int minF = Integer.MAX_VALUE, minT = Integer.MAX_VALUE, remK = -1;
                for(Node n : map.values()) if(n.f < minF || (n.f == minF && n.t < minT)) { minF = n.f; minT = n.t; remK = n.k; }
                map.remove(remK);
            }
            map.put(key, new Node(key, value, 1, ++time));
        }
    }
}
Approach 2

Level II: Priority Queue (O(log N))

Intuition

Use a PriorityQueue to store entries sorted by frequency, and then by access time (tie-breaker). While push and pop are O(logN)O(log N), it is simpler to implement than the O(1)O(1) DLL version.

⏱ O(log N) for get and put.💾 O(Capacity).
java
class LFUCache {
    class Node implements Comparable<Node> {
        int key, val, freq, time;
        Node(int k, int v, int f, int t) { key = k; val = v; freq = f; time = t; }
        public int compareTo(Node o) {
            return freq == o.freq ? time - o.time : freq - o.freq;
        }
    }
    Map<Integer, Node> map = new HashMap<>();
    PriorityQueue<Node> pq = new PriorityQueue<>();
    int cap, timer;
    public LFUCache(int capacity) { cap = capacity; }
    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        pq.remove(node); node.freq++; node.time = ++timer;
        pq.add(node); return node.val;
    }
    public void put(int key, int value) {
        if (cap <= 0) return;
        if (map.containsKey(key)) {
            Node node = map.get(key); pq.remove(node);
            node.val = value; node.freq++; node.time = ++timer;
            pq.add(node);
        } else {
            if (map.size() == cap) { Node rem = pq.poll(); map.remove(rem.key); }
            Node node = new Node(key, value, 1, ++timer);
            map.put(key, node); pq.add(node);
        }
    }
}
Approach 3

Level III: Map Frequency to Doubly Linked List

Intuition

Maintain a minFreq variable. Use one map for key -> node and another for freq -> DLL of nodes. When a key is accessed, move it from count DLL to count+1 DLL. If count DLL becomes empty and count == minFreq, increment minFreq. Eviction happens at freqMap[minFreq].tail.prev.

⏱ O(1) for all operations.💾 O(Capacity).
java
class LFUCache {
    class Node {
        int key, val, cnt;
        Node prev, next;
        Node(int k, int v) { key = k; val = v; cnt = 1; }
    }
    class DLL {
        Node head, tail; int size;
        DLL() { head = new Node(0, 0); tail = new Node(0, 0); head.next = tail; tail.prev = head; }
        void add(Node node) { node.next = head.next; head.next.prev = node; head.next = node; node.prev = head; size++; }
        void remove(Node node) { node.prev.next = node.next; node.next.prev = node.prev; size--; }
    }
    Map<Integer, Node> map = new HashMap<>();
    Map<Integer, DLL> freqMap = new HashMap<>();
    int cap, minFreq, size;
    public LFUCache(int capacity) { cap = capacity; }
    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        update(node);
        return node.val;
    }
    public void put(int key, int value) {
        if (cap == 0) return;
        if (map.containsKey(key)) {
            Node node = map.get(key); node.val = value; update(node);
        } else {
            if (size == cap) {
                DLL minList = freqMap.get(minFreq);
                map.remove(minList.tail.prev.key);
                minList.remove(minList.tail.prev);
                size--;
            }
            Node node = new Node(key, value);
            map.put(key, node);
            DLL list = freqMap.getOrDefault(1, new DLL());
            list.add(node); freqMap.put(1, list);
            minFreq = 1; size++;
        }
    }
    private void update(Node node) {
        DLL oldList = freqMap.get(node.cnt);
        oldList.remove(node);
        if (node.cnt == minFreq && oldList.size == 0) minFreq++;
        node.cnt++;
        DLL newList = freqMap.getOrDefault(node.cnt, new DLL());
        newList.add(node); freqMap.put(node.cnt, newList);
    }
}
← Previous QuestionDesign Snake Game
Next Question →Insert Delete GetRandom O(1) - Duplicates allowed