FastPrepFind the Shortest Round Trip
Problems/Find the Shortest Round Trip

Find the Shortest Round Trip

Expedia logoExpedia● MediumFULLTIMEPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: The report gives a flight list and a start city, asks for a round trip using DFS, then asks for the shortest path as a follow-up. It does not say how ties work. Our version is about 94% the same as the follow-up in the report.

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^4 distinct 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)
All Expedia interview questionsSee Expedia hiring insights
Saved
class Solution {
    public String[] findShortestRoundTrip(String[][] flights, String start) {
        // Your code here
    }
}
Checking account…