Top K Videos by Multiplicative Similarity
Google● MediumNEW GRADONSITE INTERVIEWProblem statement
A video catalog contains n videos labeled 0 through n - 1. Each row [u, v, w] of edges means videos u and v have direct similarity w in both directions.
The similarity of a path is the product of its edge weights. For each video reachable from source, use the maximum product over all paths from source to that video. Return up to k reachable video IDs other than source, ordered by decreasing maximum similarity. Break equal-score ties by smaller video ID. If fewer than k other videos are reachable, return all of them.
All graph edges are available locally for this coding exercise. The original interview also asked how to fetch a node that is not stored locally; an RPC-backed neighbor lookup is a discussion follow-up rather than a graded input.
Function
topKSimilarVideos(n: int, edges: double[][], source: int, k: int) → int[]Examples
Example 1
n = 5edges = [[0,1,0.5],[1,2,0.5],[0,3,0.25],[3,4,1.0]]source = 0k = 3return = [1, 2, 3]Video 1 scores 0.5. Videos 2, 3, and 4 each score 0.25, so the smaller IDs 2 and 3 fill the remaining slots.
Example 2
n = 3edges = [[0,1,0.25],[0,2,0.5],[2,1,1.0]]source = 0k = 2return = [1, 2]The indirect route to video 1 scores 0.5, improving its direct 0.25 link. It ties video 2 and wins by ID.
Example 3
n = 4edges = [[0,1,0.5]]source = 0k = 3return = [1]Only video 1 is reachable from video 0, so the result contains fewer than three IDs.
Example 4
n = 2edges = [[0,1,1.0]]source = 0k = 0return = []Requesting zero recommendations returns an empty array.
Constraints
2 <= n <= 200;0 <= edges.length <= n * (n - 1) / 2.- Each edge has two distinct valid video IDs, and no unordered pair occurs twice.
- Each edge weight is exactly
0.25,0.5, or1.0. 0 <= source < nand0 <= k < n.