FastPrepMerge Subsequences Into a Consistent Total Order
Problems/Merge Subsequences Into a Consistent Total Order

Merge Subsequences Into a Consistent Total Order

Google logoGoogle● MediumINTERNFULLTIMEPHONE SCREENONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: The report describes edges between adjacent pairs, Kahn's topological sort, cycle detection, a min-heap for the lexicographically smallest order, and a follow-up for when the result is not unique. It does not give rules for duplicate edges or an empty result. Our version is about 94% the same as the reported question.

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
All Google interview questionsSee Google hiring insights
Saved
class Solution {
    public int[] mergeSubsequences(int[][] subsequences) {
      // Write your code here.
    }
}
Checking account…