Recommend top-K movies from similarity graph
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Movie Recommendation: Top K
You are building a simple movie recommendation feature.
### Input
- A set of movies `0..(M-1)`.
- An **undirected** similarity graph `adj`, where `adj[i]` lists movies similar to movie `i`.
- An array `rating[i]` (or `score[i]`) for each movie.
- A starting movie `start` that the user liked.
- A set `watched` of movies the user has already watched.
- An integer `K`.
### Output
Return a list of up to `K` **recommended movie IDs** that the user has **not watched**.
### Ranking rules
1. Prefer movies with **smaller graph distance** (fewer similarity hops) from `start`.
2. If distances tie, prefer **higher `rating`**.
3. If still tied, break ties by **smaller movie ID**.
### Notes / constraints
- The graph can be large; avoid revisiting nodes.
- If fewer than `K` unwatched movies are reachable, return all reachable unwatched movies.
### Follow-up (production thinking)
What potential issues might arise when deploying this in production (e.g., caching, concurrency, hot keys, stale data), and how would you mitigate them?
Overview: This question evaluates understanding of graph traversal and shortest-path distance concepts along with multi-criteria ranking (distance, rating, ID) and efficient exploration of large undirected graphs to avoid revisiting nodes.
Read the full Google Software Engineer interview experience this question came from
Part 1: Recommend top-K movies from similarity graph
Recommend up to **`k`** movies for a user, given a similarity graph between movies and each movie's rating.
## Problem
You are building a movie recommender. Movies form an **undirected similarity graph**: movie `i` is directly similar to every movie listed in `adj[i]`. Each movie also has a numeric rating.
Starting from a movie `start` that the user liked, return the list of recommended movie IDs (most relevant first), choosing them by graph distance, then rating, then ID.
## Function signature
```python
def solution(adj, rating, start, watched, k):
```
## Inputs
- **`adj`** — adjacency list. `adj[i]` is a list of movie IDs directly connected to movie `i`. There are `n = len(adj)` movies, with IDs `0 .. n - 1`.
- **`rating`** — list of length `n`; `rating[i]` is the rating of movie `i`.
- **`start`** — ID of the movie the user liked (the starting node).
- **`watched`** — list of movie IDs the user has already watched.
- **`k`** — the maximum number of recommendations to return.
## Output
Return a **list of up to `k` movie IDs** in recommendation order.
## Eligibility
A movie may be recommended only if **all** of the following hold:
- it is **reachable** from `start` in the graph, **and**
- it is **not** in `watched`, **and**
- it is **not** the `start` movie itself.
## Ranking
Order all eligible movies by these tie-breakers, in priority order:
1. **Smaller graph distance** from `start` comes first (distance = number of edges on the shortest path).
2. If distances tie, **higher rating** comes first.
3. If both distance and rating tie, **smaller movie ID** comes first.
If fewer than `k` eligible movies are reachable, return **all** of them in this order.
## Examples
**Example 1**
```
adj = [[1, 2], [0, 3], [0, 3, 4], [1, 2], [2]]
rating = [5, 7, 6, 9, 8]
start = 0
watched = [0, 2]
k = 3
=> [1, 3, 4]
```
Movie `2` is excluded (in `watched`) and `0` is the start. Movie `1` is at distance 1; movies `3` and `4` are at distance 2 (so `1` comes before them). Among the distance-2 movies, `3` (rating 9) ranks above `4` (rating 8).
**Example 2**
```
adj = [[1, 2], [0, 3], [0, 4], [1], [2]]
rating = [1, 8, 8, 7, 9]
start = 0
watched = [0]
k = 4
=> [1, 2, 4, 3]
```
Movies `1` and `2` are at distance 1 with equal ratings (8 and 8), so the smaller ID `1` comes first. Movies `3` and `4` are at distance 2; `4` (rating 9) outranks `3` (rating 7).
## Notes and edge cases
- If `k <= 0`, or if `start` is outside the range `[0, n - 1]`, return an empty list.
- The graph is undirected, but the input may contain **repeated/duplicate edges**; make sure you do not revisit nodes (avoid infinite loops).
- `watched` may or may not contain `start`; either way, `start` must never be recommended.
## Constraints
- `1 <= len(adj) == len(rating) <= 100000`
- `0 <= start < len(adj)`
- `0 <= k <= len(adj)`
- Each neighbor in `adj[i]` is a valid movie ID in the range `[0, len(adj) - 1]`
Constraints
- 1 <= len(adj) == len(rating) <= 100000
- 0 <= start < len(adj)
- 0 <= k <= len(adj)
- Each neighbor in adj[i] is a valid movie ID in the range [0, len(adj) - 1]
- The graph is undirected, but the input may still contain repeated edges; do not revisit nodes infinitely
- watched may or may not contain start, but start must never be recommended
Examples
Input: ([[1, 2], [0, 3], [0, 3, 4], [1, 2], [2]], [5, 7, 6, 9, 8], 0, [0, 2], 3)
Expected Output: [1, 3, 4]
Explanation: Movie 1 is distance 1 and unwatched. Movies 3 and 4 are distance 2. Among distance-2 movies, rating 9 beats rating 8.
Input: ([[1, 2], [0, 3], [0, 4], [1], [2]], [1, 8, 8, 7, 9], 0, [0], 4)
Expected Output: [1, 2, 4, 3]
Explanation: Movies 1 and 2 are both distance 1 with equal rating, so smaller ID 1 comes first. At distance 2, movie 4 has higher rating than movie 3.
Hints
- Use BFS because every edge has the same cost, so BFS gives the shortest hop distance.
- Process one BFS layer at a time. All movies found in the same layer have the same distance, so you only need to sort that layer by rating and movie ID.
Part 2: Classify stale and hot cache keys for movie recommendations
Classify every starting movie in a recommendation cache as **stale**, **hot**, both, or neither, and return one action per movie.
## Background
A production recommendation service caches results keyed by a **starting movie ID**. Each cached entry was computed from a list of **dependency movie IDs** that influenced that recommendation. If any of those dependency movies has changed, the cached result is **stale** and must be recomputed.
A starting movie is **hot** if it appears frequently in recent requests, and hot keys should be protected with mitigations such as request coalescing or per-key throttling.
## Task
Implement:
```python
def solution(requests, cache_entries, updated_movies, hot_threshold):
```
### Parameters
- **`requests`** — a list of integer movie IDs representing recent requests. A movie may appear multiple times.
- **`cache_entries`** — a dict mapping each cached **starting movie ID** to a list of its **dependency movie IDs**. A dependency list may be empty.
- **`updated_movies`** — a list of integer movie IDs that have changed.
- **`hot_threshold`** — an integer.
### Which movies to classify
Produce an action for **every** starting movie that appears in **either**:
- the `requests` list, **or**
- the keys of `cache_entries`.
(A movie may appear in only one of these. A movie present in `requests` but absent from `cache_entries` simply has no dependencies.)
### Classification rules
For each such movie, determine two independent flags:
- **stale** — `True` if **at least one** of the movie's dependency IDs (from its `cache_entries` list) is in `updated_movies`. A movie with **no cache entry** or an **empty** dependency list is **not** stale.
- **hot** — `True` if the movie's number of occurrences in `requests` is **greater than or equal to** `hot_threshold`. A movie not present in `requests` has a count of `0`.
Map the two flags to an action:
| stale | hot | action |
|-------|-----|--------|
| yes | yes | `recompute_and_protect` |
| yes | no | `recompute` |
| no | yes | `protect_hot_key` |
| no | no | `ok` |
## Output
Return a list of strings, one per classified movie, each formatted as:
```
"movie_id:action"
```
The list must be **sorted by `movie_id` in ascending order**.
## Notes
- Movie IDs are non-negative integers.
- If no movie qualifies (both `requests` and `cache_entries` are empty), return an empty list.
### Example
```
requests = [1, 2, 1, 3, 1, 2]
cache_entries = {1: [1, 4, 5], 2: [2, 7], 4: [8]}
updated_movies = [5, 7]
hot_threshold = 3
-> ["1:recompute_and_protect", "2:recompute", "3:ok", "4:ok"]
```
- Movie `1`: appears 3 times (≥ 3 → hot); dependency `5` is in `updated_movies` (stale) → `recompute_and_protect`.
- Movie `2`: appears 2 times (< 3 → not hot); dependency `7` is updated (stale) → `recompute`.
- Movie `3`: appears once (not hot) and has no cache entry (not stale) → `ok`.
- Movie `4`: never requested (not hot); dependency `8` is not updated (not stale) → `ok`.
Constraints
- 0 <= len(requests) <= 200000
- 0 <= sum(len(v) for v in cache_entries.values()) <= 200000
- 1 <= hot_threshold <= 1000000000
- Movie IDs are non-negative integers
- cache_entries may contain keys with empty dependency lists
Examples
Input: ([1, 2, 1, 3, 1, 2], {1: [1, 4, 5], 2: [2, 7], 4: [8]}, [5, 7], 3)
Expected Output: ["1:recompute_and_protect", "2:recompute", "3:ok", "4:ok"]
Explanation: Key 1 is requested 3 times and depends on updated movie 5, so it is both hot and stale. Key 2 is stale only. Key 3 is requested but not hot. Key 4 is cached but unaffected.
Input: ([5, 5, 5, 6], {2: [1], 5: [9], 6: [10]}, [11], 2)
Expected Output: ["2:ok", "5:protect_hot_key", "6:ok"]
Explanation: No cache entry is stale because updated movie 11 is not in any dependency list. Key 5 is hot because it appears 3 times, which is at least 2.
Approach
Approach. We classify every movie that shows up either in requests or as a key in cache_entries, deciding for each whether it is stale, hot, both, or neither — then sort by movie_id.
Step 1 — count request frequency. Iterate over requests once, building a counts dict (counts[movie_id] += 1). This lets us test the hot condition (count >= hot_threshold) in O(1) per key.
Step 2 — fast staleness lookup. Convert updated_movies to a set (updated_set). Membership testing against a set is O(1) average, which is what makes the dependency scan efficient.
Step 3 — collect the universe of keys. Union the cache-entry keys with the requested keys: set(cache_entries) | set(counts). This guarantees we emit an action for every relevant movie, including request-only keys (no cache entry) and cache-only keys (never requested).
Step 4 — classify, sorted. Iterate sorted(all_keys) so output is ordered by movie_id. For each key:
- stale = any(dep in updated_set for dep in deps) — true if any dependency was updated. A missing cache entry yields deps = [], so any(...) is False (correctly not stale). Empty dependency lists behave the same way.
- hot = counts.get(movie_id, 0) >= hot_threshold.
The two booleans pick the action: both → recompute_and_protect, stale only → recompute, hot only → protect_hot_key, neither → ok. We append f'{movie_id}:{action}'.
Why it's correct. Every classification is independent per key and derived directly from the two precomputed structures, and the union over both sources ensures none is dropped. The any short-circuits on the first updated dependency, so repeated or empty dependency lists are handled naturally.
Space complexity: O(Ru + Mu + U), where Ru = unique requested movie IDs (counts dict), Mu = len(updated_movies) (updated_set), and U = number of output keys (the all_keys set and the result list).
Hints
- First count how many times each movie ID appears in requests to find hot keys.
- Convert updated_movies to a set so you can test whether a cache entry is stale by scanning its dependency list once.
Community answers
Answer by sourabh.19.cse
`
public List solution(List> adj, List rating, int start, List watched, int k) {
// Edge case checks
if (k <= 0 || start < 0 || start >= adj.size()) {
return new ArrayList<>();
}
// Fast O(1) lookup for watched movies
Set watchedSet = new HashSet<>(watched);
// Track visited nodes during BFS
boolean[] visited = new boolean[adj.size()];
visited[start] = true;
Queue queue = new ArrayDeque<>();
queue.offer(start);
List recommendations = new ArrayList<>();
// BFS level by level (by graph distance)
while (!queue.isEmpty() && recommendations.size() < k) {
int layerSize = queue.size();
List currentLayerEligible = new ArrayList<>();
for (int i = 0; i < layerSize; i++) {
int curr = queue.poll();
for (int neighbor : adj.get(curr)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.offer(neighbor);
// Eligible if not watched and not the start movie
if (!watchedSet.contains(neighbor) && neighbor != start) {
currentLayerEligible.add(neighbor);
}
}
}
}
// Sort eligible movies at the current distance level:
// 1. Higher rating first
// 2. Smaller ID first
currentLayerEligible.sort((a, b) -> {
int r1 = rating.get(a);
int r2 = rating.get(b);
if (r1 != r2) {
return Integer.compare(r2, r1); // Descending rating
}
return Integer.compare(a, b); // Ascending ID
});
// Add sorted candidates to recommendations
for (int movieId : currentLayerEligible) {
recommendations.add(movieId);
if (recommendations.size() == k) {
break;
}
}
}
return recommendations;
}
Answer by Josef420
def solution(requests, cache_entries, updated_movies, hot_threshold):
key_count = Counter(requests)
key_is_hot = defaultdict(bool)
key_needs_update = defaultdict(bool)
all_keys = {key for key in cache_entries} | set(requests)
recompute_and_protect: str = "recompute_and_protect"
recompute: str = "recompute"
protect_hot_key: str = "protect_hot_key"
ok: str = "ok"
for key, count in key_count.items():
if count >= hot_threshold:
key_is_hot[key] = True
def key_get_has_changed_dependencies(node, seen):
if node in seen:
return False
if node in updated_movies:
return True
seen.add(node)
for next_node in cache_entries.get(node, []):
if key_get_has_changed_dependencies(next_node, seen):
return True
return False
for key in all_keys:
if key_get_has_changed_dependencies(key, set()):
key_needs_update[key] = True
key_classification = []
for key in sorted(all_keys):
if key_is_hot[key] and key_needs_update[key]:
status = "recompute_and_protect"
elif key_is_hot[key]:
status = "protect_hot_key"
elif key_needs_update[key]:
status = "recompute"
else:
status = "ok"
key_classification.append(f"{key}:{status}")
return key_classification
Answer by mojahidislam221
import java.util.*;
public class Solution {
public List solution(
List requests,
Map> cacheEntries,
List updatedMovies,
int hotThreshold) {
Map count = new HashMap<>();
Set updated = new HashSet<>(updatedMovies);
Set stale = new HashSet<>();
// Count requests
for (int id : requests) {
count.put(id, count.getOrDefault(id, 0) + 1);
}
// Find stale movie IDs
for (Map.Entry> entry : cacheEntries.entrySet()) {
Object key = entry.getKey();
int movie;
if(key instanceof String){
movie = Integer.parseInt(key.toString());
}else {
movie = entry.getKey();
}
for (int dep : entry.getValue()) {
if (updated.contains(dep)) {
stale.add(movie);
break;
}
}
}
// All movie IDs
Set all = new HashSet<>(requests);
all.addAll(cacheEntries.keySet());
// Sort
List ids = new ArrayList<>(all);
Collections.sort(ids);
// Generate result
List ans = new ArrayList<>();
for (int id : ids) {
boolean hot = count.getOrDefault(id, 0) >= hotThreshold;
boolean isStale = stale.contains(id);
if (hot && isStale) {
ans.add(id + ":recompute_and_protect");
} else if (isStale) {
ans.add(id + ":recompute");
} else if (hot) {
ans.add(id + ":protect_hot_key");
} else {
ans.add(id + ":ok");
}
}
return ans;
}
}