LRU Cache

Free with account Updated Nov 19, 2026 · 6 min read
On this page

    Problem statement

    Design a cache with a fixed capacity that supports get(key) and put(key, value), both in O(1) average time. get returns the value or −1 if the key is missing. put inserts or updates a key; if that pushes the cache over capacity, it first removes the least recently used key. Both get and put count as a use.

    One of the most frequently asked design-style coding questions. It checks whether you can combine two data structures so that each covers the other's weakness. Original problem: LeetCode 146.

    Example

    With capacity 2, reading key 1 makes key 2 the least recently used, so putting key 3 evicts key 2.
    With capacity 2, reading key 1 makes key 2 the least recently used, so putting key 3 evicts key 2.
    LRUCache(2)
    put(1, A); put(2, B)
    get(1)     -> A        # order now: 1, 2
    put(3, C)              # evicts 2 (least recently used)
    get(2)     -> -1
    get(3)     -> C

    Constraints (assumed)

    • 1 ≤ capacity ≤ 3,000; up to 2 × 10⁵ calls.
    • Keys and values are integers.

    What this question tests

    • Recognizing that no single structure gives O(1) lookup and O(1) reordering.
    • Implementing a doubly linked list with sentinels without pointer bugs.
    • Keeping the map and the list consistent on every operation.

    Questions to ask first

    1. Does get count as a use? (Here: yes, it refreshes the key.)
    2. Does updating an existing key count as a use? (Here: yes.)
    3. Can I use the language's ordered map (Python OrderedDict, Java LinkedHashMap)? Many interviewers want it built by hand.
    4. Is it single-threaded? (Here: yes. Concurrency is a common follow-up.)