Katkat
Back

Reconstruct an Itinerary While Keeping an Unspecified Variant Explicit

PinterestSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

Tests finding an Eulerian path in a directed multigraph with lexicographical tie-breaking using Hierholzer's algorithm.

Problem Statement

You are given a list of airline tickets where each ticket represents a directed flight from an origin airport to a destination airport: tickets[i] = [from_i, to_i]. All tickets belong to a single traveler.

Reconstruct the traveler's itinerary in order. The itinerary must start from airport "JFK" and must use every ticket exactly once. If there are multiple valid itineraries that use all tickets, return the itinerary that has the smallest lexical order when read as a single list of airport codes.

You may assume that at least one valid itinerary exists that uses all given tickets.

Function Signature

def find_itinerary(tickets: list[list[str]]) -> list[str]:
    pass

Input & Output Format

  • Input: A list of pairs of strings tickets, where each pair [from_i, to_i] contains two 3-letter uppercase airport codes.
  • Output: A list of strings representing the sequence of airport visits, beginning with "JFK".

Constraints

  • 1 <= len(tickets) <= 3000
  • tickets[i].length == 2
  • Each airport code consists of exactly 3 uppercase English letters.
  • Duplicate tickets (multigraph edges) may exist.
  • It is guaranteed that at least one valid itinerary using all tickets exists.

Examples

Example 1

Input: tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Output: ["JFK", "MUC", "LHR", "SFO", "SJC"]

Explanation: The only valid sequence visiting all edges is JFK -> MUC -> LHR -> SFO -> SJC.

Example 2

Input: tickets = [["JFK", "SFO"], ["JFK", "ATL"], ["SFO", "ATL"], ["ATL", "JFK"], ["ATL", "SFO"]]
Output: ["JFK", "ATL", "JFK", "SFO", "ATL", "SFO"]

Explanation: Another possible itinerary is ["JFK", "SFO", "ATL", "JFK", "ATL", "SFO"], but "JFK", "ATL", ... is lexicographically smaller.

Edge Cases to Consider

  • Dead ends before exhausting all tickets: A greedy search that commits to the smallest lexical neighbor can get stuck in a dead-end before visiting all edges. Post-order traversal (Hierholzer's algorithm) or backtracking is required.
  • Duplicate tickets between the same pair of airports: Multiple identical flights must each be traversed exactly once.
  • Cycles: Routes often contain cycles returning to airports like "JFK" multiple times.

Hints

Hint 1

Model the tickets as directed edges in a multigraph and observe that the problem requires finding an Eulerian path starting at "JFK".

Hint 2

Sort the adjacency list for each airport in reverse lexicographical order so you can efficiently pop the smallest remaining destination.

Hint 3

Perform a post-order depth-first search (Hierholzer's algorithm), appending an airport to the result only when it has no outgoing edges left, then reverse the result at the end.

Follow-up questions

  • How would you detect and report if no valid itinerary that consumes all tickets exists?
  • How would you adapt the algorithm if the starting airport is not fixed to 'JFK' but can be any airport with a valid Eulerian path?
  • If recursion depth is a concern due to a deep chain of flights, how would you rewrite the algorithm iteratively using an explicit stack?