Check Whether Two Ordered Sequences Can Be Merged
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given two arrays of integer labels, `a` and `b`. The order of labels in each array gives ordering constraints: an earlier label must appear before every later label from that array.
Determine whether there is one ordering containing each distinct label from either array exactly once while preserving the relative order specified by both arrays. Return `true` if such an ordering exists and `false` if the constraints conflict. Only the Boolean feasibility result is required; the source report explicitly permits this form instead of returning a valid ordering.
### Input and Output
- Inputs: arrays `a` and `b` of integer labels. Equal labels across the two arrays identify the same item. The numeric values are identifiers; numeric sort order imposes no constraint.
- Output: one Boolean value.
For this practice version, labels within each individual array are distinct, though a label may occur in both arrays. Label values fit in signed 32-bit integers. An empty array imposes no ordering constraints, so two empty arrays are feasible. The source report does not specify repeated labels within one array or an input-size bound.
### Example 1
```text
a = [1, 2, 3]
b = [2, 4, 5]
answer = true
```
The ordering `[1, 2, 3, 4, 5]` satisfies both arrays.
### Example 2
```text
a = [1, 6, 4]
b = [4, 1]
answer = false
```
The first array requires `1` before `4`, while the second requires `4` before `1`.
Overview: Determine whether two ordered sequences have compatible relative-order constraints, returning Boolean feasibility when shared labels create conflicts.
Read the full Google Software Engineer interview experience this question came from
You are given two arrays of integer labels, `a` and `b`. The order of labels in each array gives ordering constraints: an earlier label must appear before every later label from that array.
Determine whether there is one ordering containing each distinct label from either array exactly once while preserving the relative order specified by both arrays. Return `true` if such an ordering exists and `false` if the constraints conflict. Only the Boolean feasibility result is required; the source report explicitly permits this form instead of returning a valid ordering.
### Input and Output
- Inputs: arrays `a` and `b` of integer labels. Equal labels across the two arrays identify the same item. The numeric values are identifiers; numeric sort order imposes no constraint.
- Output: one Boolean value.
For this practice version, labels within each individual array are distinct, though a label may occur in both arrays. Label values fit in signed 32-bit integers. An empty array imposes no ordering constraints, so two empty arrays are feasible. The source report does not specify repeated labels within one array or an input-size bound.
### Example 1
```text
a = [1, 2, 3]
b = [2, 4, 5]
answer = true
```
The ordering `[1, 2, 3, 4, 5]` satisfies both arrays.
### Example 2
```text
a = [1, 6, 4]
b = [4, 1]
answer = false
```
The first array requires `1` before `4`, while the second requires `4` before `1`.
Constraints
- Each input is a finite array of internally distinct signed 32-bit integer labels; either array may be empty.
- A label appearing in both arrays identifies one item. Numeric label order has no meaning.
- Return only Boolean feasibility; no witness ordering is required.
- No input-size bound is supplied.
Examples
Input: ([1, 2, 3], [2, 4, 5])
Expected Output: True
Explanation: The two orderings share label 2 and admit one merged ordering.
Input: ([1, 6, 4], [4, 1])
Expected Output: False
Explanation: The first sequence puts 1 before 4 while the second reverses them.
Hints
- Both arrays impose earlier-before-later constraints.
- Two empty arrays impose no constraints.