Netflix Data Scientist Interview Questions & Answers

I would use Dijkstra’s algorithm with a min-heap because every link has a positive latency. First, I build an undirected neighbor map and keep only the smallest ping for parallel links. I set the source distance to zero and repeatedly pop the city with the smallest current distance. I relax each neighbor when I find a shorter route. The overall target time is O((n + m) log n), with expected O(m) preprocessing, and the auxiliary space is O(n + m).

We have n cities connected by links. Each link has a positive travel delay called ping. We start from one source city. We need the smallest total delay needed to reach every city from that source. If a city cannot be reached, its answer must be -1. Links work in both directions. There can also be several links between the same two cities, so we keep the one with the smallest ping. We then find the shortest total delay to every reachable city without changing the input lists.

1. Are all link latencies positive? Yes. This makes Dijkstra’s algorithm valid.
2. Can there be parallel links between the same two cities? Yes. We can keep only the smallest ping between each pair.
3. What should I return for a city that cannot be reached? Return -1 for that city.
4. Should the input lists remain unchanged? Yes. The solution builds its own graph and does not mutate them.

The function receives n, links, and source. Cities are numbered from 0 through n - 1. Each link is [u, v, ping]. It is undirected, so we can travel from u to v or from v to u with the same ping. The result has one entry per city. Each entry is the minimum total latency from source. An unreachable city gets -1.

All pings are positive, so Dijkstra’s shortest-path algorithm fits this problem. I use a min-heap. Each heap item is (distance, city), so the smallest candidate distance comes out first. I also build a neighbor dictionary for each city. It maps neighbor -> minimum ping. If several links connect the same pair, I store only the smallest ping. Each improving relaxation pushes a new heap entry. An older entry may remain in the heap, so the code skips it when it is later popped and no longer matches dist[u].

For the example, n = 4, links = [[0,1,3],[0,2,2],[2,3,4],[1,3,5]], and source = 0. After building the undirected neighbor maps, the distance list starts as [0, infinity, infinity, infinity]. The source has distance 0 because no travel is needed to reach itself. The heap starts with (0, 0).

Step 1: The graph is ready. We keep one minimum-ping entry for each neighboring city. The distance state is [0, infinity, infinity, infinity], and the heap contains (0, 0).

Step 2: Pop (0, 0). City 0 has two neighbors. Reaching city 1 costs 0 + 3 = 3, so dist[1] becomes 3. Reaching city 2 costs 0 + 2 = 2, so dist[2] becomes 2. The distance list becomes [0, 3, 2, infinity]. The heap contains (2, 2) and (3, 1).

Step 3: Pop (2, 2). From city 2, the route to city 3 costs 2 + 4 = 6. This improves city 3 from infinity to 6. The distance list becomes [0, 3, 2, 6]. The heap contains (3, 1) and (6, 3).

Step 4: Pop (3, 1). Going from city 1 to city 3 would cost 3 + 5 = 8. The current distance to city 3 is already 6, so there is no update. The heap contains (6, 3).

Step 5: Pop (6, 3). There is no shorter route to any neighbor. The heap becomes empty, so processing ends. The final distances are [0, 3, 2, 6]. City 3 is reached by 0 -> 2 -> 3 with latency 2 + 4 = 6.

The min-heap always exposes the smallest candidate distance currently stored. When a city is popped with a distance equal to its current dist value, Dijkstra can safely process that distance because every retained edge weight is positive. Relaxation checks whether going through that city gives a neighbor a smaller distance and records every improvement. If an older heap entry is popped after a better route was already found, d != dist[u] identifies it as stale and the code skips it.

The code first creates one dictionary per city. Each dictionary maps a neighboring city to the smallest ping seen for that pair. Because links are undirected, the code writes the same ping in both directions. It then creates the distance list and starts a min-heap with the source. The main loop pops the smallest candidate. A stale entry is ignored. For every retained neighbor, the code calculates nd = d + ping. If nd is smaller, it updates dist[v] and pushes the new candidate. At the end, infinity is converted to -1.

Building the neighbor maps takes expected O(m) time because Python dictionary lookup and insertion are O(1) on average. Let m' be the number of unique retained undirected links after parallel links are collapsed. Dijkstra takes O((n + m') log n), and m' is at most m, so this satisfies the requested O((n + m) log n) target. Extra memory is O(n + m). Important cases are disconnected cities, parallel links, one city, and positive edge weights. For example, minimum_broadcast_latencies(3, [], 1) returns [-1, 0, -1].

Treat the cities as a weighted undirected graph and run Dijkstra’s algorithm from source. Before the shortest-path search, each city uses a dictionary that maps neighbor -> minimum ping. If parallel links exist, only the smallest ping is retained. The min-heap stores (candidate distance, city), so the smallest known candidate is processed first. The central invariant is that dist[v] stores the smallest distance discovered so far for city v. A relaxation changes it only when a strictly shorter route is found. Each improvement can add a new heap entry, and stale older entries are skipped when popped. Positive edge weights make Dijkstra valid.

Let n be the number of cities and m be the number of input links. Building the neighbor dictionaries takes expected O(m) time because Python dictionary lookup and insertion are O(1) on average. Let m' be the number of unique links left after parallel links are reduced to their smallest ping. Dijkstra takes O((n + m') log n). Since m' <= m, this meets the requested O((n + m) log n) target. The graph, distance list, and heap together use O(n + m) auxiliary space.

A common mistake is using ordinary BFS even though the links can have different weights. Another is forgetting that each link is undirected and must be represented in both directions. Candidates may mishandle parallel links instead of retaining the smallest ping for this design. Another mistake is failing to recognize stale heap entries, which can cause unnecessary repeated work. It is also easy to forget to convert unreachable infinity values to -1 or to state a complexity that ignores the heap, graph storage, or expected dictionary preprocessing.

State the invariant before coding: dist stores the best distance found so far, and the min-heap gives the next smallest candidate. Then show one exact relaxation, such as city 2 giving city 3 a distance of 2 + 4 = 6. This connects the reasoning, walkthrough, and code.

I would use an OrderedDict to keep live keys in LRU-to-MRU order and a min-heap for expiration deadlines. Before every operation, I purge heap records whose deadline is at or before the current time and ignore stale records. Successful puts and gets move the key to MRU. After a put, I evict the LRU key if capacity is exceeded. Heap work gives O(log n) amortized time per operation, while cache lookup and reorder are expected O(1). Auxiliary space is O(n) plus the live cache.

The function simulates a cache where entries can disappear for two reasons. A key can expire after its TTL, or it can be removed because the cache is full and it is the least recently used key. Expired entries must be removed before every command. A successful get or put makes that key the most recently used. The function returns one result for every command. The solution uses one structure for usage order and another structure for expiration order.

1. Should invalid capacity or more than 200,000 operations also raise ValueError, in addition to malformed operation rows?
2. When an existing key is updated, may its old expiration record remain in the heap and be ignored later as stale?
3. Does TTL 0 always mean that the key never expires? The stated contract says yes.

The function is run_cache(operations, capacity). Capacity is between 1 and 100,000. There are at most 200,000 operations, and operation times are nondecreasing integers.

There are four supported row types. put stores or updates a key. get reads a live key. delete removes a key. size returns the number of live keys. A put or delete returns None. A get returns the stored value or None. A size operation returns the current live count.

A positive TTL expires at put_time + ttl. If an operation happens exactly at that deadline, the entry is already expired. TTL 0 means the entry never expires.

I use an OrderedDict for live cache entries. Its order is always LRU to MRU. The leftmost key is the least recently used key. The rightmost key is the most recently used key. Each key stores (value, deadline). A deadline of None means the key never expires.

I also use a heapq min-heap. Each finite-TTL put adds (deadline, key). The earliest deadline is at the top. Old heap records can remain after updates, deletes, or capacity eviction. When one is popped, I compare its deadline with the key's current stored deadline. If they do not match, the heap record is stale and I ignore it.

The main invariant is that after the purge step, every live cache entry has no deadline or has a deadline greater than the current operation time. The OrderedDict is also always ordered from LRU to MRU.

First, validate the row. Then purge every expired heap record whose deadline is less than or equal to the current time.

For put, compute the new deadline. Store or update the key. Move it to MRU. If the TTL is positive, push the finite deadline into the heap. If the cache now exceeds capacity, remove the LRU key. Append None.

For get, return None if the key is absent. Otherwise, move the key to MRU and return its value.

For delete, remove the key if it exists and append None.

For size, append len(cache).

The capacity is 2.

At time 0, put("a", 10, 5) stores a with deadline 5. The heap contains (5, "a"). The cache contains a. The result is None.

At time 1, put("b", 20, 0) stores b with no deadline. The cache order is [a, b], from LRU to MRU. The result is None.

At time 2, get("a") finds a alive. It returns 10 and moves a to MRU. The cache becomes [b, a].

At time 5, the heap record (5, "a") is due because 5 <= 5. The current deadline of a is also 5, so a is deleted before the get runs. get("a") returns None. The cache is [b].

At time 6, put("c", 30, 0) stores c with no deadline and makes it MRU. The cache becomes [b, c]. Capacity is not exceeded. The result is None.

At time 7, delete("b") removes b. The cache becomes [c]. The result is None.

At time 8, size returns 1. The final result is [None, None, 10, None, None, None, 1].

Expired entries are removed before every operation, so an expired key cannot be returned by get or counted by size. Comparing a popped heap deadline with the key's current deadline prevents an old heap record from deleting a newer version of that key. Successful gets and puts move their keys to MRU. Therefore the leftmost live key is always the correct LRU key to remove when a put exceeds capacity.

OrderedDict.move_to_end(key) moves a successful get or put to the MRU end. popitem(last=False) removes the LRU key. The min-heap stores finite expiration records. The purge helper repeatedly pops deadlines that are due and verifies that each popped record still matches the current cache entry before deleting anything.

The main loop validates each row, checks that time does not move backward, purges expired entries first, performs the requested operation, updates LRU order when required, enforces capacity after put, and appends exactly one result.

Let n be the number of expiration records that may be pending in the heap. Each finite-TTL put performs one heap push, and each heap record can be popped at most once. Heap push and pop operations cost O(log n), so the heap work is O(log n) amortized per operation. OrderedDict lookup, deletion, and reordering are expected O(1).

The heap can contain stale records, so its memory can grow to O(n) over the operation sequence. The live OrderedDict stores at most capacity keys. Important cases are TTL 0, expiry exactly at the operation time, updating an existing key, stale heap records after update or delete, and LRU eviction after a put.

The key idea is to separate two different orderings. Expiration order is handled by a min-heap because we always need the earliest deadline first. Usage order is handled by an OrderedDict because successful gets and puts must move to the MRU end, while over-capacity puts must remove the LRU end. Each live key stores (value, deadline), and each finite TTL adds (deadline, key) to the heap. The invariant is that after purging, every live entry is unexpired and the OrderedDict is exactly LRU to MRU. Stale heap records are safe because a popped record deletes a key only when its deadline still matches the key's current stored deadline.

Let n be the number of pending expiration records. A finite-TTL put pushes one record into the min-heap, which costs O(log n). Purging may pop several records during one operation, but each heap record can be popped only once over the full run. This makes the heap work O(log n) amortized per operation. OrderedDict lookup, deletion, and reordering are expected O(1). The heap may keep stale records, so it can use O(n) extra space. The live cache itself stores at most capacity entries.

A common mistake is purging after the operation instead of before it. That incorrectly allows a key to survive at its exact expiration deadline. Another mistake is treating TTL 0 as immediate expiration instead of never expiring. Candidates may forget that old heap records can become stale after updates, deletes, or capacity eviction. It is also easy to forget to move a key to MRU after a successful get or put. Another error is enforcing capacity before the put instead of after the put makes the cache too large. Finally, Python hash-based operations should be described as expected O(1), not guaranteed worst-case O(1).

State the two invariants before coding: after every purge, all remaining cache entries are live, and the OrderedDict is ordered from LRU to MRU. Then make every operation preserve those two facts.