Amazon · Coding 4 of 5

LRU Cache

Build a fixed-size cache that evicts the least recently used key in O(1).

MediumDesignHash mapLinked listBest: O(1) per call time · O(capacity) space

Practice question: an editorial practice prompt, not a claim that Amazon asks this exact question. Interviews vary by role, level, team, and location.

Problem

Problem statement

Design a Least Recently Used (LRU) cache with a fixed positive capacity.

get(key) returns the value stored for key, or -1 if the key is absent. put(key, value) inserts the key or updates its value. When an insert pushes the cache over capacity, evict the least recently used key.

A successful get and any put both count as using that key. Both operations must run in O(1) average time.

Examples

Example 1
Input
capacity = 2
put(1, 1), put(2, 2), get(1),
put(3, 3), get(2), put(4, 4),
get(1), get(3), get(4)
Output
1, -1, -1, 3, 4

Why: The outputs are the five get results in order. get(1) makes key 1 the most recent, so put(3, 3) evicts key 2; then put(4, 4) evicts key 1.

Example 2
Input
capacity = 2
put(1, 1), put(2, 2), put(1, 10),
put(3, 3), get(1), get(2)
Output
10, -1

Why: Updating key 1 refreshes it, so key 2 is the one evicted.

Constraints

  • 1 ≤ capacity ≤ 3000
  • 0 ≤ key, value ≤ 10⁴
  • Up to 2 × 10⁵ calls to get and put.
In the interview

How to answer it out loud

What it tests: Combining data structures to meet a strict complexity target and maintaining invariants correctly.

  1. 1
    Clarify

    Confirm capacity behavior and the required O(1) get and put operations.

  2. 2
    Implement

    Combine a hash map with a doubly linked list so lookup, promotion, insertion, and eviction stay constant time.

  3. 3
    Verify

    Trace updates, repeated keys, capacity one, and eviction order; explain the list/map invariant.

Approaches

From brute force to the best solution

ApproachIdeaTimeSpace
List ordered by recencyKeep keys in an array; move a key to the end on every use.O(n) per callO(capacity)
Hash map + doubly linked listBestThe map finds a node in O(1); the list moves or evicts it in O(1).O(1) per callO(capacity)
Key insight

A hash map gives O(1) lookup but no order; a doubly linked list gives O(1) reordering but no lookup. Storing list nodes in the map gives you both.

Solution

Reference solution

Each version is self-contained and has been run against the examples and test cases on this page.

class Node:    __slots__ = ("key", "val", "prev", "next")​    def __init__(self, key=0, val=0):        self.key, self.val = key, val        self.prev = self.next = None​​class LRUCache:    def __init__(self, capacity: int):        self.capacity = capacity        self.nodes = {}                        # key -> Node        self.head, self.tail = Node(), Node()  # sentinels: head.next = LRU, tail.prev = MRU        self.head.next, self.tail.prev = self.tail, self.head​    def _remove(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._remove(node)        self._append(node)        return node.val​    def put(self, key: int, value: int) -> None:        node = self.nodes.get(key)        if node is not None:                   # update: refresh value and recency            node.val = value            self._remove(node)            self._append(node)            return        node = Node(key, value)        self.nodes[key] = node        self._append(node)        if len(self.nodes) > self.capacity:            lru = self.head.next            self._remove(lru)            del self.nodes[lru.key]
Time
O(1) per call
Space
O(capacity)
Approach
Hash map + doubly linked list
Test cases

Edge cases to run before you say “done”

InputExpectedWhy it matters
capacity = 1: put(1, 1), put(2, 2), get(1)-1Capacity one evicts on every new key.
capacity = 2: put(1, 1), put(1, 5), get(1)5Updating an existing key must not evict anything.
capacity = 2: put(1, 1), put(2, 2), get(1), put(3, 3), get(2)-1A get refreshes recency.
Likely follow-ups

Answer the main question first, then take these on one at a time:

  • Why is a doubly linked list needed?
  • How would you make it thread-safe?
  • What happens when capacity is zero?
Avoid these mistakes

Check your recording or written solution against this list:

  • Using an array that makes removal O(n)
  • Failing to update an existing key’s recency
  • Leaving evicted nodes in the map
Sources and methodology

This guide combines general interview-practice patterns with the public hiring material below. The practice prompt and coaching are PiriPiri AI editorial content, not official Amazon questions or answers.

Amazon: software development interview topics ↗Amazon: Leadership Principles ↗
Official sources reviewed 20 September 2026.