FastPrep
Problem · Hash Table

Order Records by Matching Start and End

● EasyMicrosoftFULLTIMEONSITE INTERVIEW
See Microsoft hiring insights

You are given a shuffled set of records. Record i has three fields: starts[i], ends[i], and payloads[i].

The records form exactly one chain. If record A has ends[A] == starts[B], then record A must appear immediately before record B in the chain.

Order the records by this chaining rule and concatenate their payloads in that order.

Function Description

Complete the function concatenateOrderedPayloads in the editor below.

concatenateOrderedPayloads has the following parameters:

  1. String[] starts: the start keys
  2. String[] ends: the end keys
  3. String[] payloads: the payload fragments

Returns

String: the concatenated payload string after ordering the chain.

Examples
01 · Example 1
starts = ["aaa", "bbb", "ccc"]
ends = ["bbb", "ccc", "ddd"]
payloads = ["2", "1", "3"]
return = "213"

The only valid order is aaa -> bbb -> ccc -> ddd, so the payloads join as 2 + 1 + 3.

02 · Example 2
starts = ["p"]
ends = ["q"]
payloads = ["X"]
return = "X"

A single record is already ordered.

Constraints
  • 1 <= starts.length == ends.length == payloads.length <= 2 * 10^5
  • The records form exactly one valid chain.
More Microsoft problems
drafts saved locally
public String concatenateOrderedPayloads(String[] starts, String[] ends, String[] payloads) {
    // write your code here
}
starts["aaa", "bbb", "ccc"]
ends["bbb", "ccc", "ddd"]
payloads["2", "1", "3"]
expected"213"
checking account