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]`

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`.