Pinterest·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

May 2026Remote

Summary

Pinterest phone screen for a software engineer role, pretty much one meaty graph problem the whole time. The question had enough moving parts that I left unsure if I'd covered everything they wanted.

Questions Asked (1)

Given a list of airline tickets as directed pairs [from, to], reconstruct an itinerary starting from a given airport that uses every ticket exactly once. If multiple valid itineraries exist, return the lexicographically smallest one. Walk through your data structures, time and space complexity, and explain how your solution handles cycles and cases where no valid itinerary can be formed.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

This is basically Hierholzer's algorithm dressed up in an airport costume.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the tickets as a directed multigraph and use Hierholzer's algorithm to find an Eulerian path, ensuring the lexicographically smallest result by sorting adjacency lists and using a min-heap or sorted list. Build the itinerary by performing a post-order DFS and reversing the result, which naturally handles cycles and dead ends.

Pro tip: Emphasize that lexicographic order is achieved by always choosing the smallest next airport, but be careful: greedy DFS without backtracking can fail; Hierholzer's algorithm with post-order insertion guarantees correctness. Also, explicitly discuss how to detect if no valid itinerary exists (e.g., if the graph is disconnected or degrees violate Eulerian path conditions).

1. Clarify problem and constraints

Restate the problem: given a list of directed edges, find an Eulerian path starting from a given airport that uses all edges exactly once, and return the lexicographically smallest such path. Mention assumptions: tickets may form multiple components, and the graph may not have a valid itinerary.

2. Choose data structures

Use a hash map (or dictionary) to map each airport to a min-heap (or sorted list) of destination airports. This allows O(1) access to the next smallest destination and efficient removal. Also maintain a list to build the itinerary in reverse order.

3. Apply Hierholzer's algorithm

Perform a DFS starting from the given airport. At each step, pop the smallest destination from the heap and recursively visit it. After exploring all outgoing edges from a node, append the node to the itinerary list. This post-order traversal ensures that cycles are handled correctly and the final reversed list is a valid Eulerian path.

4. Handle edge cases and validation

Check if the total number of edges used equals the number of tickets; if not, no valid itinerary exists. Also, verify that the starting airport has the correct degree balance (out-degree = in-degree + 1 for start, unless start = end for Eulerian circuit). Discuss how cycles are naturally handled by the algorithm.

5. Analyze complexity and trade-offs

Time complexity: O(E log E) due to heap operations, where E is the number of tickets. Space complexity: O(E) for the graph and recursion stack. Mention that using a sorted list with pointer could reduce to O(E log E) for sorting but O(1) per edge, or O(E) if using bucket sort for small alphabet. Discuss trade-offs between heap and sorted list.

Key Points to Mention

Eulerian path conditions: exactly one vertex with out-degree = in-degree + 1 (start), one with in-degree = out-degree + 1 (end), others balanced; or all balanced for a circuit.
Lexicographically smallest itinerary: achieved by always choosing the smallest next airport, but must use post-order DFS to avoid getting stuck in cycles.
Handling cycles: Hierholzer's algorithm naturally handles cycles by exploring all edges before adding a node to the itinerary, ensuring cycles are inserted correctly.
No valid itinerary: if the graph is disconnected (ignoring isolated vertices) or degree conditions are violated, return an empty list or indicate impossibility.
Data structures: hash map of min-heaps for efficient retrieval of smallest destination; list for reverse itinerary.
Complexity: O(E log E) time, O(E) space; can optimize to O(E) with bucket sort if airport codes are limited.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.