{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

LRU Cache – Solution & Complexity

Interview solutions
/
LRU Cache

Watch: LRU Cache with a hash map and a doubly linked list

A hash map finds any key's node in O(1); a doubly linked list keeps nodes in order of use, most recent at the front. Every get or put moves the node to the front, and when over capacity the node before the dummy tail is evicted, along with its key, which is why nodes store their key.

Solution Walkthrough

  1. Step 1: Recognize the Pattern

    The key pattern is: Hash lookup plus recency ordering supports O(1) operations. Identify the state and invariant before coding.

  2. Step 2: Build the Algorithm

    Advance one state transition at a time. Mark or update state before exploring dependent work.

  3. Step 3: Check Edge Cases

    Test empty or minimal input, skewed shapes, duplicates where allowed, and impossible outcomes.

  4. Step 4: Solution and Complexity

    Time: O(q). Space: O(capacity).

    def lru_cache(capacity: int, operations: list[str], keys: list[int], values: list[int]) -> list[int]:
    from collections import OrderedDict
    cache, answer = OrderedDict(), []
    for operation, key, value in zip(operations, keys, values):
        if operation == "get":
            if key not in cache: answer.append(-1)
            else:
                answer.append(cache[key]); cache.move_to_end(key)
        else:
            if key in cache: del cache[key]
            cache[key] = value
            if len(cache) > capacity: cache.popitem(last=False)
    return answer

FAQ

See also

Practice LRU Cache online (run code in the browser)3Sum solution (medium)Accounts Merge solution (medium)Add Two Numbers solution (medium)Clone Graph solution (medium)All coding interview problems