Problem 174862 · hard · Level 01 Prerequisites & Setup

What Should I Watch Next?

cosine similarity · k most similar · weighted sum · dictionaries · ranking

A film club keeps everyone's star ratings: ratings[u] is a dictionary {film: stars} for viewer u, with stars from 1 to 5. A film a viewer has not rated is missing from their dictionary. The club wants to suggest films to viewer me, using the viewers whose ratings look most like theirs.

  1. Similarity. The similarity of two viewers is the cosine similarity of their rating dictionaries, with a missing film counting as 0: the sum over shared films of the product of the two ratings, divided by the product of the two Euclidean lengths. A viewer with no ratings has similarity 0 with everybody.
  2. Neighbours. The neighbours of me are the k other viewers with the highest similarity, counting only viewers with a similarity greater than 0. Break ties by the smaller viewer index. If fewer than k viewers qualify, use all of them.
  3. Scores. Every film that me has not rated and at least one neighbour has rated gets a score: the sum, over the neighbours who rated it, of similarity × stars.
  4. Suggestions. Return the m films with the highest scores, best first (fewer if there are fewer candidates). Break ties by film name in alphabetical order.

So that ties are reproducible on every device, round every similarity to 9 decimal places as soon as you compute it (and use the rounded values in the scores), and round every score to 9 decimal places before comparing scores.

The tests build rating tables with film_ratings(n_users, n_films, seed), which is available in your code.

Examples

Input:  ratings = [{"alien": 5, "brave": 1},
                   {"alien": 4, "brave": 1, "coco": 2, "dune": 5},
                   {"brave": 5, "coco": 5},
                   {"alien": 5, "dune": 4, "elf": 1}]
        me = 0, k = 2, m = 3
Output: ["dune", "coco", "elf"]
Explanation: viewer 0 has similarity 0.607 with viewer 1, 0.139 with viewer 2 and 0.757 with
viewer 3, so the two neighbours are viewers 3 and 1. Viewer 0 has already seen alien and brave.
dune scores 0.757 · 4 + 0.607 · 5 = 6.06, coco 0.607 · 2 = 1.21 and elf 0.757 · 1 = 0.76.

Input:  ratings = [{}, {"alien": 3}], me = 0, k = 1, m = 2
Output: []
Explanation: a viewer with no ratings is similar to nobody, so there are no neighbours.

Constraints

  • 1 <= len(ratings) <= 2000, at most 60 different films, 0 <= me < len(ratings)
  • 1 <= k <= 50, 1 <= m <= 10

Goals

  • Find the k vectors most similar to a query by cosine similarity
  • Combine the neighbours' ratings into a score weighted by similarity
  • Rank candidates with a precise, reproducible tie rule
Starting Python…