Reconstruct Itinerary

Algorithms
Hard
Stripe
54.2K views

Given a list of flight tickets, reconstruct the itinerary in order. The itinerary must begin with 'JFK'. If there are multiple valid itineraries, you should return the one that has the smallest lexical order. Use DFS and sorting.

Why Interviewers Ask This

Stripe evaluates candidates on graph traversal and state management under constraints. This question tests the ability to model real-world flight data as a directed graph, handle complex backtracking logic when dead-ends occur, and implement Hierholzer's algorithm efficiently. It specifically assesses lexical ordering requirements and the candidate's proficiency with DFS in non-trivial scenarios.

How to Answer This Question

1. Clarify constraints: Confirm if all tickets form a single valid Eulerian path starting at JFK and verify edge cases like multiple tickets to the same destination. 2. Model the Graph: Explain that you will use an adjacency list (HashMap) where keys are airports and values are sorted lists of destinations to ensure lexical order is met naturally during traversal. 3. Implement DFS Strategy: Describe using a post-order traversal approach. Instead of returning immediately upon visiting a node, recursively visit neighbors first. Only add the current airport to the result stack after all its outgoing edges are exhausted. 4. Handle Backtracking Logic: Emphasize that this specific DFS pattern automatically handles 'dead ends' by backtracking up the call stack until a valid path is found, ensuring the final reversed list represents the correct itinerary. 5. Optimize Complexity: Mention that sorting takes O(N log N) while the DFS runs in O(E), making the overall solution efficient for large datasets typical at Stripe.

Key Points to Cover

  • Explicitly mention using a HashMap with sorted lists for the adjacency structure
  • Demonstrate understanding of post-order DFS traversal for Eulerian path reconstruction
  • Explain how reversing the result stack yields the correct forward itinerary
  • Address the specific requirement of finding the lexicographically smallest path
  • Reference handling of disconnected components or dead-end scenarios gracefully

Sample Answer

To solve the Reconstruct Itinerary problem, I would first treat the flight tickets as a directed graph where each ticket represents an edge from one airport to another. Since we need the lexicographically smallest itiner…

Common Mistakes to Avoid

  • Attempting standard pre-order DFS which fails to handle dead-ends and produces invalid itineraries
  • Forgetting to sort the destination lists, leading to incorrect lexical ordering results
  • Using recursion without managing the visited state properly, causing infinite loops or missed edges
  • Neglecting to reverse the final result stack, outputting 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.

Try it free

Related Interview Questions

Edit Distance

Hard
LinkedIn

Split Array Largest Sum

Hard
Microsoft

Search in Rotated Sorted Array

Medium
Salesforce
Browse all 145 Algorithms questionsBrowse all 57 Stripe questions
Try this question free