Return the Earliest ID Seen Exactly Once
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Maintain the earliest ID that has been posted exactly once so far. Support posting an ID and querying the current earliest single visit.
Implement `earliest_single_visits(operations: int[][]) -> int[]`.
### Constraints & Assumptions
- A row `[0,id]` represents `post(id)`. A row `[1]` represents `getEarliestSingleVisit()`.
- IDs are integers from 0 through 1000000; -1 is reserved for no qualifying ID.
- At most 300000 operations. Return one integer for each query, in query order; posting produces no output entry.
- “Earliest” means earliest first-post position among IDs whose total count is exactly one. Once an ID has been posted twice, it never qualifies again.
- All state fits in memory. Aim for O(1) query time and amortized O(1) posting time. Explain whether your chosen implementation instead shifts amortized cleanup work into queries.
### Example
```text
operations = [[0,1],[0,3],[1],[0,1],[0,5],[1]]
result = [1,3]
```
```text
operations = [[1],[0,7],[0,7],[1],[0,7],[1]]
result = [-1,-1,-1]
```
The reported follow-up suggests pruning repeated IDs from a queue's head. Explain the invariant that makes its head the earliest remaining single ID and why total pruning work is amortized linear. If strict O(1) getters are required, decide when that pruning must occur. Compare with maintaining only unique IDs in an ordered linked structure.
```hint An ID only stops being unique once
Counts tell you whether a candidate still qualifies. Each queued candidate can be discarded permanently when it reaches the head and is no longer unique.
```
Overview: Maintain the earliest single-visit ID with counts and queue pruning, handling permanent duplicates, empty results, and strict versus amortized constant-time queries.
Read the full Uber Software Engineer interview experience this question came from
Maintain the earliest ID that has been posted exactly once so far. Support posting an ID and querying the current earliest single visit.
Implement `earliest_single_visits(operations: int[][]) -> int[]`.
### Constraints & Assumptions
- A row `[0,id]` represents `post(id)`. A row `[1]` represents `getEarliestSingleVisit()`.
- IDs are integers from 0 through 1000000; -1 is reserved for no qualifying ID.
- At most 300000 operations. Return one integer for each query, in query order; posting produces no output entry.
- “Earliest” means earliest first-post position among IDs whose total count is exactly one. Once an ID has been posted twice, it never qualifies again.
- All state fits in memory. Aim for O(1) query time and amortized O(1) posting time. Explain whether your chosen implementation instead shifts amortized cleanup work into queries.
### Example
```text
operations = [[0,1],[0,3],[1],[0,1],[0,5],[1]]
result = [1,3]
```
```text
operations = [[1],[0,7],[0,7],[1],[0,7],[1]]
result = [-1,-1,-1]
```
The reported follow-up suggests pruning repeated IDs from a queue's head. Explain the invariant that makes its head the earliest remaining single ID and why total pruning work is amortized linear. If strict O(1) getters are required, decide when that pruning must occur. Compare with maintaining only unique IDs in an ordered linked structure.
```hint An ID only stops being unique once
Counts tell you whether a candidate still qualifies. Each queued candidate can be discarded permanently when it reaches the head and is no longer unique.
```
Constraints
- At most 300000 operations, each [0,id] for a post or [1] for a query.
- IDs are integers 0 through 1000000; return -1 when no ID has count exactly one.
- Earliest means earliest first-post position among currently unique IDs.
- An ID posted twice is permanently disqualified. Return one integer per query only.
Examples
Input: ([[0, 1], [0, 3], [1], [0, 1], [0, 5], [1]],)
Expected Output: [1, 3]
Explanation: Queries choose earliest surviving first-post position.
Input: ([[1], [0, 7], [0, 7], [1], [0, 7], [1]],)
Expected Output: [-1, -1, -1]
Explanation: Repeated IDs never regain eligibility.