Rank Items by Dot-Product Similarity to a User Embedding, Excluding Seen Items

A recommendation model represents a user and each candidate item as embedding vectors of the same dimension. The similarity score of an item is the dot product of the user's embedding and the item's embedding; a higher score means a more similar item. Given the user's embedding and the embeddings of $N$ items, return the item indices sorted from the highest score to the lowest. Follow-up from the same round: the user has already seen some of the items. Leave those items out of the ranked result. In the interview this was to be written with NumPy. Here the inputs are plain lists. ### Function Signature ```python def rank_items(user: list[int], items: list[list[int]], seen: list[int]) -> list[int]: ``` `user` is the user's embedding of dimension `d`, `items[i]` is the embedding of item `i`, and `seen` lists the indices of the items the user has already seen. ### Rules - The score of item `i` is `sum(user[j] * items[i][j] for j in range(d))`. - Return the indices of all items that are not in `seen`, ordered by score from highest to lowest. - Items with equal scores are ordered by index, smallest first. - If `seen` is empty, every item is ranked. If every item has been seen, return an empty list. - Embedding components are integers in this version, so scores are exact and ties are well defined. ### Constraints - `1 <= d <= 128`, where `d = len(user)`, and every `items[i]` has length `d`. - `1 <= len(items) <= 10^4` - Every component of `user` and of every `items[i]` is an integer in `[-1000, 1000]`, so every score lies in `[-1.28 * 10^8, 1.28 * 10^8]`. - `0 <= len(seen) <= len(items)`; the indices in `seen` are distinct, and each lies in `[0, len(items) - 1]`. ### Examples **Example 1** ```text Input: user = [1, 2], items = [[3, 0], [1, 1], [0, 2], [-1, 4]], seen = [] Output: [3, 2, 0, 1] ``` The scores are 3, 3, 4 and 7 for items 0 to 3. Item 3 ranks first and item 2 second. Items 0 and 1 tie at 3, so the smaller index comes first. **Example 2** ```text Input: user = [1, 2], items = [[3, 0], [1, 1], [0, 2], [-1, 4]], seen = [2, 0] Output: [3, 1] ``` Same scores as Example 1, but items 2 and 0 have been seen and are removed. **Example 3** ```text Input: user = [2, -1, 0], items = [[1, 1, 5], [0, 3, 1], [2, 4, -3], [-1, -5, 7]], seen = [3] Output: [0, 2, 1] ``` The scores are 1, -3, 0 and 3. Item 3 has the highest score but has been seen, so the result ranks items 0, 2 and 1.