Remove Global Duplicates While Preserving Order
Company: Vanta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Remove Global Duplicates While Preserving Order
Implement `global_unique(values)`.
`values` is a list of strings. Return a new list containing the first occurrence of every distinct string and omit all later occurrences, even when equal values are not adjacent. The relative order of the retained values must be exactly the same as in the input.
String comparison is case-sensitive. Do not modify the input list.
## Examples
- `global_unique(["a", "b", "a", "c", "b"])` returns `["a", "b", "c"]`.
- `global_unique([])` returns `[]`.
- `global_unique(["x", "x", "x"])` returns `["x"]`.
## Constraints
- `0 <= len(values) <= 200_000`
- Each value is a valid Python string.
## Discussion follow-up
After implementing the in-memory version, explain how you would process an input too large to fit in memory by partitioning work while still emitting the retained values in their original order.
Overview: Practice removing duplicate strings globally while preserving first-seen order and leaving the input unchanged. Consider how the design changes when the input is too large to fit in memory.
Implement global_unique(values). Given a list of strings, return a new list containing only the first occurrence of each distinct string. Equality is case-sensitive, later duplicates may be non-adjacent, retained values keep their original order, and the input must not be modified. Non-graded discussion follow-up: explain how you would partition an input too large to fit in memory while still emitting retained values in original order.
Constraints
- 0 <= len(values) <= 200,000
- Every element is a string.
- String comparison is case-sensitive.
Examples
Input: ([],)
Expected Output: []
Explanation: Covers first-occurrence retention and stable order.
Input: (['a'],)
Expected Output: ['a']
Explanation: Covers first-occurrence retention and stable order.
Hints
- Track values already retained in a hash set.
- Append a value only when it is first inserted into the set.
- Discussion only: a partitioned external-memory design must preserve the global first position of every value before its ordered emit phase.