Highest-Rated Movie Among Transitively Similar Movies
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
A movie catalog has `k` movies, numbered `0` to `k - 1`, and every movie has a rating. Some pairs of movies are marked as similar, and similarity carries over through chains of similar pairs. Given one movie, return the highest-rated movie that is similar to it.
### Function Signature
```python
def best_similar_movie(ratings: list[int], pairs: list[list[int]], movie: int) -> int:
```
### Rules
- `ratings[i]` is the rating of movie `i`, and `k = len(ratings)`.
- `pairs[j] = [a, b]` means that movies `a` and `b` are directly similar.
- Similarity is symmetric and transitive: if `a` is similar to `b` and `b` is similar to `c`, then `a` is similar to `c`, even when `[a, c]` is not listed.
- The given movie is never a candidate itself, even when its own rating is the highest among the similar movies.
- Return the id of the highest-rated movie similar to `movie`. If several similar movies share the highest rating, return the smallest id among them.
- Return `-1` when no other movie is similar to `movie`.
### Constraints
- `1 <= k <= 10^5`
- `0 <= len(pairs) <= 2 * 10^5`
- `0 <= a, b < k` and `a != b` for every pair; the same pair may appear more than once, in either order.
- `0 <= ratings[i] <= 10^9`, integers, so every value fits in a 32-bit signed integer.
- `0 <= movie < k`
### Examples
**Example 1**
```text
Input: ratings = [6, 4, 9, 10, 7], pairs = [[0, 1], [1, 2], [3, 4]], movie = 0
Output: 2
```
Movie `0` is similar to movie `1` directly and to movie `2` through movie `1`. Of those two, movie `2` has the higher rating, `9`. Movie `3` has the highest rating overall but is not similar to movie `0`.
**Example 2**
```text
Input: ratings = [9, 8, 8, 1], pairs = [[2, 0], [0, 1]], movie = 0
Output: 1
```
Movies `1` and `2` are both similar to movie `0` and tie at rating `8`, so the smaller id, `1`, is returned. Movie `0`'s own rating of `9` does not count, and movie `3` is not similar to it.
**Example 3**
```text
Input: ratings = [4, 2], pairs = [], movie = 1
Output: -1
```
No movie is similar to movie `1`.
Overview: A graph coding problem about a movie catalog in which similarity carries over through chains of similar pairs. Given every movie's rating, the similarity pairs and one movie, return the highest-rated other movie in its similarity group, breaking ties by the smallest id. It tests graph traversal and grouping of connected items.
Read the full Google Software Engineer interview experience this question came from
A movie catalog has `k` movies, numbered `0` to `k - 1`, and `ratings[i]` is the rating of movie `i` (so `k = len(ratings)`). Each entry `pairs[j] = [a, b]` means that movies `a` and `b` are directly similar. Similarity is symmetric and transitive: if `a` is similar to `b` and `b` is similar to `c`, then `a` is similar to `c`, even when `[a, c]` is not listed.
Implement `best_similar_movie(ratings, pairs, movie)`, which returns the id of the highest-rated movie that is similar to `movie`.
- The given movie is never a candidate itself, even when its own rating is the highest among the movies similar to it.
- If several similar movies share the highest rating, return the smallest id among them.
- Return `-1` when no other movie is similar to `movie`.
### Constraints
- `1 <= k <= 10^5`
- `0 <= len(pairs) <= 2 * 10^5`
- `0 <= a, b < k` and `a != b` for every pair; the same pair may appear more than once, in either order.
- `0 <= ratings[i] <= 10^9`, integers. Every rating and every returned id fits in a 32-bit signed integer (no value exceeds 2^31 - 1), so `int` is enough in Java and C++.
- `0 <= movie < k`
### Example 1
```text
Input: ratings = [6, 4, 9, 10, 7], pairs = [[0, 1], [1, 2], [3, 4]], movie = 0
Output: 2
```
Movie `0` is similar to movie `1` directly and to movie `2` through movie `1`. Of those two, movie `2` has the higher rating, `9`. Movie `3` has the highest rating overall but is not similar to movie `0`.
### Example 2
```text
Input: ratings = [9, 8, 8, 1], pairs = [[2, 0], [0, 1]], movie = 0
Output: 1
```
Movies `1` and `2` are both similar to movie `0` and tie at rating `8`, so the smaller id, `1`, is returned. Movie `0`'s own rating of `9` does not count, and movie `3` is not similar to it.
Constraints
- 1 <= k <= 10^5, where k = len(ratings)
- 0 <= len(pairs) <= 2 * 10^5
- 0 <= a, b < k and a != b for every pair [a, b]; the same pair may appear more than once, in either order.
- 0 <= ratings[i] <= 10^9, integers; every rating and every returned id fits in a 32-bit signed integer (no value exceeds 2^31 - 1).
- 0 <= movie < k
Examples
Input: ([5], [], 0)
Expected Output: -1
Explanation: Minimum valid input: k = 1 with no pairs, so no other movie exists and the answer is -1.
Input: ([4, 2], [], 1)
Expected Output: -1
Explanation: Source example 3: no pairs, so no movie is similar to movie 1.
Hints
- Similarity carries through chains of pairs, so a movie can be similar to `movie` without ever appearing in a pair with it. First determine the full set of movies that end up similar to `movie`.
- Every pair works in both directions, and a repeated pair adds nothing new.
- `movie` itself never counts, a rating of 0 can still be the best rating, and ties at the top go to the smallest id.