Implement weighted-eviction cache
Company: Netflix
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
##### Question
Design and implement a weighted cache supporting get(key) and put(key, value, weight) operations. The cache has a total weight limit; when inserting a new item would exceed the limit, evict the key-value pair with the largest weight. Aim for O(log N) get/put using an ordered map (e.g., TreeMap). Explain your data structures and complexity.
Quick Answer: This question evaluates understanding and practical implementation of data structures and algorithms for a weighted cache, including weighted eviction policies, use of ordered maps, and time-space complexity analysis.
Implement a weighted-eviction cache that processes a sequence of operations with a fixed total weight capacity. Each operation is either put(key, value, weight) or get(key). Keys and values are integers; weights are positive integers. The cache must maintain that the sum of weights of stored items never exceeds capacity. Rules: (1) get(key) returns the stored value if present, otherwise -1; it does not affect the cache. (2) put(key, value, weight): if weight > capacity, ignore the operation (no changes). Otherwise, set/overwrite key's value and weight (replacing any existing entry for key). If this causes total weight to exceed capacity, evict exactly one key: the one with the largest weight; if multiple keys share the largest weight, evict the one with the smallest key. Return one result per operation: the value for get, and the string "null" for put. Process operations in order and apply the eviction rule deterministically as specified.
Constraints
- 0 <= len(operations) <= 200000
- 0 <= capacity <= 10^12
- Operations are arrays: ["put", key, value, weight] or ["get", key]
- Keys and values are 32-bit signed integers
- 1 <= weight <= 10^9 for put operations
- If weight > capacity, the put is ignored and the cache is unchanged
- On put of an existing key, first replace its value and weight, then apply eviction
- When evicting due to capacity overflow, evict exactly one key: the key with the largest weight; ties broken by smallest key
- Return "null" for every put operation; return the stored value or -1 for get
Solution
from typing import List
import heapq
def weighted_eviction_cache(operations: list[list], capacity: int) -> list:
# Max-heap via negatives: entries are (-weight, key, version)
heap = []
store = {} # key -> (value, weight, version)
total = 0
version = 0
res: List[object] = []
def push(key: int, value: int, weight: int):
nonlocal version, total
version += 1
store[key] = (value, weight, version)
heapq.heappush(heap, (-weight, key, version))
total += weight
def evict_once_if_needed():
nonlocal total
if total <= capacity:
return
# Pop until we find a valid (non-stale) top; evict it.
while heap:
neg_w, k, ver = heapq.heappop(heap)
w = -neg_w
cur = store.get(k)
if cur is None or cur[2] != ver:
continue # stale
# Evict this key
total -= w
del store[k]
break
for op in operations:
if not op:
res.append("null")
continue
typ = op[0]
if typ == "put":
_, key, value, weight = op
if weight > capacity:
# Ignore this put entirely
res.append("null")
continue
# If key exists, remove its old weight from total; the old heap entry becomes stale
old = store.get(key)
if old is not None:
total -= old[1]
push(key, value, weight)
evict_once_if_needed()
res.append("null")
elif typ == "get":
_, key = op
cur = store.get(key)
res.append(cur[0] if cur is not None else -1)
else:
# Unknown op type; ignore
res.append("null")
return res
Explanation
Use two structures: (1) a hash map from key to (value, current weight, version), enabling O(1) get and tracking the current entry; and (2) a heap keyed by (-weight, key, version) so the top is always the largest weight, breaking ties by smallest key. Because Python's heapq is a min-heap, negative weights implement a max-heap. Updates create new heap nodes; old nodes become stale. Each cache mutation increments a version counter. When capacity is exceeded after a put, pop from the heap until a non-stale entry is found and evict that key, which is the largest by weight with ties broken by smallest key. Ignoring puts with weight > capacity avoids pathological immediate eviction and ensures determinism.
Time complexity: Amortized O(log N) per put (heap push and at most one valid pop), O(1) per get; stale pops are amortized. N is the number of keys in the cache.. Space complexity: O(N) for the map and heap (heap may contain stale entries proportional to the number of updates)..
Hints
- Maintain key -> (value, weight, version) in a hash map for O(1) access.
- Use a max-priority structure to find the largest weight quickly; in Python, use a min-heap with negative weights.
- To break ties by smallest key, include the key as the second component of the heap tuple.
- Handle updates by storing a version/timestamp per key and marking old heap entries as stale.
- Subtract the old weight before adding the new weight on put; if overweight, evict the current maximum.