LRU Cache: Design and Code in Python and TypeScript

The Problem

Design a cache with a fixed capacity and two operations. get(key) returns the value if the key is present, otherwise -1. put(key, value) inserts or updates the key. Both operations count as "using" the key. When a put would take the cache over capacity, remove the least recently used key first. Both operations must run in constant time on average.

Example 1

Capacity 2. put(1, 10), put(2, 20), get(1) returns 10 and makes key 1 the most recent. put(3, 30) now evicts key 2, so get(2) returns -1.

Example 2

Capacity 1. put(1, 1), then put(2, 2) evicts key 1 immediately. get(1) returns -1 and get(2) returns 2.

Assumptions to confirm

• Does updating an existing key count as a use? Normally yes.
• Is capacity always at least 1?
• May you use your language's ordered map, or does the interviewer want the linked list built by hand? Ask. Many expect you to build it.

The Naive Approach

A plain hash map gives O(1) lookups but no idea of order. Adding a timestamp to each entry and scanning for the oldest on eviction makes put O(n). Keeping keys in an array or list ordered by use makes moving a key to the front O(n). Say this out loud: the problem is that you need fast lookup and fast reordering at the same time, and no single basic structure gives you both.

The Optimal Design: Hash Map Plus Doubly Linked List

Python and TypeScript Solutions

Python, with OrderedDict

OrderedDict is a hash map that remembers order and can move a key to the end in O(1), so it is the shortest correct answer.

from collections import OrderedDict


class LRUCache:
    def __init__(self, capacity: int) -> None:
        self.capacity = capacity
        self.items: OrderedDict[int, int] = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.items:
            return -1
        self.items.move_to_end(key)          # now the most recently used
        return self.items[key]

    def put(self, key: int, value: int) -> None:
        if key in self.items:
            self.items.move_to_end(key)
        self.items[key] = value
        if len(self.items) > self.capacity:
            self.items.popitem(last=False)   # evict the least recently used

Python, built by hand

If the interviewer rules out OrderedDict, this is the hash map plus doubly linked list version.

class Node:
    def __init__(self, key: int = 0, value: int = 0) -> None:
        self.key, self.value = key, value
        self.prev: "Node | None" = None
        self.next: "Node | None" = None


class LRUCacheManual:
    """Hash map + doubly linked list, for when the interviewer says 'no OrderedDict'."""

    def __init__(self, capacity: int) -> None:
        self.capacity = capacity
        self.nodes: dict[int, Node] = {}
        self.head, self.tail = Node(), Node()   # sentinels: head.next is the LRU item
        self.head.next, self.tail.prev = self.tail, self.head

    def _unlink(self, node: Node) -> None:
        node.prev.next, node.next.prev = node.next, node.prev

    def _append(self, node: Node) -> None:      # insert just before tail (most recent)
        node.prev, node.next = self.tail.prev, self.tail
        self.tail.prev.next = node
        self.tail.prev = node

    def get(self, key: int) -> int:
        node = self.nodes.get(key)
        if node is None:
            return -1
        self._unlink(node)
        self._append(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key in self.nodes:
            self._unlink(self.nodes[key])
        node = Node(key, value)
        self.nodes[key] = node
        self._append(node)
        if len(self.nodes) > self.capacity:
            lru = self.head.next
            self._unlink(lru)
            del self.nodes[lru.key]

TypeScript

A JavaScript Map iterates keys in insertion order, so deleting and re-inserting a key moves it to the most recent end, and the first key is always the least recently used.

class LRUCache {
  private items = new Map<number, number>();
  private capacity: number;

  constructor(capacity: number) {
    this.capacity = capacity;
  }

  get(key: number): number {
    if (!this.items.has(key)) return -1;
    const value = this.items.get(key)!;
    this.items.delete(key); // re-insert so it becomes the most recently used
    this.items.set(key, value);
    return value;
  }

  put(key: number, value: number): void {
    this.items.delete(key);
    this.items.set(key, value);
    if (this.items.size > this.capacity) {
      // A Map iterates in insertion order, so the first key is the least recently used.
      const lru = this.items.keys().next().value as number;
      this.items.delete(lru);
    }
  }
}

Complexity Compared

How to Talk Through It in an Interview

1. Clarify: "Both get and put count as use? Capacity is at least 1? Can I use an ordered map, or should I build the list?"
2. Naive: "A hash map alone can't tell me which key is oldest without a scan, and a list alone can't find a key without a scan."
3. Design: "So I combine them: the map finds the node, the doubly linked list keeps usage order, and both operations are O(1)."
4. Code: write the two helpers first, unlink and append, then get and put on top of them. Mention the sentinels and why each node stores its key.
5. Test: walk through the capacity 2 example, then capacity 1, then updating an existing key.

Edge Cases and Follow-Ups

Practise It in a Mock Coding Round

Reading a solution is not the same as producing it with someone watching. In a real round you have to clarify the problem, say the brute force out loud, and keep talking while you type. MockIF runs coding rounds with a voice AI interviewer in a real in-browser editor, in Python and TypeScript. It runs your code against tests, asks you to explain your approach, follows up on edge cases and complexity, then scores the round and gives you specific feedback. A session costs 2 credits. It is free to start with 5 credits, then monthly or 3-monthly plans, or one-off credit packs (see pricing). Read more about how a mock coding interview works.

Frequently Asked Questions