Katkat
Back

Implement an O(1) LRU Cache

J.P. MorganSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to combine a hash map with a doubly linked list to achieve O(1) time complexity for cache operations.

Problem Statement

Design and implement a Least Recently Used (LRU) cache. The cache should support two operations: get and put.

  • get(key): Return the value of the key if it exists in the cache; otherwise, return -1. Accessing a key makes it the most recently used.
  • put(key, value): Update the value of the key if it exists. Otherwise, add the key-value pair to the cache. If the cache reaches its capacity, it must evict the least recently used item before adding the new item.

Both get and put must run in O(1) average time complexity.

Constraints

  • Capacity is a positive integer.
  • Total operations will be at most 10^5.

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

Example

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 key 2, Cache: {1=1, 3=3}
lru.get(2)    # Returns -1

Edge Cases

  • Accessing a key that does not exist.
  • Inserting into a cache with capacity 1.
  • Updating an existing key's value to move it to the most recently used position.

Hints

Hint 1

To achieve O(1) lookup, use a hash map to store keys and their corresponding node references.

Hint 2

To keep track of order in O(1) time, use a doubly linked list where the head represents the most recently used item and the tail the least recently used.

Hint 3

When a key is accessed or updated, move its corresponding node to the head of the linked list.

Follow-up questions

  • How would you handle thread safety if multiple threads access this cache simultaneously?
  • If the cache needed to be distributed across multiple servers, what architectural changes would you implement?
  • How would you modify the eviction policy if you wanted to implement a Least Frequently Used (LFU) cache instead?