Deduplicate a Retrieval Result List
Problem Statement
A retrieval index built from augmented or near-duplicate images returns the same underlying item under several ids. Collapse the ranked list to unique items — keeping each item's best (earliest) position — then take the top-K.
Background
Given a ranked list of (item_id, score) results (best first) where item_id may repeat, produce the deduplicated top-K: for each distinct item_id, keep only its first occurrence (highest rank), preserve the original order, and return the first K ids. This mirrors post-processing a retrieval system before showing results to a user, so the same photo does not fill the page.
Your Task
Implement:
def dedup_topk(results, k):
- results: list of (item_id, score) tuples, already sorted best-first.
Return the list of the first K distinct item ids in order.
Input Format
- results: list of (item_id, score).
- k (int).
Output Format
- A list of item ids (length min(K, num_distinct)).
Sample
print(dedup_topk([(5, 0.9), (5, 0.8), (3, 0.7), (2, 0.6)], 2))
Output:
[5, 3]
Example:
print(dedup_topk([(5, 0.9), (5, 0.8), (3, 0.7), (2, 0.6)], 2))
[5, 3]
- Initialize an empty set to track seen items and an empty list for the result, since we need to preserve the first occurrence of each unique ID.
- Process the first result (5,0.9): ID 5 is not in the seen set, so add 5 to the seen set and append 5 to the result list; the result is now [5].
- Process the second result (5,0.8): ID 5 is already in the seen set, so skip this entry to avoid duplicates.
- Process the third result (3,0.7): ID 3 is not in the seen set, so add 3 to the seen set and append 3 to the result list; the result is now [5,3].
- The result list length is now 2, which matches the target K=2, so stop processing further items (skipping (2,0.6)).
- The final output is [5, 3]
Constraints:
0 <= len(results) <= 100000,k >= 0.- Keep each item's earliest occurrence; preserve order.
- Return at most
Kids.
1. Background Knowledge
In retrieval-augmented generation and vision-language models, a query is matched against a large index of items (images, documents, embeddings). Because indices are often built from augmented data—cropped, resized, or slightly perturbed versions of the same source image—the top of the ranked list frequently contains multiple entries that point to the same underlying entity. If you display these raw results, the user sees the same photo five times, which is both confusing and wasteful.
The standard post-processing step is reciprocal rank fusion or, more simply, deduplication by identity. The goal is to collapse the list so each distinct item appears exactly once, at its best (earliest) rank. This preserves the ranking signal: if item 5 appears at positions 1 and 2, we keep position 1 and discard position 2. The operation is order-preserving and idempotent.
This pattern generalizes to any scenario where you have a stream of labeled records and need the first occurrence of each label. It is closely related to stable deduplication in databases and unique-by-key operations in dataframes.
2. Algorithm Approach
The problem is a classic single-pass, first-occurrence filter. Because the input is already sorted best-first, the first time you see an item_id is its optimal position. You do not need to sort, re-rank, or compare scores—only track which ids you have already emitted.
The core data structure is a set for O(1) membership testing. Iterate through the ranked list; for each (item_id, score), check if item_id is in the seen set. If not, add it to the result list and mark it as seen. Stop early once the result list reaches length K.
This is a greedy approach: at each step, you make the locally optimal choice (keep the earliest unseen id), which is globally optimal because the input order already encodes the ranking.
3. Step-by-Step Strategy
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.