Reconstruct Itinerary
Reported by candidates from Bloomberg's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
Brute force dies fast on this one. Bloomberg reported Reconstruct Itinerary in January 2021, and trying every ordering of the tickets blows up factorially the moment an airport has several outgoing flights. You have to use every ticket exactly once, start at JFK, and return the lexicographically smallest route. That's an Eulerian path problem dressed up as a travel puzzle. If you blank on the trick during the OA, StealthCoder sits invisibly on your screen as a safety net and hands you the approach. Know the idea first, though, because it's short.
The problem
You are given airline tickets represented as [from, to] pairs. Reconstruct the itinerary that uses every ticket exactly once. The itinerary must start at "JFK". If multiple valid itineraries exist, return the lexicographically smallest itinerary when read as a single sequence of airport codes. Function findItinerary(tickets: String[][]) → String[] Examples Example 1 tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]] return = ["JFK","MUC","LHR","SFO","SJC"] There is only one route that uses all tickets from JFK. Example 2 tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]] return = ["JFK","ATL","JFK","SFO","ATL","SFO"] Both choices from JFK can lead to valid routes, but the route beginning with ATL is lexicographically smaller.
Reported by candidates. Source: FastPrep
Pattern and pitfall
The trick is Hierholzer's algorithm. Build an adjacency list where each airport maps to its destinations sorted lexicographically, using a min-heap or a reverse-sorted list you pop from. Run DFS from JFK. At each node, keep taking the smallest unused outgoing ticket. When a node has no tickets left, append it to the result. Reverse the result at the end. The post-order append is what handles dead ends correctly, since the stuck airport lands at the tail of the route. The common pitfall is greedy without backtracking: picking the smallest neighbor and walking forward fails when that branch strands you with tickets unused. Another is mutating the adjacency list wrong or forgetting duplicate tickets, which are valid. Complexity is O(E log E) from sorting. If you freeze live, StealthCoder is the hedge that surfaces the Hierholzer template so you can still ship clean code.
The honest play: practice the pattern, and have StealthCoder ready for the one you didn't see coming.
You can drill Reconstruct Itinerary cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Built for the candidate who saw this exact problem leak two days before his OA and wondered if anyone had a play.
Get StealthCoderRelated leaked OAs
This OA pattern shows up on LeetCode as reconstruct itinerary. If you have time before the OA, drill that.
You've seen the question.
Make sure you actually pass Bloomberg's OA.
Bloomberg reuses patterns across OAs. Built for the candidate who saw this exact problem leak two days before his OA and wondered if anyone had a play. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Reconstruct Itinerary FAQ
What's the trick to Reconstruct Itinerary?+
Treat it as finding an Eulerian path and use Hierholzer's algorithm. Sort destinations, run DFS from JFK, append an airport only after all its outgoing tickets are used, then reverse the list. The post-order append handles dead ends without explicit backtracking.
Why does simple greedy fail here?+
Taking the smallest next airport each time can lead you into a dead end with tickets still unused. Example 2 shows the shape of it: choices from JFK both look fine locally. Hierholzer's post-order construction fixes the stranded branch by placing it at the end of the route.
How hard is this really for a Bloomberg OA?+
It's a hard-tagged graph problem, mostly because the Eulerian path idea isn't obvious. Once you know Hierholzer, the code is about fifteen lines. Bloomberg reported it in January 2021, so expect graph traversal with an ordering constraint rather than a trick question.
How do I handle lexicographic order efficiently?+
Sort the tickets once, or push destinations into a min-heap per airport. Then always pop the smallest remaining destination during DFS. Duplicate tickets are allowed, so don't use a set. A heap or sorted list popped from the end keeps each step cheap.
How do I prepare in 48 hours?+
Write Hierholzer from memory twice on this exact problem. Then test Example 2 by hand, including the dead-end case. Skim related graph traversal with ordering rules. Don't try to learn ten new patterns. One clean template beats broad shallow coverage.