Katkat
Back

Implement an LRU cache

DisneySoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to design a cache that supports O(1) access, insertion, and eviction by combining two core data structures.

Problem Description

Design and implement a Least Recently Used (LRU) cache. The cache should be initialized with a positive capacity n and support the following operations:

  1. get(key): Return the value of the key if it exists in the cache; otherwise, return -1. If the key exists, mark it as the most recently used item.
  2. 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 capacity, remove the least recently used item before inserting the new item.

Constraints

  • 1 <= capacity <= 1000
  • 0 <= key <= 10^5
  • 0 <= value <= 10^9
  • Operations must run in O(1) average time complexity.

Example

# Initialize with capacity 2
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 (not found)
lru.put(4, 4)   # evicts key 1, cache: {3: 3, 4: 4}
lru.get(1)      # returns -1

Hints

Hint 1

To achieve O(1) time complexity, you need to combine a hash map for fast lookups with a doubly linked list to track the order of usage.

Hint 2

The doubly linked list allows you to move an accessed node to the 'head' or remove the 'tail' node in constant time without traversing the entire list.

Hint 3

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

Follow-up questions

  • How would you modify your implementation to be thread-safe in a multi-threaded environment?
  • If you were to implement a Least Frequently Used (LFU) cache instead, how would the data structures change?
  • What are the implications of using a fixed-capacity cache in a distributed system versus a single-node application?