FastPrepFastPrep
Problem Brief

Order Records by Matching Start and End

FULLTIMEONSITE INTERVIEW
See Microsoft online assessment and 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.

1Example 1

Input
starts = ["aaa", "bbb", "ccc"], ends = ["bbb", "ccc", "ddd"], payloads = ["2", "1", "3"]
Output
"213"
Explanation

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

2Example 2

Input
starts = ["p"], ends = ["q"], payloads = ["X"]
Output
"X"
Explanation

A single record is already ordered.

Constraints

Limits and guarantees your solution can rely on.

  • 1 <= starts.length == ends.length == payloads.length <= 2 * 10^5
  • The records form exactly one valid chain.
public String concatenateOrderedPayloads(String[] starts, String[] ends, String[] payloads) {
    // write your code here
}
Input

starts

["aaa", "bbb", "ccc"]

ends

["bbb", "ccc", "ddd"]

payloads

["2", "1", "3"]

Output

"213"

Sign in to submit your solution.