The O(n) Club: LFU Cache: How to Get Unpopular Fast (and Still Write O(1) Java)

The O(n) Club: LFU Cache — How to Get Unpopular Fast (and Still Write O(1) Java)

⚡ TL;DR

LFU (Least Frequently Used) Cache is basically a popularity contest where your keys better show up or get tossed. When full, the least-used item is shown the door. If there’s a tie, the least-recently-used (LRU) among the unpopular gets evicted. Achieving O(1) updates? It’s all about clever Java maps and double-linked lists, not wishful thinking.

// Skeleton LFU structure
class LFUCache {
    public int get(int key) { /*...*/ }
    public void put(int key, int value) { /*...*/ }
    // Uses: key→node, freq→list, minFreq
}

🧠 How Devs Usually Mess This Up

Many folks mix up LFU with LRU. LFU checks how often you use stuff, not just when you last did. Rookie error: people think putting a new key is free. Nope—add a new key at capacity, and someone else gets evicted instantly (even new guys aren’t safe if there’s no space). Also: both get() and put() must bump frequency, or your eviction is hopelessly unfair. And trying to do it all with one map? Who hasn’t shot themselves in the foot with O(n) lookups?

🔍 What’s Actually Going On

Imagine your cache as a grim nightclub. Each frequency is its own table—a bucket. Keys (party guests) get promoted to fancier tables as they rack up visits (accesses). Not popular? Last in, last out. Tiebreakers ruthlessly evict whoever’s napping longest. You want:

• key → node map for lightning lookups and updates
• freq → linked list for instant tiebreaker finding (LRU style!)
• minFreq tracker so you know which bucket to start the eviction process

Done right, all your crucial ops are O(1)—unless you lose track of the tables, in which case enjoy dragging your runtime through the mud.

🛠️ PseudoCode

• get(key):
  • If key is missing: return -1—don’t even try to save face.
  • If found: remove node from current freq list, add to next freq’s list, bump freq. Update minFreq if needed.
  • Return value.

  if (!keyToNode.containsKey(key)) return -1;
  Node node = keyToNode.get(key);
  updateFrequency(node);
  return node.value;

• put(key, value):
  • If capacity is zero: return (not even the velvet rope will help).
  • If key exists: update its value, bump freq like get().
  • If full: evict the LRU key from the min frequency bucket and make space.
  • Add new node at frequency 1, set minFreq to 1.

  if (capacity == 0) return;
  if (keyToNode.containsKey(key)) { /* update and bump */ }
  if (keyToNode.size() == capacity) { /* evict least */ }
  addNewNode(key, value);
  minFreq = 1;

• Clean up: Delete empty freq lists as you go!

💻 The Code

// Java LFU Cache (semi-complete version)
class LFUCache {
    class Node {
        int key, value, freq;
        Node prev, next;
        Node(int k, int v) { key = k; value = v; freq = 1; }
    }
    int capacity, minFreq;
    Map<integer node> keyToNode = new HashMap<>();
    Map<integer doublylinkedlist> freqToList = new HashMap<>();
    
    public LFUCache(int capacity) {
        this.capacity = capacity;
        minFreq = 0;
    }
    public int get(int key) {
        if (!keyToNode.containsKey(key)) return -1;
        Node node = keyToNode.get(key);
        update(node);
        return node.value;
    }
    public void put(int key, int value) {
        if (capacity == 0) return;
        if (keyToNode.containsKey(key)) {
            Node node = keyToNode.get(key);
            node.value = value;
            update(node);
            return;
        }
        if (keyToNode.size() == capacity) {
            DoublyLinkedList list = freqToList.get(minFreq);
            Node lru = list.removeTail();
            keyToNode.remove(lru.key);
        }
        Node node = new Node(key, value);
        keyToNode.put(key, node);
        freqToList.computeIfAbsent(1, f -> new DoublyLinkedList()).addHead(node);
        minFreq = 1;
    }
    private void update(Node node) {
        int freq = node.freq;
        DoublyLinkedList list = freqToList.get(freq);
        list.remove(node);
        if (freq == minFreq && list.isEmpty()) minFreq++;
        node.freq++;
        freqToList.computeIfAbsent(node.freq, f -> new DoublyLinkedList()).addHead(node);
    }
    class DoublyLinkedList {
        Node head = new Node(-1, -1), tail = new Node(-1, -1);
        DoublyLinkedList() {
            head.next = tail; tail.prev = head;
        }
        void addHead(Node n) {
            n.next = head.next; n.prev = head;
            head.next.prev = n; head.next = n;
        }
        void remove(Node n) {
            n.prev.next = n.next; n.next.prev = n.prev;
        }
        Node removeTail() {
            if (tail.prev == head) return null;
            Node last = tail.prev;
            remove(last);
            return last;
        }
        boolean isEmpty() {
            return head.next == tail;
        }
    }
}</integer></integer>

⚠️ Pitfalls, Traps & Runtime Smacks

• LRU tie-breaker: Don’t skip this or your cache will pick victims at random. Nobody wants surprise sackings (well, except maybe Product).
• Frequency Bloat: Without “aging” counters, some keys get immortal. Good for vampires, bad for caches.
• Zero Capacity: If your boss gives you a cache of size 0, just return everything with a straight face and pray you get a raise.
• Forget double-layered maps? Enjoy O(n) time, and a follow-up interview at 9am.

🧠 Interviewer Brain-Tattoo

“LFU cares how many parties you attend, not just how late you rock up. O(1) speed? That’s you, the accountant, not a magician.”