LRU Cache: Hash Map Plus Recency List Pattern

Learning Outcome

After this lesson, you should be able to combine direct lookup with a recency order structure.

Problem Statement

Design an LRUCache with get(key) and put(key,value). When capacity is exceeded, remove the least recently used key.

Brute Force Approach

Store pairs in an array and scan to find keys and update recency. This makes operations O(n).

Optimized Approach

Use a hash map for O(1) key lookup and a doubly linked list or ordered map to move touched keys to most recent position.

Exact Pseudocode

get(key):
  if key is missing:
    return -1
  move key to most recent position
  return value

put(key, value):
  if key exists:
    update value and move key to most recent
  else:
    add key as most recent
  if size is greater than capacity:
    remove least recent key
  

Reference Code

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)
  

Sample Dry Run

Complexity

Edge Cases

• Updating an existing key must refresh recency.
• get on a missing key should return -1 and not change the cache.
• Evict only after adding or updating causes size to exceed capacity.

Interview Checklist

• Use a map from key to node or iterator.
• Move every accessed key to most recent position.
• Evict from the least recent end, not the most recent end.

FAQs