Katkat
Back

Implement an LRU Cache

ShopifyData Scientist · Technical Screen
MediumData ScientistTechnical ScreenCoding & Algorithms

Last updated

This question tests the ability to combine a hash map and a doubly linked list to achieve constant-time performance for cache operations.

LRU Cache Implementation

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

Requirements

  • LRUCache(int capacity): Initialize the LRU cache with a positive size capacity.
  • int get(int key): Return the value of the key if the key exists; otherwise, return -1. If a get occurs, the accessed key becomes the most recently used.
  • void put(int key, int value): Update the value of the key if it exists. Otherwise, add the key-value pair to the cache. If the cache exceeds capacity during this operation, evict the least recently used key.

Example

lru = LRUCache(2)
lru.put(1, 1) # Cache is {1: 1}
lru.put(2, 2) # Cache is {1: 1, 2: 2}
lru.get(1)    # Returns 1. Cache is {2: 2, 1: 1}
lru.put(3, 3) # Evicts key 2. Cache is {1: 1, 3: 3}
lru.get(2)    # Returns -1 (not found)

Constraints

  • 1 <= capacity <= 3000
  • 0 <= key <= 10^4
  • 0 <= value <= 10^5
  • Both get and put will be called at most 2 * 10^5 times.

Edge Cases

  • Accessing a key that doesn't exist.
  • Inserting a key when the cache is already at capacity.
  • Updating an existing key's value.
  • Capacity of 1.

Hints

Hint 1

Consider using a hash map for fast key lookup and a linked structure to maintain the order of usage.

Hint 2

A doubly linked list allows for O(1) removal and insertion if you have a reference to the specific node.

Hint 3

Think about how to keep track of the 'head' (most recently used) and 'tail' (least recently used) pointers to manage evictions efficiently.

Follow-up questions

  • How would you modify your implementation to be thread-safe in a multi-threaded environment?
  • What would change if you needed to track the 'most frequently used' items instead of 'least recently used'?
  • How does the memory complexity of this data structure scale as the capacity increases?