How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Netflix.

What role is this question designed for?

This question is commonly asked for Data Engineer candidates at Netflix during technical interviews.

Implement a Weighted Eviction Cache | Netflix Coding Question

Quick Overview

This question evaluates proficiency with data structures and algorithmic design for resource-constrained caching, specifically weight-aware eviction policies combined with LRU tie-breaking, and the ability to reason about efficiency and stateful operation under capacity limits.

Implement a Weighted Eviction Cache

Company: Netflix

Role: Data Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

Design an in-memory cache whose capacity is limited by **total weight** rather than by the number of entries. Each entry has: - a `key` - a `value` - a positive integer `weight` Support the following operations: - `get(key)`: return the value associated with `key`, or `-1` if the key is not present. - `put(key, value, weight)`: insert a new entry or update an existing one. The cache has a maximum allowed total weight `W`. After every `put`, if the sum of weights of all cached entries exceeds `W`, repeatedly evict entries until the total weight is at most `W`. Eviction rule: - Evict the entry with the **largest weight** first. - If multiple entries have the same weight, evict the **least recently used** among them. Additional rules: - A successful `get` makes the entry most recently used. - Updating an existing key through `put` also makes it most recently used. - If a single entry's weight is greater than `W`, it should not remain in the cache. Implement this data structure efficiently.

Quick Answer: This question evaluates proficiency with data structures and algorithmic design for resource-constrained caching, specifically weight-aware eviction policies combined with LRU tie-breaking, and the ability to reason about efficiency and stateful operation under capacity limits.

Design an in-memory cache whose capacity is limited by total weight instead of number of entries. Each cached entry has a key, a value, and a positive integer weight. Process a sequence of operations on the cache: - [1, key, value, weight] means put(key, value, weight) - [2, key] means get(key) Rules: - get(key): return the stored value, or -1 if the key is not present. - put(key, value, weight): insert a new entry or update an existing one. - After every put, if the sum of weights in the cache exceeds max_weight, repeatedly evict entries until the total weight is at most max_weight. - Evict the entry with the largest weight first. - If multiple entries have the same weight, evict the least recently used among them. - A successful get makes that entry most recently used. - A put on an existing key replaces its old value and weight, and the updated entry becomes most recently used. - A newly inserted entry is also considered most recently used. - If a single entry's weight is greater than max_weight, it must not remain in the cache. Return the results of all get operations in order. For this problem, values are non-negative integers, so -1 is reserved for a missing key.

Constraints

0 <= max_weight <= 10^9
0 <= key <= 10^9
0 <= value <= 10^9
1 <= weight <= 10^9 for every put operation
1 <= len(operations) <= 2 * 10^5
operations[i][0] is either 1 or 2

Examples

Input: (10, [[1, 1, 100, 4], [1, 2, 200, 6], [2, 1], [1, 3, 300, 6], [2, 2], [2, 3]])

Expected Output: [100, -1, 300]

Explanation: After inserting key 3, total weight becomes 16. The largest weight is 6, shared by keys 2 and 3. Key 2 is less recent, so it is evicted. The get results are 100, -1, and 300.

Input: (8, [[1, 1, 10, 4], [1, 2, 20, 4], [2, 1], [1, 3, 30, 4], [2, 2], [2, 1], [2, 3]])

Expected Output: [10, -1, 10, 30]

Explanation: The get on key 1 makes it most recently used among weight-4 entries. When key 3 is inserted, the cache must evict one weight-4 entry, so key 2 is removed as the least recently used.

Input: (7, [[1, 1, 10, 3], [1, 2, 20, 3], [1, 1, 15, 5], [2, 1], [2, 2]])

Expected Output: [-1, 20]

Explanation: Updating key 1 replaces its old weight 3 with weight 5. The total becomes 8, so the cache evicts the largest-weight entry, which is key 1 itself. Key 2 remains.

Input: (5, [[1, 1, 10, 7], [2, 1], [1, 2, 20, 3], [1, 3, 30, 3], [2, 2], [2, 3]])

Expected Output: [-1, -1, 30]

Explanation: Key 1 has weight 7, which is larger than the capacity, so it is immediately evicted. Later, inserting key 3 causes total weight 6, so between keys 2 and 3 with equal weight 3, key 2 is evicted as the least recently used.

Input: (0, [[1, 5, 50, 1], [2, 5], [1, 6, 60, 2], [2, 6]])

Expected Output: [-1, -1]

Explanation: The cache has zero total capacity, so every inserted entry is immediately evicted.

Hints

Recency only matters when weights tie, so consider maintaining a separate LRU order for each weight.
You need to find the current largest weight quickly; a max-heap with lazy deletion works well with per-weight buckets.

Quick Overview