Rebuild a Trip From Flight Tickets
Updated
Problem statement
A traveler kept every ticket from a trip, but the tickets got out of order. Ticket tickets[i] = [from, to] is one flight from airport from to airport to. The trip began at airport start.
Put the trip back together. Return the list of airports in the order they were visited, starting with start. The trip must use every ticket exactly once, so the list has tickets.length + 1 airports. Two tickets with the same from and to are two separate flights, and both must be used.
Sometimes more than one order uses every ticket. Then return the one that comes first alphabetically: compare the two lists airport by airport, and at the first airport where they differ, the list with the alphabetically smaller airport comes first.
Function
buildItinerary(tickets: String[][], start: String) → String[]Examples
Example 1
tickets = [["SEA","DEN"],["ORD","BOS"],["DEN","ORD"]]start = "SEA"return = ["SEA","DEN","ORD","BOS"]From SEA the only ticket goes to DEN. From there the only ticket goes to ORD, and then to BOS. All three tickets are used once.
Example 2
tickets = [["AUS","MIA"],["AUS","PHX"],["MIA","AUS"]]start = "AUS"return = ["AUS","MIA","AUS","PHX"]Only one order uses every ticket: AUS, MIA, AUS, PHX. If you fly from AUS to PHX first, you are stuck at PHX with two tickets unused.
Example 3
tickets = [["LAX","ATL"],["LAX","BOS"],["BOS","LAX"]]start = "LAX"return = ["LAX","BOS","LAX","ATL"]ATL comes before BOS in the alphabet. But flying from LAX to ATL first gets stuck at ATL with two tickets left. The only full trip is LAX, BOS, LAX, ATL.
Constraints
1 <= tickets.length <= 300tickets[i].length == 2- Every airport code, including
start, is exactly 3 uppercase English letters. tickets[i][0] != tickets[i][1]- At least one trip from
startuses every ticket exactly once.
More DocuSign Phone Screen questions
- Symmetric Binary TreePHONE SCREEN · Seen Oct 2026
- Union Area of Two RectanglesPHONE SCREEN · Seen Oct 2026
- Execute Cursor-Based Text Editor OperationsPHONE SCREEN · Seen Sep 2026
- Minimize Array Sum After K Halving OperationsPHONE SCREEN · Seen Sep 2026
- Fizz and Buzz Words From 1 to nPHONE SCREEN · Seen Sep 2026
- Two Positions That Add Up to a TargetPHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Rain Kept Between WallsPHONE SCREEN · Seen Mar 2026
- Exact Palindrome CheckPHONE SCREEN · ONSITE INTERVIEW · Seen Apr 2022
- Reverse the Characters of a TextPHONE SCREEN · ONSITE INTERVIEW · Seen Apr 2022
- Find the Words for Each PrefixPHONE SCREEN · Seen Sep 2018
Similar questions at other companies
- Minimum Boards to Cover Roof HolesGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Visit Desired Attractions Without Reusing a TrailDuolingo · PHONE SCREENDuolingo interview questions
- Attraction Route Without Reusing TrailsWhatNot · PHONE SCREENWhatNot interview questions
- Spreadsheet With Dependent CellsCharacter.AI · PHONE SCREEN
- Course Order and CycleAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Evaluate Live Spreadsheet ExpressionsStrala · PHONE SCREEN
- Enumerate Directed Paths and CyclesByteDance · PHONE SCREENByteDance interview questions
- Process Graph Rule ValidationHadrian · PHONE SCREENHadrian interview questions
- Spreadsheet Formula EvaluatorPika · PHONE SCREEN
- Group Training Overdue RollupVanta · PHONE SCREEN