How should I practice Find the Shortest Round Trip?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Expedia phone screen problems in FastPrep.

Is Find the Shortest Round Trip associated with Expedia?

FastPrep tags this as a Expedia phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Graph

Find the Shortest Round Trip

Learn this problem

● Medium

ExpediaFULLTIMEPHONE SCREEN

Problem statement

Each directed flight [from, to] is one available leg. Starting from start, return a route that follows available flights and returns to start using at least one leg.

The judged task targets the reported follow-up: choose a route with the fewest legs. For this exercise, if several shortest round trips exist, return the lexicographically smallest complete city sequence. Return an empty array when no round trip exists.

Function

findShortestRoundTrip(flights: String[][], start: String) → String[]

Examples

Example 1

flights = [["SFO","LAX"],["LAX","SFO"],["SFO","SEA"],["SEA","PDX"],["PDX","SFO"]]start = "SFO"return = ["SFO","LAX","SFO"]

The route through LAX uses two legs, fewer than the three-leg route through SEA and PDX.

Example 2

flights = [["A","B"],["B","C"]]start = "A"return = []

No available flight returns to A.

Constraints

0 <= flights.length <= 2 * 10^4
City identifiers are nonempty strings.
Duplicate flight pairs have the same meaning as one pair.
The graph contains at most 10^4 distinct cities.