Reconstruct itinerary with lexicographic ties
Company: Pinterest
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
You are given m airline tickets as directed pairs [from, to]. Build an itinerary that starts at a specified airport start (e.g., "JFK") and uses every ticket exactly once. If multiple itineraries are possible, return the lexicographically smallest sequence of airport codes. Tickets may repeat; m can be up to 10^4. Implement the function to return the itinerary, describe your data structures, analyze time and space complexity, and explain how your approach handles cycles and cases where no valid itinerary exists.
Quick Answer: This question evaluates a candidate's ability to model and traverse directed graphs with repeated edges, enforce lexicographic ordering among possible paths, and analyze time and space complexity for an algorithmic solution.