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

LRU Cache – Solution & Complexity

Interview solutions
/
LRU Cache

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
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?