Find the Shortest Round Trip
Updated
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.
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^4distinct cities.
More Expedia Phone Screen questions
- Two SumPHONE SCREEN · ONSITE INTERVIEW · Seen Feb 2024
- Merge Two Sorted Linked ListsPHONE SCREEN · ONSITE INTERVIEW · Seen May 2023
- Assign CookiesPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2022
- Kth Smallest Value in a BSTPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2022
- Reverse a Singly Linked ListPHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2022
- Climbing StairsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2021
- First Substring OccurrencePHONE SCREEN · ONSITE INTERVIEW · Seen Aug 2021
- Array Containment with MultiplicitiesPHONE SCREEN · Seen Nov 2019
- Merge Sorted Arrays in PlacePHONE SCREEN · ONSITE INTERVIEW · Seen May 2019
- Subtract the Next Smaller ValuePHONE SCREEN · Seen Oct 2018
Similar questions at other companies
- Number of IslandsAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Evaluate DivisionApple · PHONE SCREENApple interview questions
- Possible BipartitionByteDance · PHONE SCREENByteDance interview questions
- Route Graph Reachability with a Broken LinkFigma · PHONE SCREENFigma interview questions
- Count Friend CirclesOpenAI · PHONE SCREEN · ONSITE INTERVIEWOpenAI interview questions
- Number of IslandsGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Count Connected IslandsUber · PHONE SCREENUber interview questions
- Course ScheduleNykaa · PHONE SCREENNykaa interview questions
- Number of IslandsSpaceX · PHONE SCREENSpaceX interview questions
- Pacific Atlantic Water FlowAnduril · PHONE SCREENAnduril interview questions
Expedia interview experiences
- Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
- Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
- Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
- Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
- Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)
- Expedia SWE Intern Final Round: 126 Experiences (Part 1 of 6)