DSA DSA In Depth
0%
From-Scratch Build

O(1) LRU and Frequency-Bucketed LFU Cache Engine

Strict O(1) LRU and Shah-Mitra-Matani frequency-bucketed LFU caches built over sentinel-guarded intrusive doubly linked lists with zero heap-log overhead.

~35 min Advanced Lessons: Build Lab: O(1) LRU and Frequency-Bucketed LFU Cache Engine, Composing Hash Maps + Doubly Linked Lists: O(1) LRU & LFU Caches, Singly, Doubly & Intrusive Linked Lists (Linux Kernel list_head), Production Case Study: Redis ZSET (Listpack vs SkipList + Dict Dual Indexing), Collision Resolution: Separate Chaining vs Linear/Quadratic/Double Probing, Amortized Analysis: Aggregate, Banker's & Physicist's Potential (Φ)
Interactive Build Lab 0/4 Steps Completed

Code & Verify in the Browser Workbench

Complete 4 progressive engineering steps in JavaScript or TypeScript against an in-browser Node.js v22 runtime (virtual filesystem, loopback TCP/HTTP, and automated unit tests) — zero local setup required.

Overview

Strict O(1) LRU and Shah-Mitra-Matani frequency-bucketed LFU caches built over sentinel-guarded intrusive doubly linked lists with zero heap-log overhead.

Guided Implementation Walkthrough (4 Progressive Steps)

Step 1: Sentinel-Guarded Intrusive Doubly Linked List

  • Core Mechanical Concept: Eliminating Null Checks with Dummy Head and Tail Sentinels
  • Target Module: index.js (DoublyLinkedList.addFront / DoublyLinkedList.remove)
  • Engineering Specification: Implement addFront(node) and remove(node) on DoublyLinkedList. Because this.head and this.tail are permanent dummy sentinel nodes, every real node always has non-null node.prev and node.next. addFront splices node between head and head.next; remove links node.prev.next = node.next and node.next.prev = node.prev.
  • Verification Invariant: splices and unlinks nodes in O(1) using sentinel head and tail

Step 2: O(1) LRU Cache via Hash Map + Recency List

  • Core Mechanical Concept: Composing Hash Lookups with Intrusive List Promotion
  • Target Module: index.js (LRUCache.get / LRUCache.put)
  • Engineering Specification: Implement get(key) and put(key, value) on LRUCache. - Most recently used node sits at list.head.next; least recently used sits at list.tail.prev. - On get(key): unlink node and addFront(node). - On put(key, value): if map.size === capacity, evict list.popBack() and delete its key from map.
  • Verification Invariant: evicts least-recently-used key in O(1) time

Step 3: Frequency Bucket Promotion & minFreq Invariant

  • Core Mechanical Concept: Shah-Mitra-Matani O(1) Frequency Bucket Advancement
  • Target Module: index.js (LFUCache._promote)
  • Engineering Specification: Implement _promote(node) on LFUCache. When node moves from oldFreq to oldFreq + 1, remove it from buckets.get(oldFreq). If that bucket becomes empty and this.minFreq === oldFreq, increment this.minFreq = oldFreq + 1. Then insert node at the front of buckets.get(oldFreq + 1).
  • Verification Invariant: advances minFreq exactly when the minimum frequency bucket empties

Step 4: LFU Insertion & Tie-Breaking LRU Eviction

  • Core Mechanical Concept: Evicting Tail of buckets[minFreq] & Resetting minFreq = 1
  • Target Module: index.js (LFUCache.put)
  • Engineering Specification: Implement put(key, value) on LFUCache. 1. If key exists, update node.value = value and call this._promote(node). 2. If at capacity, pop the LRU victim from this.buckets.get(this.minFreq).popBack() and delete it from this.nodes. 3. Insert the new node into bucket 1 and set this.minFreq = 1.
  • Verification Invariant: evicts lowest-frequency key and breaks ties by least-recently-used order

Asymptotic & Memory Layout Guarantees

  • Category: Linked Structures & Caching
  • Difficulty: Advanced (~35 minutes)
  • Key Architectural Highlights:
    • Sentinel-guarded doubly linked list eliminating null-pointer branches
    • Shah-Mitra-Matani O(1) LFU cache with frequency-bucketed LRU tie-breaking
    • Exact minFreq invariant maintenance across hits, promotions, and evictions
  • Tags & Primitives: LFU Cache, LRU Cache, Intrusive Linked List, O(1) Eviction, Frequency Buckets

Production Systems Context & Verification

This from-scratch implementation is engineered with zero external dependencies and deterministic verification harnesses. Every internal invariant—from pointer restoration and bitmask addressing to amortized potential bounds and tree height balance—is asserted directly in test.js. Use the interactive browser workbench above to complete the guided steps in Guided Lab mode or inspect and benchmark the complete reference architecture in Full Solution mode.