FastPrepValidate and Complete Racer Precedence

Validate and Complete Racer Precedence

Microsoft logoMicrosoft● MediumINTERNONSITE INTERVIEW
Learn

Problem statement

Each pair [before,after] states that racer before finished ahead of racer after. Racer names are the names appearing in at least one pair.

Return four strings: whether the data is acyclic, whether it determines one complete total order, the first racer, and the last racer. Boolean fields are "true" or "false". If the data is cyclic or does not determine a unique total order, return empty strings for first and last. Duplicate relations do not change the result.

Function

analyzeRaceOrder(relations: String[][]) → String[]

Examples

Example 1

relations = [["A","B"],["B","C"],["C","D"]]return = ["true","true","A","D"]

The DAG has one topological order from A to D.

Example 2

relations = [["A","C"],["B","C"]]return = ["true","false","",""]

The data is valid but A and B are incomparable.

Example 3

relations = [["A","B"],["B","A"]]return = ["false","false","",""]

The cycle makes the data invalid.

Constraints

  • 0 <= relations.length <= 100000.
  • Names are nonempty.

More Microsoft problems

See Microsoft hiring insights
public String[] analyzeRaceOrder(String[][] relations) {
    // write your code here
}
relations[["A","B"],["B","C"],["C","D"]]
expected["true", "true", "A", "D"]
Checking account…