Reconstruct Itinerary
Hard · Onsite · Phone screen · Full-time
Reconstruct an itinerary from flight tickets starting at JFK, using all tickets, with lexical ordering as the tiebreaker. Got this in my Pinterest phone screen. I used Hierholzer's algorithm for finding an Eulerian path, using a min-heap for each airport's destinations to get lexical order naturally. The interviewer asked why I build the path in reverse and whether the algorithm works when the graph isn't guaranteed to have an Eulerian path. Good discussion about the preconditions.
