Katkat
Back

LRU Cache

AnthropicSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question tests the ability to combine a hash map and a doubly linked list to implement an LRU cache with O(1) performance for both get and put operations.

LRU Cache Implementation

Design and implement a Least Recently Used (LRU) cache. The cache should support get and put operations, both with an average time complexity of O(1).

Your LRUCache class should be initialized with a positive integer capacity:

  • get(key): Return the value of the key if it exists, otherwise return -1.
  • put(key, value): Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity before this operation, evict the least recently used item.

Implementation Signature

class LRUCache:
    def __init__(self, capacity: int):
        pass

    def get(self, key: int) -> int:
        pass

    def put(self, key: int, value: int) -> None:
        pass

Examples

Example 1:

lru = LRUCache(2)
lru.put(1, 1)  # cache: {1=1}
lru.put(2, 2)  # cache: {1=1, 2=2}
lru.get(1)     # returns 1, cache: {2=2, 1=1}
lru.put(3, 3)  # evicts 2, cache: {1=1, 3=3}
lru.get(2)     # returns -1

Constraints

  • capacity will be between 1 and 3000.
  • key and value will be non-negative integers.
  • You must handle updates to existing keys correctly.

Edge Cases

  • Accessing a key that doesn't exist.
  • Inserting into a full cache.
  • Updating a key that is already at the most recent position.
  • Cache capacity of 1.

Hints

Hint 1

To achieve O(1) time complexity, you need to combine two data structures: a hash map for fast lookups and a doubly linked list to track usage order.

Hint 2

The doubly linked list allows you to move an accessed node to the front (most recent) or remove the tail node (least recent) in O(1) time if you maintain pointers.

Hint 3

Consider using a sentinel 'head' and 'tail' node for the linked list to simplify insertion and deletion logic by avoiding null checks.

Follow-up questions

  • How would your implementation change if the cache needed to be thread-safe in a multi-threaded environment?
  • What would be the memory overhead of your implementation compared to a simple dictionary?
  • How would you modify the cache to support Time-to-Live (TTL) expiration for entries?