How should I practice Reconstruct Itinerary?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Amazon onsite interview problems in FastPrep.

Is Reconstruct Itinerary associated with Amazon?

FastPrep tags this as a Amazon onsite interview coding practice problem when the problem catalog has that company and stage context.

Reconstruct Itinerary

Amazon● HardFULLTIMEONSITE INTERVIEW

Learn

Problem statement

Each ticket is a directed flight [from, to]. Build an itinerary that begins at JFK and uses every ticket exactly once. Return the airports in travel order, including the starting airport. Tickets with the same endpoints are distinct and must each be used.

At least one complete itinerary is guaranteed. If several complete itineraries exist, return the lexicographically smallest airport sequence. An early alphabetical choice may lead to a dead end, so the returned route must still use every ticket.

Function

findItinerary(tickets: String[][]) → String[]

Examples

Example 1

tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]return = ["JFK","MUC","LHR","SFO","SJC"]

The tickets form one complete route from JFK.

Example 2

tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]return = ["JFK","ATL","JFK","SFO","ATL","SFO"]

Both first destinations can be completed, but starting with ATL gives the lexicographically smaller itinerary.

Example 3

tickets = [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]return = ["JFK","NRT","JFK","KUL"]

Taking JFK → KUL first gets stuck. The complete route takes the NRT circuit before the final KUL ticket.

Constraints

1 <= tickets.length <= 300
Each ticket has exactly two airport codes.
Each airport code has exactly three uppercase English letters.
The departure and arrival on a ticket differ.
A complete itinerary beginning at JFK always exists.