How should I practice Reconstruct Flight Departure Chains?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Salesforce onsite interview problems in FastPrep.

Is Reconstruct Flight Departure Chains associated with Salesforce?

FastPrep tags this as a Salesforce onsite interview coding practice problem when the problem catalog has that company and stage context.

Problem · Graph

Reconstruct Flight Departure Chains

Learn this problem

● Medium

SalesforceFULLTIMEONSITE INTERVIEW

See Salesforce hiring insights

Problem statement

You are given directed flight legs in legs, where each pair [departure, arrival] represents one flight.

The legs form one or more vertex-disjoint simple directed paths. Every airport appears at most once as a departure and at most once as an arrival, there are no cycles, and no leg is duplicated.

For each maximal path, return the ordered departure airport of every leg. Do not include the final airport, because it is only an arrival. Order the returned chains lexicographically by their first airport.

Function

reconstructDepartureChains(legs: String[][]) → String[][]

Examples

Example 1

legs = [["a","b"],["b","c"],["c","d"],["x","y"],["y","z"]]return = [["a","b","c"],["x","y"]]

The first path has departures a, b, and c; terminal destination d is omitted. The second path similarly returns x and y.

Example 2

legs = [["B","C"],["X","Y"],["A","B"]]return = [["A","B"],["X"]]

The rows need not arrive in route order. The two roots are sorted as A and X.

Example 3

legs = [["MIA","LAX"]]return = [["MIA"]]

A one-leg path contributes its single departure airport.

Constraints

1 <= legs.length <= 200000.
Each row contains exactly two nonempty case-sensitive airport identifiers.
Each identifier has length at most 30.
The legs form vertex-disjoint simple directed paths with no duplicate edge.