Netflix·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

May 2026Remote

Summary

Netflix SWE interview with a custom data structure problem that had more moving parts than I expected. The weight-based eviction twist is what got me.

Questions Asked (1)

Design and implement a cache that supports get(key) and put(key, value, weight) operations, where the cache has a total weight capacity. When adding a new entry would push the total weight over the limit, evict the entry with the highest weight. Target O(log N) time for both operations and explain your data structure choices.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

I went straight for a HashMap plus a TreeMap keyed by weight, which felt right.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the requirements and constraints first, then propose a data structure that combines a hash map for O(1) key lookup with a balanced binary search tree (or heap) keyed by weight to efficiently find and evict the highest-weight entry. Explain how you maintain the total weight and handle edge cases like updating an existing key's weight, ensuring O(log N) for both get and put.

Pro tip: Mention that you would use a self-balancing BST (e.g., red-black tree) or a skip list to guarantee O(log N) worst-case, and discuss how you would handle weight updates by removing and reinserting the entry. Also, consider if the eviction policy should be 'highest weight' or 'highest weight among least recently used' and clarify with the interviewer.

1. Clarify Requirements and Constraints

Ask about the expected size of the cache, whether weights can be updated, if there are any concurrency requirements, and confirm the eviction policy (evict the entry with the highest weight when over capacity).

2. Choose Data Structures

Propose a hash map for O(1) key lookup and a balanced BST (or heap) keyed by weight for O(log N) insertion, deletion, and finding the max weight. Explain why a heap alone is insufficient if you need to update weights or remove arbitrary entries.

3. Design Operations

Detail how get(key) works: look up in hash map, return value. For put(key, value, weight): if key exists, update value and weight (remove old weight from BST, insert new weight); else insert into both structures. Then, while total weight > capacity, find and remove the entry with the highest weight from the BST and hash map, updating total weight.

4. Analyze Complexity and Trade-offs

Explain that get is O(1) and put is O(log N) due to BST operations. Discuss trade-offs: a heap gives O(log N) for insertion and O(1) for finding max, but O(N) for arbitrary deletion/update; a balanced BST gives O(log N) for all operations. Mention alternative approaches like using a Fibonacci heap or a skip list.

5. Handle Edge Cases and Optimizations

Address edge cases: empty cache, weight exceeding capacity, updating weight of existing key, and concurrent access (if relevant). Suggest optimizations like lazy deletion or using a doubly linked list combined with a heap for O(1) access to max if weights are static.

Key Points to Mention

Hash map for O(1) key lookup and balanced BST (e.g., red-black tree) for O(log N) weight-ordered operations.
Maintaining total weight and updating it on insertions, deletions, and weight changes.
Handling weight updates by removing the old entry from the BST and reinserting with the new weight.
Eviction loop: while total weight > capacity, remove the entry with the maximum weight from the BST and hash map.
Complexity analysis: get O(1), put O(log N) due to BST operations; space O(N).
Trade-offs between using a heap (O(log N) insert, O(1) find max, but O(N) delete/update) and a balanced BST (O(log N) for all).

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.