Quick 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.

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

  1. 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.
  2. 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?
  3. 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.

Loading coding console...

Show the approach

Approach

Treat every distinct value as a node and add a directed edge a -> b for every pair of adjacent elements a, b in each input sequence. The relative order of one sequence is exactly the transitive closure of its adjacent pairs, so an input sequence is a subsequence of a candidate exactly when all of its adjacent-pair edges point forward; a valid consolidation is therefore exactly a topological order of this graph. A value repeated inside one sequence produces a closed walk (a self-loop when the copies are adjacent), hence a cycle, so no topological order exists and the answer is [].

To get the lexicographically smallest order, build it greedily from left to right: keep a min-heap of values whose remaining in-degree is zero (every required predecessor is already placed), repeatedly pop the smallest, append it, and decrement the in-degree of its successors, pushing any that reach zero. Values are mapped to their rank in sorted order, so comparing ranks in the heap compares numeric values. Invariant: while a consolidation exists, the placed prefix is the prefix of some valid consolidation. Any valid continuation must put one of the currently available values next; placing the smallest available value v keeps the remainder completable (removing a source from an acyclic graph leaves it acyclic), and every candidate that puts a larger value at this position is lexicographically larger. So the greedy choice is optimal at every position.

If the heap empties before every value is placed, each remaining value still has an unplaced predecessor, so the remaining subgraph contains a cycle and no consolidation exists: return []. Repeated edges (from duplicate sequences or from a pair shared by several sequences) are counted once per occurrence in the in-degree and decremented once per occurrence, so they never block a value forever or release it early. Edge cases: a single value, a single sequence (returned unchanged), identical sequences, and adjacent or non-adjacent repeats inside one sequence.

Time complexity:
O(T log T), where T is the total number of elements over all sequences
Space complexity:
O(T)