Merge Subsequences Into a Consistent Total Order
Updated
Problem statement
You are given several integer subsequences. Every adjacent pair in a subsequence imposes a directed ordering constraint. Merge all distinct values into one total sequence that respects every constraint.
If the constraints contain a cycle, return an empty array. If several valid total orders exist, return the lexicographically smallest one.
Function
mergeSubsequences(subsequences: int[][]) → int[]Examples
Example 1
subsequences = [[1,2,3],[1,3],[2,4]]return = [1,2,3,4]The order respects every edge and chooses 3 before 4 when both are available.
Example 2
subsequences = [[1,2],[2,1]]return = []The constraints contain a cycle.
Example 3
subsequences = [[2,4],[1,4],[3]]return = [1,2,3,4]Values 1, 2, and 3 initially have zero indegree and are chosen in increasing order.
Example 4
subsequences = [[5],[5,6],[7,6]]return = [5,7,6]Both 5 and 7 precede 6, and 5 is the smaller initial choice.
Constraints
1 <= subsequences.length <= 100000.- Each subsequence contains distinct integers.
- The total number of element occurrences is at most
200000. - Parallel constraints between the same ordered pair count once.
More Google Onsite Interview questions
- Evaluate a Nested Math ExpressionPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Distinct Subset SumsONSITE INTERVIEW · Seen Nov 2026
- Playlist With No Same Artist in a RowONSITE INTERVIEW · Seen Nov 2026
- Route Pattern MatcherPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Delete Nodes and Return Forest RootsONSITE INTERVIEW · Seen Nov 2026
- Dice-Walk Winning ProbabilityPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- First and Last Target Position in a Mountain ArrayONSITE INTERVIEW · Seen Nov 2026
- Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- 0/1 Knapsack with Weight and Volume LimitsONSITE INTERVIEW · Seen Nov 2026
- Batched Subsequence Word MatchesONSITE INTERVIEW · Seen Nov 2026
Similar questions at other companies
- Course Schedule IIAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Task Scheduler with Prerequisites and Execution PathsBrex · PHONE SCREEN
- Dependency-Aware Task SchedulerRippling · PHONE SCREENRippling interview questions
- Lexicographically Smallest Topological OrderByteDance · PHONE SCREEN · ONSITE INTERVIEWByteDance interview questions
- Lexicographic Dependency OrderIllumio · PHONE SCREENIllumio interview questions
- Topological Sort with Secondary OrderingRoblox · PHONE SCREEN · ONSITE INTERVIEWRoblox interview questions
- Lexicographically Smallest Course OrderLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
- Order Sources by Their DependenciesRetool · PHONE SCREENRetool interview questions
- ETL Pipeline SchedulerUnity · ONSITE INTERVIEW
- Dependency-Aware Agent Task SchedulerOpenAI · PHONE SCREENOpenAI interview questions
Google interview experiences
- Google L5 Security Engineer Domain Knowledge Round: 1 Experience
- Google Software Engineer Onsite Questions: 10 Experiences
- Google OA: What It Tests (2026)
- Google L4 SWE Phone Screen: 1 Experience
- Google ML Engineering Manager Onsite: 1 Experience
- Google Experienced SWE First Round and Onsite: 1 Experience