Merge Integer Sequences into One Duplicate-Free Order, Lexicographically Smallest
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given several sequences of integers. Decide whether they can be consolidated into one sequence that contains no repeated number and keeps the relative order of the numbers in every input sequence. For example, `1, 2, 15, 8` and `2, 4, 7, 8` can be consolidated, for instance into `1, 2, 15, 4, 7, 8`. If a consolidation exists, return the lexicographically smallest one; otherwise return an empty list.
The interview first asked only whether a consolidation exists and later asked for the lexicographically smallest one; this version returns the latter, so an empty result answers the first question. A further follow-up, under what condition the consolidation is unique, was a discussion question and is not graded here.
### Function Signature
```python
def merge_sequences(sequences: list[list[int]]) -> list[int]:
```
### Rules
- A valid consolidation contains every distinct value that appears in any input sequence exactly once, and no other values.
- Every input sequence must be a subsequence of it: if `a` appears before `b` in an input sequence, then `a` appears before `b` in the consolidation. The elements need not be adjacent.
- A sequence that contains the same value twice can never be satisfied, because the consolidation holds each value once; in that case return `[]`.
- If at least one valid consolidation exists, return the lexicographically smallest one: two candidates are compared at the first position where they differ, by numeric value. All valid consolidations have the same length.
- If none exists, return `[]`. Every input sequence is nonempty, so a valid consolidation is never empty and `[]` is unambiguous.
### Constraints
- `1 <= len(sequences) <= 10^4`
- `1 <= len(s)` for every sequence `s`, and the total number of elements over all sequences is at most `2 * 10^5`
- `-10^9 <= value <= 10^9`
- Values may repeat across sequences, and the same sequence may appear more than once.
### Examples
**Example 1**
```text
Input: sequences = [[1, 2, 15, 8], [2, 4, 7, 8]]
Output: [1, 2, 4, 7, 15, 8]
```
Every valid consolidation starts with 1, 2 (1 precedes 2, and 2 precedes every other value) and ends with 8 (which follows 15 and 7). The middle interleaves 15 with 4, 7, giving `[1, 2, 15, 4, 7, 8]`, `[1, 2, 4, 15, 7, 8]` and `[1, 2, 4, 7, 15, 8]`; the last is the smallest.
**Example 2**
```text
Input: sequences = [[1, 2], [2, 1]]
Output: []
```
The first sequence needs 1 before 2 and the second needs 2 before 1.
**Example 3**
```text
Input: sequences = [[1, 2], [1, 2]]
Output: [1, 2]
```
Repeating the same sequence adds no new ordering requirement.
Overview: Given several integer sequences, decide whether they can be merged into one sequence without repeated numbers that keeps every input's relative order, and return the lexicographically smallest such merge or an empty list. It tests reasoning about ordering constraints, detecting impossible inputs and tie-breaking.
Read the full Google Software Engineer interview experience this question came from
You are given a list `sequences` of nonempty integer sequences. Decide whether they can be consolidated into one sequence that contains no repeated number and keeps the relative order of the numbers in every input sequence. If a consolidation exists, return the lexicographically smallest one; otherwise return an empty list.
A **valid consolidation** satisfies both rules:
- It contains every distinct value that appears in any input sequence exactly once, and no other values.
- Every input sequence is a subsequence of it: if `a` appears before `b` in an input sequence, then `a` appears before `b` in the consolidation. The elements need not be adjacent.
A sequence that contains the same value twice can never be satisfied, because the consolidation holds each value once; in that case return `[]`.
If at least one valid consolidation exists, return the lexicographically smallest one: two candidates are compared at the first position where they differ, by numeric value (so `-5` comes before `-1`, and `9` before `10`). All valid consolidations have the same length. If none exists, return `[]`. Every input sequence is nonempty, so a valid consolidation is never empty and `[]` is unambiguous; an empty result also answers the simpler question of whether any consolidation exists.
**Example 1**
```text
Input: sequences = [[1, 2, 15, 8], [2, 4, 7, 8]]
Output: [1, 2, 4, 7, 15, 8]
```
Every valid consolidation starts with 1, 2 (1 precedes 2, and 2 precedes every other value) and ends with 8 (which follows 15 and 7). The middle interleaves 15 with 4, 7, giving `[1, 2, 15, 4, 7, 8]`, `[1, 2, 4, 15, 7, 8]` and `[1, 2, 4, 7, 15, 8]`; the last is the smallest.
**Example 2**
```text
Input: sequences = [[1, 2], [2, 1]]
Output: []
```
The first sequence needs 1 before 2 and the second needs 2 before 1, so no valid consolidation exists.
**Constraints**
- `1 <= len(sequences) <= 10^4`
- `1 <= len(s)` for every sequence `s`, and the total number of elements over all sequences is at most `2 * 10^5`
- `-10^9 <= value <= 10^9` (every value fits in a signed 32-bit integer; no value exceeds `2^31 - 1`)
- Values may repeat across sequences, and the same sequence may appear more than once.
Constraints
- 1 <= len(sequences) <= 10^4
- 1 <= len(s) for every sequence s, and the total number of elements over all sequences is at most 2 * 10^5
- -10^9 <= value <= 10^9 (every value fits in a signed 32-bit integer)
- Values may repeat across sequences, and the same sequence may appear more than once.
Examples
Input: ([[1, 2, 15, 8], [2, 4, 7, 8]],)
Expected Output: [1, 2, 4, 7, 15, 8]
Explanation: Source example 1: 1, 2 are forced first and 8 last; 4, 7 go before 15 because 4 < 15. Regression: the valid but larger order [1, 2, 15, 4, 7, 8] (e.g. from a FIFO queue) is rejected.
Input: ([[1, 2], [2, 1]],)
Expected Output: []
Explanation: Source example 2: two sequences demand opposite orders of 1 and 2, a two-sequence contradiction cycle.
Hints
- Two values that sit next to each other in an input sequence give one ordering requirement; every other requirement of that sequence follows from those adjacent pairs.
- Build the answer one position at a time: which values are allowed to occupy the next position given what is already placed, and which of them should you pick to keep the result as small as possible?
- If at some point no remaining value is allowed at the next position, ask what the remaining requirements must contain. A value repeated inside one sequence is one way this happens.