Recommend top-K movies from similarity graph

Q: Recommend top-K movies from similarity graph

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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

Prefer movies with smaller graph distance (fewer similarity hops) from start .
If distances tie, prefer higher rating .
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?