Movie Recommendations by Jaccard Similarity
Problem statement
Each row of viewers is the set of people who watched one movie. Movie IDs are row indices. Jaccard similarity is the size of the intersection of two viewer sets divided by the size of their union.
Return up to k movie IDs with the highest Jaccard similarity to movie reference. Exclude the reference movie. For this exercise, compare the exact fractions, break equal similarities by smaller movie ID, and return IDs in that ranked order. Include zero-similarity candidates when needed to fill the result. If both viewer sets are empty, define their similarity as zero.
For this exercise, people are represented by integer IDs and viewer IDs are unique within each row. A request for zero recommendations returns an empty array; if fewer than k other movies exist, return all of them. k=1 is the reported top recommendation. k=2 is a bounded practice interpretation of the mentioned top-two follow-up, whose exact details the author did not remember.
Function
recommendMovies(viewers: int[][], reference: int, k: int) → int[]Examples
Example 1
viewers = [[0,1,2,3],[0,1,4],[1,2],[3]]reference = 0k = 1return = [2]Movie 0 is starwar, movie 1 is startrek, movie 2 is galaxy and movie 3 is firefly. People 0 through 4 stand for peter, jane, susan, tom and john. The similarities to movie 0 are 2/5=0.4, 2/4=0.5 and 1/4=0.25. Movie 2 therefore ranks first, so return [2].
Example 2
viewers = [[],[],[1],[2]]reference = 0k = 3return = [1,2,3]The empty reference shares no person with another movie. The two empty sets also have similarity zero by the practice rule. All three candidates tie at zero, so increasing movie IDs give [1,2,3].
Constraints
1 <= viewers.length <= 2000 <= viewers[i].length <= 10000 <= viewers[i][j] <= 1000000. Each row contains distinct person IDs.0 <= reference < viewers.length0 <= k <= 200