FastPrepLexicographically Smallest Topological Order

Lexicographically Smallest Topological Order

Coinbase logoCoinbase● MediumFULLTIMEPHONE SCREEN
Learn

Problem statement

Find a topological order of a directed graph. For this exercise, assume vertices supplies all unique vertex labels, including isolated vertices. Each pair [u,v] in edges requires u to appear before v. Every endpoint belongs to the supplied vertices.

For this exercise, assume repeated identical pairs represent one dependency. Return every supplied label exactly once in the lexicographically smallest valid order: at the first differing position, the smaller lowercase string wins. A strict prefix comes before its longer form.

For this exercise, assume any directed cycle, including a self-loop, makes a complete order impossible; return an empty array. An empty graph also returns an empty array. Do not return a partial order or modify either input.

Function

topologicalOrder(vertices: String[], edges: String[][]) → String[]

Examples

Example 1

vertices = ["delta","alpha","charlie","bravo"]edges = [["alpha","charlie"],["bravo","charlie"],["charlie","delta"]]return = ["alpha","bravo","charlie","delta"]

Authored example: Alpha and bravo are initially available. Choosing alpha first gives the smallest complete order.

Example 2

vertices = ["a","b","z"]edges = [["a","b"],["b","a"]]return = []

Authored example: The a/b cycle prevents a complete order. Do not return the available isolated z as a partial answer.

Example 3

vertices = ["d","c","b","a"]edges = [["c","b"]]return = ["a","c","b","d"]

Authored example: After a and c, b becomes available and must precede the already available d.

Constraints

  • For this exercise, assume 0 <= vertices.length <= 100 and 0 <= edges.length <= 500.
  • Every unique vertex label contains 1 through 10 lowercase English letters.
  • Each edge has exactly two labels from vertices. An empty vertex list has no edges.
  • Duplicate pairs and self-loops are allowed.

More Coinbase problems

See Coinbase hiring insights
public String[] topologicalOrder(String[] vertices, String[][] edges) {
    // Write your code here.
    return new String[0];
}
vertices["delta","alpha","charlie","bravo"]
edges[["alpha","charlie"],["bravo","charlie"],["charlie","delta"]]
expected["alpha", "bravo", "charlie", "delta"]
Checking account…