Pick the highest-scoring movie row by top-k similarity

A user just finished a movie they liked. Your recommender already scored every other title for how similar it is to that movie, and the catalog is split into curated groups (rows on the home screen). Pick the row to show first.

Implement:

def highest_scoring_group(similarity: list[float], groups: list[list[int]], k: int) -> int

• similarity[i] is the similarity between the source movie and movie i (movie IDs are 0..n-1). Scores are floats and may be negative.
• groups[g] is a list of movie IDs. A movie can appear in several groups.
• A group's score is the sum of the k highest similarity scores among its distinct movies. If a group has fewer than k distinct movies, sum all of them. An empty group scores 0.

Return the index of the group with the highest score. Break ties by the smaller index. Return -1 if there are no groups.

Constraints: 1 <= n <= 10^5, 0 <= len(groups) <= 10^4, total group memberships up to 10^6, 1 <= k <= 1000. Aim for better than sorting every group.

Example 1

similarity = [0.9, 0.1, 0.4, 0.8, 0.3, 0.75]
groups     = [[0, 1, 2], [3, 5, 4], [1, 4]]
k = 2

Group scores are 0.9 + 0.4 = 1.3, 0.8 + 0.75 = 1.55 and 0.1 + 0.3 = 0.4. Return 1. With k = 1 the scores are 0.9, 0.8 and 0.3, so return 0.

Example 2

similarity = [-0.2, -0.7]
groups     = [[1], [0, 0]]
k = 3

The repeated movie counts once. Scores are -0.7 and -0.2. Return 1.

Reconstructed from the reported question; details may differ from what interviewers ask.