Efficient Lookups and Deduplication

EasyPython

Problem

Mistral AI's inference gateway receives batches of request IDs, which may contain retries and IDs already processed. Implement an efficient lookup routine that summarizes the batch without changing the order of first appearance.

Given request_ids and known_ids, return a dictionary with three results:

unique_ids: every ID from request_ids, appearing once in first-seen order.
duplicate_ids: IDs that occur at least twice in request_ids, appearing once in the order of their first occurrence.
new_ids: IDs from unique_ids that are not present in known_ids, preserving order.

Use sets or dictionaries to achieve linear expected time. Do not sort the input, because ordering is significant.

Formal Specification

Input: request_ids, a list of strings, and known_ids, a list of strings.
Output: a dictionary with keys unique_ids, duplicate_ids, and new_ids; each value is a list of strings.
IDs are compared using exact, case-sensitive string equality.

Constraints

0 <= len(request_ids), len(known_ids) <= 10^5
Each ID is a non-empty string of at most 128 characters
IDs are compared using exact, case-sensitive equality
Ordering is determined by first appearance in request_ids

Function Signature

def summarize_request_ids(request_ids, known_ids):

Given request_ids and known_ids, return a dictionary with three results:

unique_ids: every ID from request_ids, appearing once in first-seen order.
duplicate_ids: IDs that occur at least twice in request_ids, appearing once in the order of their first occurrence.
new_ids: IDs from unique_ids that are not present in known_ids, preserving order.

Use sets or dictionaries to achieve linear expected time. Do not sort the input, because ordering is significant.

Formal Specification

Input: request_ids, a list of strings, and known_ids, a list of strings.
Output: a dictionary with keys unique_ids, duplicate_ids, and new_ids; each value is a list of strings.
IDs are compared using exact, case-sensitive string equality.