InternDoor

Movie ratings where critics count double

Harddesign · hash map · sortingDesign a class

Reported in interviews at (where)

Build MovieRatings, which takes star ratings for movies and names the best-rated ones. Users and movies are numbered.

A user who has rated 3 or more movies is a critic, and every rating a critic has given counts twice, including the ratings they gave before they became one. A movie's average is then its weighted average: each critic's stars count twice, everyone else's once.

MovieRatings() starts with no ratings.

rate(user, movie, stars) records that user gave movie between 1 and 5 stars. A user rates a movie at most once.

topMovies(k) returns the k movies with the highest average, highest first, or every rated movie if fewer than k have been rated. Movies with the same average go in order of their number, smallest first. A movie nobody has rated is never listed.

Example 1
Input
["MovieRatings","rate","rate","rate","topMovies","rate","rate","topMovies","topMovies"]
[[],[1,10,5],[2,20,4],[2,10,2],[2],[1,40,3],[1,50,3],[3],[9]]
Output
[null,null,null,null,[20,10],null,null,[10,20,40],[10,20,40,50]]

At first movie 10 averages (5 + 2) / 2 = 3.5. User 1's third rating makes them a critic, so their 5 stars now count twice: (5 + 5 + 2) / 3 = 4, level with movie 20, and the smaller number goes first. Movies 40 and 50 both average 3.

Example 2
Input
["MovieRatings","topMovies","rate","rate","topMovies"]
[[],[3],[7,2,2],[8,1,2],[3]]
Output
[null,[],null,null,[1,2]]

With nothing rated the list is empty. Two movies with the same average are listed by number.

Limits

  • 1 <= user <= 5000
  • 1 <= movie <= 500
  • 1 <= stars <= 5
  • 1 <= k <= 10
  • a user rates a movie at most once
  • at most 20000 calls after the constructor

Hints

Hint 1

Keep each movie's weighted total of stars and its total weight: the average is one divided by the other, and every rating changes them in O(1).

Hint 2

A user becomes a critic exactly once, at their third rating. Only their first two ratings need raising then: remember them, and add each one's stars and weight once more.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.