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
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.