{ }DevToolsDaily
ToolsInterview
Problems
New
CheatsheetsChat
New
BlogPricing
Ctrl + K

LRU Cache – Solution & Complexity

Interview solutions
/
LRU Cache

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. Build the Algorithm

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

3. Check Edge Cases

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

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)Clone Graph solution (medium)Contains Duplicate solution (easy)Design Add and Search Words solution (medium)Find Median from Data Stream solution (hard)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsContact Us © Monkey SkatesHave kids?