Katkat
Back

Reconstruct route from unordered travel tickets

PinterestSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to model a graph where each edge represents a transition, requiring you to find a valid linear sequence that visits every node exactly once.

Problem Statement

You are given a collection of unordered travel tickets, where each ticket represents a direct flight from one city to another. You are given a list of pairs [source, destination], where every city has exactly one outgoing flight and one incoming flight, except for the starting city (which has no incoming flight) and the ending city (which has no outgoing flight).

Your task is to reconstruct the full journey starting from the departure city and visiting every destination in the correct sequence.

Function Signature

def reconstruct_route(tickets: List[List[str]]) -> List[str]:

Constraints

  • Each ticket is represented as a list of two strings: [start_city, end_city].
  • The total number of tickets is n.
  • Every city is represented as a string.
  • The input is guaranteed to form a single valid path.

Examples

Example 1: Input: [['SFO', 'JFK'], ['LAX', 'SFO'], ['JFK', 'DXB']] Output: ['LAX', 'SFO', 'JFK', 'DXB'] Explanation: The sequence follows the connections LAX -> SFO -> JFK -> DXB.

Example 2: Input: [['Paris', 'London'], ['Berlin', 'Paris']] Output: ['Berlin', 'Paris', 'London']

Edge Cases

  • A journey consisting of only one ticket.
  • Large numbers of tickets (ensure your approach is more efficient than a naive search).

Hints

Hint 1

Represent the tickets as a directed graph where each city points to its destination city.

Hint 2

Identify the starting city by finding the node that appears as a source but never as a destination.

Hint 3

Once the start city is found, simply follow the pointers until you reach the final destination city.

Follow-up questions

  • What changes if the input could contain cycles, or if a city could be visited multiple times?
  • How would you handle a scenario where the input is incomplete and there is no valid path connecting all nodes?
  • What is the time and space complexity of your solution in terms of the number of tickets `n`?