# The First of Their Kind > When the same record arrives twice, only the first one survives. Canonical URL: Domain: Python · Difficulty: easy · Seniority: L3 ## 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. ## 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 using a set A set provides O(1) membership checking to determine if a record's key value has been encountered before. #### 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** ```python 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 ``` > **Time and Space Complexity** > > **Time:** O(n) where n is the number of records. Each record is checked once. > > Space: O(k) where k is the number of unique key values, for the seen set. > **Interviewers Watch For** > > Do you use a set rather than checking the result list for duplicates? Using `value in result_list` is O(n) per check, making the overall approach O(n^2). > **Common Pitfall** > > Deduplicating by the entire record instead of the specified key field. Two records with the same key value but different other fields should still be collapsed based on that value. --- ## Common follow-up questions - What if you wanted to keep the last occurrence instead of the first? _(Tests reversing the input, deduplicating, then reversing the result.)_ - What if records could have composite keys (multiple fields)? _(Tests using a tuple of field values as the dedup key.)_ - How would you handle this for a 100GB dataset that does not fit in memory? _(Tests external sorting with merge-based deduplication.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/the_first_of_their_kind) - [Python Interview Questions](https://datadriven.io/python-interview-questions) - [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep) - [Daily Challenge](https://datadriven.io/daily) --- Source: DataDriven (https://datadriven.io). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.