Reconstruct Itinerary (Graph & Stack)
Given a list of airline tickets, reconstruct the itinerary in order, starting from 'JFK'. If multiple valid itineraries exist, return the one that has the smallest lexical order. Use DFS/Backtracking on a graph.
Why Interviewers Ask This
Microsoft asks this to evaluate a candidate's mastery of graph traversal algorithms, specifically Hierholzer's algorithm or DFS with backtracking. They assess the ability to handle complex constraints like lexical ordering while ensuring every ticket is used exactly once. It tests whether you can model real-world routing problems as directed graphs and manage state efficiently without getting stuck in dead ends.
How to Answer This Question
Key Points to Cover
- Explicitly mention using a Min-Heap or Sorted List to handle lexical ordering automatically
- Explain the critical difference between pre-order and post-order node addition in DFS
- Demonstrate understanding of Eulerian Path properties where every edge must be traversed exactly once
- Clarify how to handle duplicate tickets by removing edges rather than just marking visited nodes
- State the Time Complexity clearly as O(E log E) due to the sorting requirement
Sample Answer
Common Mistakes to Avoid
- Using a simple visited set instead of removing edges, which fails when multiple tickets exist between the same cities
- Adding nodes to the result list immediately upon entry (pre-order), causing the algorithm to terminate at a dead end prematurely
- Failing to sort the adjacency list, leading to incorrect results when multiple valid itineraries exist
- Not reversing the final result list because the post-order DFS generates the itinerary in reverse chronological order
Sound confident on this question in 5 minutes
Answer once and get a 30-second AI critique of your structure, content, and delivery. First attempt is free — no signup needed.