Netflix software engineer interviews cover algorithms, data structures, system design, and coding problems drawn from real interview rounds.
Weight-Based Cache
Input: ListScenario
Part 1 — Expiration and recency
op, time_ms, namespace, and key; op is PUT or GET. Times are nondecreasing.(namespace, key). Different namespaces may use the same key independently.PUT also contains value and bytes, where bytes is a positive decimal integer representing the metadata's measured footprint. An optional positive ttl_ms overrides the default TTL of 1000 milliseconds.expires_at <= time_ms. Set expires_at = time_ms + ttl_ms on each successful PUT; a GET never renews TTL.max_entries. A successful PUT inserts or replaces an entry and makes it most recently used. A successful GET also makes its entry most recently used. Misses do not change recency.PUT, evict the globally least recently used entries until the entry limit is satisfied. Input order breaks recency ties, including operations with identical timestamps.STORED for a successful PUT, HIT with the stored value for a successful GET, and MISS otherwise. Your return type is up to you; the examples use a list of result objects.simulate_cache(records: list[dict[str, str]], max_entries: int = 3); return type is up to the candidate.Example 1:
{
"records": [
{"op": "PUT", "time_ms": "0", "namespace": "artwork", "key": "title-1:en", "value": "image-A", "bytes": "2"},
{"op": "GET", "time_ms": "5", "namespace": "artwork", "key": "title-1:en"},
{"op": "GET", "time_ms": "6", "namespace": "manifest", "key": "title-1:en"},
{"op": "PUT", "time_ms": "7", "namespace": "artwork", "key": "title-1:en", "value": "image-B", "bytes": "3", "ttl_ms": "10"},
{"op": "GET", "time_ms": "17", "namespace": "artwork", "key": "title-1:en"}
]
}[
{"status": "STORED"},
{"status": "HIT", "value": "image-A"},
{"status": "MISS"},
{"status": "STORED"},
{"status": "MISS"}
]7 + 10 = 17; it is expired exactly at time 17.Part 2 — Independently owned namespace budgets
part=2.max_bytes, default 10, as the global live-byte limit. Every namespace has a default live-byte limit of 6. Optional namespace_limits records such as {"namespace":"artwork","max_bytes":"8"} override that namespace's limit.(expires_at, namespace, key) using lexicographic string ordering.PUT target, reject it if its individual bytes exceeds its namespace limit or the global byte limit. Return REJECTED and all violated policy names, ordered NAMESPACE_BYTES, then GLOBAL_BYTES. Equality is allowed. Rejection must preserve any still-live old value and must not refresh its recency or TTL.EXPIRED, NAMESPACE_BYTES, GLOBAL_BYTES, or ENTRY_COUNT. A replacement is not a reported removal. Expiration removals precede capacity removals.removed list, even when empty. Return final resident entry and byte counts as well. These counts reflect the time of the last operation, without advancing the clock afterward.simulate_cache(records: list[dict[str, str]], max_entries: int = 3, *, part: int = 1, max_bytes: int = 10, namespace_limits: list[dict[str, str]] | None = None); discuss and choose the return type.Example 2:
{
"part": 2,
"records": [
{"op": "PUT", "time_ms": "0", "namespace": "artwork", "key": "a", "value": "A", "bytes": "4"},
{"op": "PUT", "time_ms": "1", "namespace": "manifest", "key": "m", "value": "M", "bytes": "4"},
{"op": "PUT", "time_ms": "2", "namespace": "artwork", "key": "b", "value": "B", "bytes": "3"},
{"op": "GET", "time_ms": "3", "namespace": "manifest", "key": "m"},
{"op": "PUT", "time_ms": "4", "namespace": "subtitle", "key": "s", "value": "S", "bytes": "4"}
]
}{
"results": [
{"status": "STORED", "removed": []},
{"status": "STORED", "removed": []},
{"status": "STORED", "removed": [{"namespace": "artwork", "key": "a", "reason": "NAMESPACE_BYTES"}]},
{"status": "HIT", "value": "M", "removed": []},
{"status": "STORED", "removed": [{"namespace": "artwork", "key": "b", "reason": "GLOBAL_BYTES"}]}
],
"resident": {"entries": 2, "bytes": 8}
}b initially produces artwork usage 4 + 3 = 7 > 6 and global usage 4 + 4 + 3 = 11 > 10. Namespace enforcement runs first and removes a, reducing global usage to 7, so no global eviction is needed at that step. Reading m makes it newer than b. Inserting s produces 3 + 4 + 4 = 11 bytes; global enforcement removes b, leaving m and s with 4 + 4 = 8 bytes.Example 3:
{
"part": 2,
"records": [
{"op": "PUT", "time_ms": "0", "namespace": "artwork", "key": "a", "value": "A", "bytes": "4", "ttl_ms": "10"},
{"op": "PUT", "time_ms": "1", "namespace": "manifest", "key": "m", "value": "M", "bytes": "5"},
{"op": "PUT", "time_ms": "2", "namespace": "artwork", "key": "a", "value": "too-large", "bytes": "11"},
{"op": "GET", "time_ms": "3", "namespace": "artwork", "key": "a"},
{"op": "PUT", "time_ms": "10", "namespace": "subtitle", "key": "s", "value": "S", "bytes": "1"},
{"op": "GET", "time_ms": "10", "namespace": "artwork", "key": "a"}
]
}{
"results": [
{"status": "STORED", "removed": []},
{"status": "STORED", "removed": []},
{"status": "REJECTED", "violations": ["NAMESPACE_BYTES", "GLOBAL_BYTES"], "removed": []},
{"status": "HIT", "value": "A", "removed": []},
{"status": "STORED", "removed": [{"namespace": "artwork", "key": "a", "reason": "EXPIRED"}]},
{"status": "MISS", "removed": []}
],
"resident": {"entries": 2, "bytes": 6}
}11 > 6 and 11 > 10. It is rejected without deleting the original 4-byte value, so resident usage remains 4 + 5 = 9. The later hit does not renew its TTL. At time 10, expiration removes 4 bytes before the subtitle insertion adds 1 byte, leaving 9 - 4 + 1 = 6 bytes across two entries.Notes:
bytes is supplied metadata, not the length of value. Capacities are configurable and may be large; avoid scanning the whole cache on each operation. Aim for O(n log n) total processing time, excluding string comparison costs.now, measured in milliseconds. Timestamps are nondecreasing across all operations on an instance; do not use the system clock.A put(key, value, ttl, now) inserts or replaces an entry whose expiration timestamp is now + ttl. An entry is expired when now >= expiration. Replacing an existing live entry resets its value and expiration, and makes it most recently used. An old expiration record must never invalidate a newer version of the same key.A get(key, now) returns the value of a live entry and makes it most recently used. It returns None for a missing or expired entry. A miss does not change the relative recency of live entries.Before processing either operation, discard all expired entries. When inserting a new key into a full cache, evict the least recently used live entry. Expired entries must never cause an otherwise unnecessary live-entry eviction. If multiple operations have the same timestamp, their call order determines recency.Support O(log(capacity + 1)) amortized time per operation and O(capacity) total auxiliary storage, including expiration bookkeeping. Scanning the entire cache on every operation is not acceptable, and repeatedly updating one key must not cause unbounded expiration-record growth. An individual operation may do more work when reclaiming accumulated expired entries.Function or class signatureTTLCache(capacity: int) — construct an empty cache.put(key: str, value: int, ttl: int, now: int) -> None — insert or replace an entry.get(key: str, now: int) -> int | None — return a live value or None.{
"operations": ["TTLCache", "put", "put", "get", "put", "get", "get", "get"],
"arguments": [[2], ["title-A", 10, 5, 0], ["title-B", 20, 10, 1], ["title-A", 2], ["title-C", 30, 10, 3], ["title-B", 4], ["title-A", 5], ["title-C", 5]]
}[null, null, null, 10, null, null, null, 30]
put results are represented by null.Example 2:Input:{
"operations": ["TTLCache", "put", "put", "put", "get", "put", "get", "get", "get"],
"arguments": [[2], ["title-A", 1, 3, 0], ["title-A", 2, 10, 1], ["title-B", 3, 20, 2], ["title-A", 3], ["title-C", 4, 1, 4], ["title-B", 4], ["title-C", 5], ["title-A", 11]]
}[null, null, null, null, 2, null, null, null, null]
1 <= capacity <= 100000.200000 calls to get and put per instance.1 through 100.[-10^9, 10^9]; None is reserved for a miss.1 <= ttl <= 10^12 and 0 <= now <= 10^12; use an integer type that can hold now + ttl.get and put linearizable when multiple request threads share the cache? Explain which expiration, lookup, recency, and eviction steps must be atomic, and how timestamps should be assigned when lock-acquisition order differs from request-arrival order.Sign up for free to access walkthroughs, AI-generated questions, and more.
Get Started Free