Quick Overview

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

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

  1. Maintain key -> (value, weight, version) in a hash map for O(1) access.
  2. Use a max-priority structure to find the largest weight quickly; in Python, use a min-heap with negative weights.
  3. To break ties by smallest key, include the key as the second component of the heap tuple.
  4. Handle updates by storing a version/timestamp per key and marking old heap entries as stale.
  5. Subtract the old weight before adding the new weight on put; if overweight, evict the current maximum.

Loading coding console...

Show the approach

Approach

The cache keeps two structures in sync:

  • store: a hash map key -> (value, weight, version) giving O(1) get and the authoritative current state of each key.
  • heap: a lazy max-heap of tuples (-weight, key, version). Python's heapq is a min-heap, so negating the weight puts the largest weight on top; for ties the key field sorts ascending, so the smallest key wins — exactly the eviction order the problem requires.

put(key, value, weight): If weight > capacity the op is ignored. Otherwise, if the key already exists, its old weight is subtracted from total (its stale heap node is left in place). Then push writes the new (value, weight, version) with a fresh, monotonically increasing version, adds weight to total, and pushes a new heap node. Finally evict_once_if_needed runs.

Why exactly one eviction suffices: before each put the cache was already within capacity, and a put adds at most one new item, so the overflow is at most one item's worth. So when total > capacity, the code pops heap nodes, skipping any whose version no longer matches store (stale, from an overwrite or prior eviction), and evicts the first valid node — the heaviest current key, smallest-key on ties — then stops.

get(key) returns the stored value or -1, never mutating the cache. Empty/unknown ops append "null" defensively. Versioning is the correctness linchpin: it lets stale heap entries accumulate harmlessly and be discarded lazily, avoiding costly in-heap deletion.

Time complexity:
O(M log M) overall for M operations. Each put does one heap push and an amortized-O(1) number of valid pops; stale nodes (from overwrites/evictions) are each popped at most once over the whole run, so total pop work is O(M log M). get is O(1).
Space complexity:
O(M) worst case. The store holds O(N) live keys, but the heap can accumulate up to O(M) entries (one per put, including stale nodes from overwrites) before they are lazily discarded.