Remove Duplicates While Preserving First-Appearance Order
Company: Upstart
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
Remove duplicate values from an array while preserving the order in which each distinct value first appears.
### Function Contract
Implement `filter_duplicates(data) -> list[int]`.
Return a new array containing the first occurrence of each distinct value in the input's original order.
### Constraints and Clarifications
For a portable practice interface, values are integers.
- `data` is always an array, never null.
- `0 <= len(data) <= 200000`.
- Values range from `-1000000000` through `1000000000`.
- Equal values count as duplicates even when separated by other values.
- Do not sort the result.
- Aim for expected `O(n)` time.
### Examples
```text
data = [7, 6, 4, 3, 3, 4, 9]
Output: [7, 6, 4, 3, 9]
```
```text
data = [0, -1, 0, -1, 2]
Output: [0, -1, 2]
```
```hint Track prior appearances without changing traversal order
Decide whether to emit a value when you first encounter it. The membership structure and the ordered result have different responsibilities.
```
Overview: Return each array value once in its original first-appearance order, using membership tracking without sorting the result.
Given an array of integers `data`, return a new array containing the first occurrence of each distinct value, in the order those first occurrences appear in `data`.
Scanning `data` from left to right, a value is kept the first time it is seen and skipped on every later appearance. Two values are duplicates whenever they are equal, even when other values sit between them. Do not sort the result: the output order is exactly the order in which the kept values appear in `data`. Aim for expected `O(n)` time.
The returned array is compared exactly, element by element, and the rule above fixes a single correct answer for every input, so there are no ties to break. If `data` is empty, return an empty array. The input is not modified.
All values lie in `[-1000000000, 1000000000]`, so no value can exceed 2^31 - 1: `int` is sufficient in Java and C++, and every value is exactly representable as a JavaScript number.
### Examples
Example 1
```text
data = [7, 6, 4, 3, 3, 4, 9]
Output: [7, 6, 4, 3, 9]
```
First occurrences, in order, are 7, 6, 4 and 3; the 3 at index 4 and the 4 at index 5 repeat earlier values and are skipped; 9 is a new value and is kept.
Example 2
```text
data = [0, -1, 0, -1, 2]
Output: [0, -1, 2]
```
0 and -1 each appear twice with another value in between, and equal values count as duplicates even when separated, so only their first occurrences are kept; 2 is new.
Constraints
- `data` is always an array, never null.
- `0 <= len(data) <= 200000`.
- Values range from `-1000000000` through `1000000000`.
- Equal values count as duplicates even when separated by other values.
- Do not sort the result; it must preserve first-occurrence order.
- Aim for expected `O(n)` time.
- Values are integers (a portable practice interface); every value fits in a signed 32-bit integer.
Examples
Input: ([],)
Expected Output: []
Explanation: Minimum valid input: an empty array has no values to keep, so the result is empty.
Input: ([5],)
Expected Output: [5]
Explanation: Singleton: the only element is its own first occurrence.
Hints
- Traverse `data` once in its original order and decide about each value at the moment you first encounter it.
- Tracking which values have appeared before and building the ordered result are two different responsibilities; one structure does not have to do both.
- Re-scanning the output already built for every new element is correct but does not reach the expected O(n) time the contract asks for.