Leetcode 444. Sequence Reconstruction
Given an original sequence and a list of subsequences, determine whether those subsequences uniquely determine the original order — equivalently, whether the precedence constraints induce a unique topological ordering equal to the given sequence. Model subsequences as directed edges and check that a topological sort exists and is unique (only one candidate with indegree zero at each step) matching the original.
Asked at:
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Late October, 2024
Junior
Given a list of pairs where each pair indicates that the first character is greater than the second, find a proper increasing sequence of all the characters if possible, otherwise return 'None'. For example, the list might look like: [['a', 'b'], ['b', 'd'], ['d', 'c'], ['a', 'd'], ['a', 'c']] (where 'a > b', 'b > d', and so on). This problem can be solved using topological sorting.
Comments
Hello Interview Premium
Your account is free and you can post anonymously if you choose.