The First of Their Kind

An easy Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
easy
Seniority
L3
Asked in
Amazon

Problem

An ingestion feed hands you records in arrival order, and the same key value can reappear whenever an upstream producer retries a record it already sent. The feed can run to millions of records, so in a single pass keep only the first record for each distinct value of key, never rescanning the ones you have already kept.

When the same record arrives twice, only the first one survives.

Example 1

Input:

records = [{"user":"mona","event_id":"a1"},{"user":"raj","event_id":"a2"},{"user":"mona-retry","event_id":"a1"},{"user":"ivy","event_id":"a3"}], key = "event_id"

Output:

[{"user":"mona","event_id":"a1"},{"user":"raj","event_id":"a2"},{"user":"ivy","event_id":"a3"}]

Example 2

Input:

records = [{"user":"lia","event_id":"b1"},{"user":"no-id-1"},{"user":"lia-dup","event_id":"b1"},{"user":"no-id-2"}], key = "event_id"

Output:

[{"user":"lia","event_id":"b1"},{"user":"no-id-1"},{"user":"no-id-2"}]

Worked solution and explanation

What this really is

This is a first-occurrence dedup dressed up as a feed cleanup. The skill being probed: can you use an O(1) set lookup to avoid the O(n^2) trap of scanning the result list on every record? Anyone can keep a list and ask 'have I seen this'. The trick is doing that check in constant time while preserving the order records first appeared, and not tripping over records that have no key at all. Get it wrong and either the cleanup slows quadratically on a big retry-heavy feed, or a retried record with changed fields slips through as a false unique.

Break down the requirements

Step 1: Track seen key values in a set

Membership is the only question you ask of past records, so keep just the key values in a set and get that answer in O(1) instead of rereading what you kept.

Step 2: Keep the first occurrence of each key value

Iterate through records in order. If the key value is new, add the record to the result and mark the value as seen.

Step 3: Skip duplicates, but keep records missing the key

If the key value is already in the seen set, skip the record. Records that lack the key entirely are not deduplicated against each other, so keep every one of them in order.

The solution

Set-based dedup preserving first occurrence
def deduplicate(records, key):
    seen = set()
    result = []
    for record in records:
        if key not in record:
            # No key to dedup on; keep it in order.
            result.append(record)
            continue
        value = record[key]
        if value not in seen:
            seen.add(value)
            result.append(record)
    return result

Common follow-up questions