Reconstruct route from unordered travel tickets

Q: Reconstruct route from unordered travel tickets

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

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.

Reconstruct route from unordered travel tickets

Overview

Comments (0)