How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Pinterest.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Pinterest during technical interviews.

Reconstruct route from unordered travel tickets

Company: Pinterest

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given a list of directed travel tickets, each represented as a pair `[from, to]` (city names are strings), e.g. `[["A","B"],["B","C"], ...]`. The tickets form exactly one valid trip that visits cities in a single chain (no branching): - Every city has **at most one outgoing** ticket and **at most one incoming** ticket. - All tickets belong to the same trip. - The starting city is **not given**. Return the full ordered itinerary as a list of cities, e.g. given `[["A","B"],["B","C"]]`, return `["A","B","C"]`. **Constraints** - `1 <= tickets.length <= 2e5` - City names are non-empty strings. - The input is guaranteed to form one valid chain. **Output** - A list of cities of length `tickets.length + 1` representing the reconstructed route.

Quick Answer: This question evaluates understanding of directed graph concepts and sequence reconstruction, assessing the ability to reason about ordered relationships and one-to-one incoming/outgoing connections between nodes.

You are given a list of directed travel tickets, each represented as a pair `[from, to]` (city names are strings), e.g. `[["A","B"],["B","C"], ...]`. The tickets form exactly one valid trip that visits cities in a single chain (no branching): - Every city has **at most one outgoing** ticket and **at most one incoming** ticket. - All tickets belong to the same trip. - The starting city is **not given**. Return the full ordered itinerary as a list of cities. For example, given `[["A","B"],["B","C"]]`, return `["A","B","C"]`. The tickets may be supplied in any order. **Approach:** Build a `from -> to` map and a set of cities that appear as a destination. The unique start city is the one that never appears as a destination. Then walk the map from the start, appending each next city, until there is no outgoing ticket. The result has length `tickets.length + 1`.

Constraints

1 <= tickets.length <= 2e5
City names are non-empty strings.
Every city has at most one outgoing and at most one incoming ticket.
The input is guaranteed to form exactly one valid chain.
The output list has length tickets.length + 1.

Examples

Input: ([["A","B"],["B","C"]],)

Expected Output: ["A", "B", "C"]

Explanation: Simple 3-city chain already in order: A->B->C.

Input: ([["B","C"],["A","B"]],)

Expected Output: ["A", "B", "C"]

Explanation: Tickets are shuffled; A is the start because it never appears as a destination.

Input: ([["JFK","LAX"]],)

Expected Output: ["JFK", "LAX"]

Explanation: Boundary case: a single ticket yields a 2-city route.

Input: ([["D","E"],["A","B"],["C","D"],["B","C"]],)

Expected Output: ["A", "B", "C", "D", "E"]

Explanation: Fully shuffled 5-city chain; reconstruct A->B->C->D->E by following the outgoing map from A.

Input: ([["NYC","BOS"],["BOS","SEA"],["SEA","SFO"]],)

Expected Output: ["NYC", "BOS", "SEA", "SFO"]

Explanation: Longer chain in order across four cities.

Hints

The start city is the only one that never appears as a destination (`to`). Track all destinations in a set and find the `from` that is not in it.
Build a `from -> to` hash map so you can jump directly to the next city in O(1).
Walk from the start, following the map and appending each city, until the current city has no outgoing ticket. No sorting needed — the chain is unique.

Quick Overview

This question evaluates understanding of directed graph concepts and sequence reconstruction, assessing the ability to reason about ordered relationships and one-to-one incoming/outgoing connections between nodes.