← Pinterest Interview Insights

Pinterest·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
May 2026Remote

Summary

Pinterest SWE interview with a graph/DFS problem that looks straightforward until you actually try to implement it correctly under pressure.

Questions Asked (1)

Q1

Given a list of airline tickets where each ticket is a [from, to] pair, reconstruct the full itinerary starting from JFK. Use every ticket exactly once, and if multiple valid orderings exist, return the one that comes first lexicographically.

Algorithms & Data Structures
Author's notes

I knew this was Eulerian path territory but my first instinct was plain DFS and I didn't think carefully about the lexical ordering constraint until I was mid-implementation.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the tickets as a directed graph and find an Eulerian path starting from JFK. Use Hierholzer's algorithm with a min-heap (or sorted adjacency list) to ensure the lexicographically smallest itinerary. Build the itinerary in reverse order and then reverse it to get the final result.

Pro tip: Emphasize that the problem guarantees a valid itinerary, so you can focus on the algorithm without edge-case handling for invalid inputs. Also, mention that using a min-heap ensures lexical order at each step, which is crucial for the lexicographically smallest result.

1. Understand the problem

Clarify that we need to use all tickets exactly once, starting from JFK, and return the lexicographically smallest itinerary among all valid ones.

2. Choose the right algorithm

Recognize this as finding an Eulerian path in a directed graph. Use Hierholzer's algorithm to efficiently construct the path.

3. Handle lexical order

Use a min-heap or sort the adjacency list for each airport to always pick the smallest next destination, ensuring the lexicographically smallest itinerary.

4. Implement Hierholzer's algorithm

Perform a DFS, removing edges as you traverse, and add airports to the itinerary in post-order. Finally, reverse the itinerary to get the correct order.

5. Analyze complexity and test

Discuss time and space complexity (O(E log E) due to sorting/heap operations) and walk through a small example to verify correctness.

Key Points to Mention

  • Eulerian path concept and conditions (all vertices with non-zero degree belong to a single strongly connected component, and the graph has at most one vertex with out-degree - in-degree = 1 and at most one with in-degree - out-degree = 1).
  • Hierholzer's algorithm for finding Eulerian paths in O(E) time (with efficient data structures).
  • Use of min-heap or sorted adjacency list to ensure lexicographical order.
  • Building the itinerary in reverse and then reversing it.
  • Time complexity: O(E log E) due to heap operations or sorting, where E is the number of tickets.
  • Space complexity: O(E) for storing the graph and the itinerary.

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