Katkat
Back

Implement a Weighted Eviction Cache

NetflixData Engineer · Technical Screen
HardData EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to design a cache that respects both memory capacity and item weights, requiring an efficient combination of a hash map and a doubly linked list.

Weighted Eviction Cache

Design and implement a cache that supports a fixed maximum capacity. Unlike a standard LRU cache, each item added to the cache has a weight (a positive integer). When adding a new item, if the current total weight of the cache plus the new item's weight exceeds the capacity, you must evict items based on their last access time (Least Recently Used) until there is enough room for the new item.

Requirements

Implement the WeightedCache class:

  • __init__(self, capacity: int): Initializes the cache with a maximum capacity.
  • put(self, key: int, value: int, weight: int) -> None: Inserts or updates an item with a given weight. If the weight of the new item is greater than the total capacity, the operation should fail (do nothing or raise an error).
  • get(self, key: int) -> int: Returns the value of the key if it exists, updating its access status. Returns -1 if not found.

Constraints

  • Time complexity for get and put should be O(1) on average.
  • capacity, weight > 0.

Example

cache = WeightedCache(10)
cache.put(1, 100, 5) # Cache: {1: 100}, total weight: 5
cache.put(2, 200, 4) # Cache: {1: 100, 2: 200}, total weight: 9
cache.get(1)         # Returns 100, 1 is now most recently used
cache.put(3, 300, 3) # Needs 3 capacity. Evicts 2 (LRU), total weight: 5+3=8

Hints

Hint 1

Use a hash map to store key-to-node mappings for O(1) access and a doubly linked list to track the recency of items.

Hint 2

Maintain a variable `current_weight` to track the sum of weights of all elements currently in the cache.

Hint 3

When adding an item, use a while loop to repeatedly remove the tail (least recently used) of the linked list until the remaining `capacity - current_weight` is greater than or equal to the new item's weight.

Follow-up questions

  • How would you modify the eviction policy if, instead of LRU, we wanted to evict the item with the smallest weight first?
  • What changes are needed if the weights were dynamic (i.e., an existing item's weight could increase or decrease)?
  • How would you handle thread-safety if multiple processes access this cache simultaneously?