Katkat
Back

Implement a Capacity-Bounded Cache

ShopifyMachine Learning Engineer · Technical Screen
MediumMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

This question tests the ability to implement a Least Recently Used (LRU) cache, requiring efficient O(1) time complexity for both data retrieval and insertion through the combination of a hash map and a doubly linked list.

Problem Statement

Design and implement a thread-safe-capable Cache class that supports a fixed capacity. Once the cache reaches its capacity, it should invalidate the least recently used item before inserting a new item.

Your implementation must support the following two operations with O(1) average time complexity:

  1. get(key): Return the value of the key if it exists, otherwise return -1.
  2. put(key, value): Update the value if the key exists. If not, add the key-value pair to the cache. If the capacity is exceeded, remove the least recently used entry.

Constraints

  • capacity will be a positive integer.
  • Total operations will be up to 10^5.

Function 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:

cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
cache.get(1)    # returns 1
cache.put(3, 3) # evicts key 2
cache.get(2)    # returns -1

Edge Cases to Consider

  • get on a non-existent key.
  • put when the key already exists (should update and move to front).
  • capacity of 1.
  • Repeatedly calling put with the same key.

Hints

Hint 1

A hash map allows O(1) access to data, but it does not maintain order for eviction purposes.

Hint 2

Consider using a doubly linked list to maintain the order of access, where the head is the most recently used and the tail is the least recently used.

Hint 3

By storing the node references in your hash map, you can achieve O(1) lookups and O(1) updates to the linked list pointers.

Follow-up questions

  • How would you modify your implementation to be thread-safe in a concurrent environment?
  • If you needed to implement a Least Frequently Used (LFU) cache instead, how would the data structures change?
  • How would you handle the serialization of this cache if the system needs to persist the state to disk upon shutdown?