LRU Cache (Hash Map + Doubly Linked List)
Language:
Systems & Distributed AlgorithmsTime: O(1) Get and PutSpace: O(Capacity)

LRU Cache (Hash Map + Doubly Linked List)

Standard Technical Benchmark Problem: Design LRU Cache (LeetCode 146)

Algorithmic Concept & Core Invariant

Combine a Hash Map for O(1) key lookups with a Doubly-Linked List to maintain recency order. Access moves a node to MRU (head); eviction removes LRU (tail) in true O(1) time without array shifting.

Try Custom Input: Operations (put k=v, get k) | Cap

Comma operations followed by | capacity (1–4)

Interactive Trace: Step 1 / 4
Operation: put(1, 10)Capacity: 2 items
Head (MRU) ➔
Node [1]Val: 10
➔ Tail (LRU)
State Watch:op=put(1, 10)
ACTIONput(1, 10) -> Cache size 1/2. Item [1:10] inserted at Head (MRU).
JavaScript Reference ImplementationZero third-party dependencies
class Node {
  constructor(key = 0, val = 0) {
    this.key = key;
    this.val = val;
    this.prev = null;
    this.next = null;
  }
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
    this.head = new Node();
    this.tail = new Node();
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  _remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  _add(node) {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next.prev = node;
    this.head.next = node;
  }

  get(key) {
    if (!this.cache.has(key)) return -1;
    const node = this.cache.get(key);
    this._remove(node);
    this._add(node);
    return node.val;
  }

  put(key, value) {
    if (this.cache.has(key)) {
      this._remove(this.cache.get(key));
    }
    const node = new Node(key, value);
    this.cache.set(key, node);
    this._add(node);

    if (this.cache.size > this.capacity) {
      const lru = this.tail.prev;
      this._remove(lru);
      this.cache.delete(lru.key);
    }
  }
}
Real-World Production Infrastructure Usage

Redis memory eviction policies, browser image/font memory cache, and database buffer pool managers.

Algorithm Engineering & Interview Notes

Deep-Dive Guide: Mastering LRU Cache (Hash Map + Doubly Linked List) for Technical Interviews

LRU Cache (Hash Map + Doubly Linked List) is one of the highest-frequency building blocks in coding interviews—most famously benchmarked via "Design LRU Cache (LeetCode 146)". Combine a Hash Map for O(1) key lookups with a Doubly-Linked List to maintain recency order. Access moves a node to MRU (head); eviction removes LRU (tail) in true O(1) time without array shifting.

From an asymptotic perspective, this pattern achieves O(1) Get and Put time complexity and O(Capacity) auxiliary space complexity. This bridges classic DSA and Senior System Design. AI will suggest libraries, but interviewers demand you demonstrate how Doubly-Linked List pointers allow true O(1) eviction without array shifting.

In production engineering, this exact technique powers real infrastructure: Redis memory eviction policies, browser image/font memory cache, and database buffer pool managers. Stepping through the live state trace and comparing both the JavaScript and Python 3 implementations above builds intuition for pointer bounds, loop termination conditions, and edge cases.

Interview Execution & Edge-Case Checklist

  • Verify the invariant before writing a loop: know exactly what every pointer, index, or auxiliary structure guarantees at each step of LRU Cache (Hash Map + Doubly Linked List).
  • Check language mutability rules: in JavaScript and Python, strings are immutable, so in-place character algorithms expect a mutable array (char[]) or list[str].
  • Trace small boundary cases manually (empty input, 1 element, 2 elements, duplicates) before declaring the solution complete.
  • Explain both Time (O(1) Get and Put) and Space (O(Capacity)) complexity clearly, including recursion stack or helper allocations.

Top 10 Frequently Asked Questions (Candidates & Hiring Companies)

1. Why does LRU Cache (Hash Map + Doubly Linked List) run in O(1) Get and Put time and O(Capacity) space?

Combine a Hash Map for O(1) key lookups with a Doubly-Linked List to maintain recency order. Access moves a node to MRU (head); eviction removes LRU (tail) in true O(1) time without array shifting. Each step makes monotonic progress toward termination without revisiting eliminated work, yielding O(1) Get and Put runtime while keeping extra working memory bounded to O(Capacity).

2. What is the classic benchmark problem used to test LRU Cache (Hash Map + Doubly Linked List) in interviews?

Interviewers frequently introduce this pattern through "Design LRU Cache (LeetCode 146)" (Systems & Distributed Algorithms), and then ask follow-ups testing boundary inputs, streaming data, or tighter space constraints.

3. What is the most common bug candidates make when implementing LRU Cache (Hash Map + Doubly Linked List)?

The top mistakes are off-by-one loop conditions (< vs <=), forgetting empty or single-element base cases, mutating immutable strings directly instead of working on an array/list, and missing state resets across iterations.

4. Where is LRU Cache (Hash Map + Doubly Linked List) used in real-world production software systems?

Beyond coding interviews, LRU Cache (Hash Map + Doubly Linked List) directly underlies production workloads such as: Redis memory eviction policies, browser image/font memory cache, and database buffer pool managers.

5. What follow-up constraints do senior interviewers add after solving Design LRU Cache (LeetCode 146)?

Expect interviewers to ask how your approach behaves if the input exceeds single-machine RAM, arrives as an unbounded stream, contains duplicate keys or Unicode multi-byte tokens, or must run concurrently without lock contention.

6. How do interviewers at Google, Amazon, Meta, and Microsoft grade DSA solutions?

Hiring committees grade four independent signals: (1) clarifying ambiguous constraints and edge cases before coding, (2) selecting an optimal pattern and stating exact Time and Space Big-O trade-offs, (3) writing clean bug-free JavaScript or Python code while narrating invariants, and (4) walking through a manual dry-run trace to catch off-by-one errors.

7. Should I code DSA interviews in Python or JavaScript?

Use whichever language you write most fluently under time pressure. Python offers concise tuple unpacking, heapq, collections.deque, and slicing—ideal for rapid LeetCode and data engineering screens. JavaScript is preferred for frontend and full-stack product loops, though remember JS has no built-in heap and strings are immutable just like in Python.

8. How do you identify which of the 24 DSA patterns applies within the first 2 minutes?

Look at input structure and constraints: sorted arrays or target pairs signal Two Pointers or Binary Search; contiguous subarray/substring bounds point to Sliding Window; parent-child or dependency hierarchies use DFS/BFS or Trie; top-K / streaming medians use Min-Heaps; and overlapping subproblems with optimal substructure require Memoization or Tabulation DP.

9. What edge cases do interviewers test on almost every DSA coding round?

Expect reviewers to test empty inputs ([] or ""), single-element inputs, duplicate keys, negative or zero values, already-sorted or reverse-sorted arrays, disconnected graphs or cycles, and maximum constraint bounds (e.g., N = 10^5 where O(N^2) times out).

10. Why do Staff interviews still ask core DSA patterns when AI coding tools exist?

AI can autocomplete syntax, but engineers still own asymptotic latency, memory footprints, and production failure modes. Knowing why O(1) space in-place mutation or O(log N) search matters prevents database timeouts, event-loop stalls, and unexpected cloud compute bills.

Explore All 24 Interactive DSA Patterns & Complexity Tools