Rebuild a trip itinerary: A Sample Coding Interview Solution

The coding question

You're given a traveler's flight tickets as from/to airport pairs. Starting from their home airport, put the trip back together in order using every ticket once. If more than one order works, return the alphabetically smallest.

Ask a few questions first

Ask	What we'll assume
Is there always a way to use every ticket?	Yes, assume the tickets always make at least one full trip from home.
Can the same flight appear twice?	Yes, two tickets from AMS to BCN are two separate tickets, and both get used.
Does the trip have to end at home?	No. It ends wherever the last ticket lands.
What does 'alphabetically smallest' mean?	Compare the trips airport by airport, and the first one with an earlier airport code wins.

A couple of examples

Input	Output
(LHR, AMS), (AMS, BCN), (BCN, LHR), home AMS	['AMS', 'BCN', 'LHR', 'AMS']
(AMS, BCN), (AMS, LIS), (LIS, AMS), home AMS	['AMS', 'LIS', 'AMS', 'BCN']. Going to BCN first gets stuck there with tickets left
(AMS, BCN), (AMS, BCN), (BCN, AMS), home AMS	['AMS', 'BCN', 'AMS', 'BCN']

Start with brute force

Try every order. From home, try each unused ticket out of the current airport, smallest first, and keep going. If you get stuck with tickets left, undo the last ticket and try the next one. The first full trip you find is the smallest one.

Cost: It's right, but in the worst case it can back up and retry a lot, which is exponential in the number of tickets. Fine for a handful, slow for thousands.

A better way

Think of airports as points and tickets as arrows between them. Using every ticket once is walking every arrow once, which is a classic graph problem with a neat trick.

Walk greedily, always taking the smallest ticket out. When you get stuck, the airport you're stuck at has to be the end of whatever's left of the trip, because there's no ticket out of it. So write it down and step back to the previous airport, then keep going from there with its other tickets.

That gives you the airports from the end of the trip back to the start. Reverse the list and you're done. Each ticket gets used once and each airport gets written down once, so there's no exponential retrying.

To always grab the smallest ticket quickly, sort each airport's destinations backwards and pop from the end of the list.

Build a map from each airport to its destinations, sorted from largest to smallest.
Start a stack with the home airport.
Look at the top airport. If it has tickets left, pop the smallest one and push the destination.
If it has none, pop it off the stack and add it to the route.
When the stack's empty, reverse the route.

The code

solution.pypython

from collections import defaultdict


def rebuild_itinerary(tickets, home):
    # airport -> destinations, sorted backwards so pop() gives the smallest
    flights = defaultdict(list)
    for origin, destination in tickets:
        flights[origin].append(destination)
    for destinations in flights.values():
        destinations.sort(reverse=True)

    route = []
    stack = [home]
    while stack:
        airport = stack[-1]
        if flights[airport]:
            # Use the smallest unused ticket out of here.
            stack.append(flights[airport].pop())
        else:
            # Stuck: nothing left from here, so it goes at the end of
            # what's left of the trip. Back out to the previous airport.
            route.append(stack.pop())

    # Airports were added from the end of the trip back to the start.
    return route[::-1]

	Cost	Why
Time	O(t log t)	Sorting the destinations. The walk itself touches each ticket once
Space	O(t)	The destination lists, the stack and the route

Test it

Walk through one of the examples out loud, then check the cases that tend to break things:

The greedy trap: from AMS with tickets to BCN and LIS, going to BCN first gets stuck. The route still comes out as AMS, LIS, AMS, BCN.
Duplicate tickets: both copies sit in the list and both get popped.
A ticket from an airport to itself: works like any other ticket.
No tickets: the trip is just the home airport.

Common mistakes

Plain greedy with no backing out, which works on easy examples and fails the dead-end case.
Forgetting to reverse the route at the end.
Using a set of destinations, which drops duplicate tickets.
Sorting ascending and popping from the front of a list, which is O(n) each time.

Follow-up questions

What if the tickets might not make a full trip?

Check the result: it should have one more airport than there are tickets, and each step should match an unused ticket. If not, say there's no valid trip.

What if you don't know the home airport?

Find the airport with one more ticket out than in. If every airport has the same in and out, the trip's a loop and you can start anywhere, so pick the smallest.

How would you write the backtracking version?

A recursive DFS that marks a ticket used, recurses, and unmarks it if it gets stuck. It's easier to explain but can be much slower on big inputs.

How the time adds up

Minutes	What you're doing
0–5	Ask about duplicates, the start and whether a trip always exists
5–10	Brute force: backtracking DFS
10–20	Spot the dead-end trick and why the route comes out reversed
20–35	Write the code
35–40	Test with the dead-end example and duplicates
40–45	Follow-up questions

Key concepts used here

We wrote this sample solution ourselves. Practice Loop is independent and isn't affiliated with or endorsed by Booking.com.