Pinterest·Machine Learning Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

Jun 2026

Summary

Pinterest MLE interview that came down to a graph problem I hadn't touched in a while. The algorithmic depth required here was a bit more than I expected for an MLE role.

Questions Asked (1)

Given a list of airline tickets where each ticket is a [departure, arrival] pair, reconstruct a valid itinerary starting from JFK that uses all tickets exactly once. If multiple valid itineraries exist, return the one with the smallest lexical order.

Algorithms & Data Structures

Author's notes

I knew this was an Eulerian path problem pretty quickly but then froze on the implementation.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the tickets as a directed graph where each airport is a node and each ticket is an edge. Use Hierholzer's algorithm to find an Eulerian path starting from JFK, ensuring lexical order by processing destinations in sorted order. Return the reversed path as the itinerary.

Pro tip: Mention that this is a classic Eulerian path problem and that using a min-heap for each airport's destinations ensures the smallest lexical order efficiently. Also, note that the problem guarantees a valid itinerary exists, so no need to handle invalid cases.

1. Understand the problem as an Eulerian path

Recognize that each ticket is a directed edge, and we need a path that uses all edges exactly once, starting from JFK. This is exactly an Eulerian path in a directed graph.

2. Build the graph with lexical ordering

Use a hash map to map each departure airport to a min-heap (or sorted list) of arrival airports. This ensures that when we explore, we always consider the smallest lexical destination first.

3. Apply Hierholzer's algorithm iteratively

Start from JFK and perform a DFS, always visiting the smallest lexical destination. When stuck (no outgoing edges), add the airport to the itinerary and backtrack. Use a stack to avoid recursion depth issues.

4. Construct and return the itinerary

After the DFS, the itinerary is built in reverse order. Reverse it to get the correct sequence from JFK to the final destination.

Key Points to Mention

Eulerian path in a directed graph
Hierholzer's algorithm for finding Eulerian paths
Using a min-heap or sorted list to ensure lexical order
Time complexity: O(E log E) due to sorting, or O(E) with efficient data structures
Space complexity: O(E) for storing the graph and itinerary
Handling of multiple valid itineraries by always choosing the smallest lexical next airport

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