Remove Duplicate Integers While Preserving Order
Company: Upstart
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Take-home Project
# Remove Duplicate Integers While Preserving Order
Return the distinct integers from an input list in the order of their first appearance.
### Function Signature
```python
def stable_unique(values: list[int]) -> list[int]:
...
```
### Example
```text
Input: [3, 5, 5, 7, 8, 8, 9]
Output: [3, 5, 7, 8, 9]
```
### Constraints
- `0 <= len(values) <= 1_000_000`
- Values are signed 64-bit integers.
### Clarifications
- Keep the first copy of each value and discard later copies.
- Return a new list and do not mutate `values`.
- An empty input returns `[]`.
### Hints
- Separate the data structure used for membership checks from the list used for output order.
Quick Answer: Remove duplicate integers while preserving the order of their first appearances. Use a membership set alongside a separate output list for linear expected time, retain the first copy, return a new list, and handle up to one million values.
Return each distinct integer once, ordered by its first appearance in the input.
Constraints
- 0 <= len(values) <= 1000000
- Values fit signed 64-bit integers
- Return a new list without mutating values
Examples
Input: []
Expected Output: []
Explanation: Empty input stays empty.
Input: [3, 5, 5, 7, 8, 8, 9]
Expected Output: [3, 5, 7, 8, 9]
Explanation: The first occurrence order is preserved.
Hints
- Use one structure for membership and another for ordered output.
- Append only when a value has not been seen.