Reconstruct Itinerary Path | Dataford Interview Questions

MakeMyTrip receives a list of directed itinerary segments, where each segment represents travel from one city to another. Given a starting city, reconstruct a valid route that uses every segment exactly once. If multiple valid routes exist, return the lexicographically smallest route by city code.

Formal Specification

Implement reconstruct_itinerary(itineraries, start). itineraries is a list of pairs [from_city, to_city], and start is the starting city code. Return a list of city codes containing the starting city and one destination for every itinerary segment. The input is guaranteed to contain at least one valid route beginning at start. City codes are uppercase strings.

Constraints

1 <= len(itineraries) <= 10^5
Each itinerary segment contains exactly two city codes
City codes contain exactly 3 uppercase letters
A valid route beginning at start exists
Every segment must be used exactly once

Function Signature

def reconstruct_itinerary(itineraries, start):

Your question is Reconstruct Itinerary Path. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Formal Specification

Constraints

1 <= len(itineraries) <= 10^5
Each itinerary segment contains exactly two city codes
City codes contain exactly 3 uppercase letters
A valid route beginning at start exists
Every segment must be used exactly once

Function Signature

def reconstruct_itinerary(itineraries, start):

Your question is Reconstruct Itinerary Path. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.