← Pinterest Interview Insights

Pinterest·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Apr 2026

Summary

Pinterest coding interview with a graph traversal problem. Pretty standard algorithmic round but the lexicographic ordering constraint is the part that trips people up if you're not careful with how you sort the adjacency list.

Questions Asked (1)

Q1

Given a list of airline tickets as departure-arrival airport pairs, reconstruct the full itinerary using every ticket exactly once, starting from the correct airport. If multiple valid itineraries exist, return the lexicographically smallest one.

Algorithms & Data Structures
Author's notes

The core of this is Hierholzer's algorithm for Eulerian paths, but I didn't think of it that cleanly in the moment.

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 to ensure the lexicographically smallest itinerary, then reverse the result.

Pro tip: Mention that the problem is essentially finding an Eulerian path in a directed graph, and that using a min-heap for neighbors ensures lexicographic order without extra sorting.

1. Understand the problem

Recognize that each ticket is a directed edge, and we need to use all edges exactly once, forming an Eulerian path. The starting airport is 'JFK'.

2. Choose the right algorithm

Use Hierholzer's algorithm to find an Eulerian path efficiently in O(E log E) time. This involves a depth-first search that builds the itinerary in reverse order.

3. Ensure lexicographic order

Store outgoing edges in a min-heap (priority queue) so that at each step, the smallest destination is chosen first. This guarantees the lexicographically smallest itinerary among all valid ones.

4. Implement and handle edge cases

Write the DFS iteratively or recursively, popping from the heap. After traversal, reverse the collected path. Handle cases where multiple tickets share the same departure and arrival.

5. Analyze complexity and test

Time complexity is O(E log E) due to heap operations, space O(E). Test with examples like [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]] to verify correctness.

Key Points to Mention

  • Graph representation: adjacency list with min-heap for each node
  • Eulerian path conditions: all nodes with non-zero degree are connected and at most one node has out-degree - in-degree = 1 (start), at most one has in-degree - out-degree = 1 (end)
  • Hierholzer's algorithm: post-order DFS to build path in reverse
  • Lexicographic order: min-heap ensures smallest next destination at each step
  • Time complexity: O(E log E) where E is number of tickets
  • Edge cases: multiple valid itineraries, disconnected graph (though problem guarantees a valid itinerary)

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