Reconstruct Itinerary

HardGraphseulerian path

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given a list of airline tickets, where tickets[i] = [from, to] is a one-way flight between two airports identified by three uppercase letters. The traveler starts at "JFK" and must use **every** ticket exactly once. Duplicate tickets may appear and each copy must be used. At least one valid itinerary is guaranteed to exist. If there are several, return the one that is **lexicographically smallest** when the itinerary is read as a single sequence of airport codes (compare airport by airport, e.g. ["JFK","ATL"] comes before ["JFK","BOS"]). Return the itinerary as a list of airports, starting with "JFK", of length tickets.length + 1.

Examples

Input: tickets = [["JFK","SEA"],["SEA","ORD"],["ORD","JFK"],["JFK","ATL"]]
Output: ["JFK","SEA","ORD","JFK","ATL"]
Flying to ATL first would strand the traveler with unused tickets, so the smallest valid itinerary visits SEA first.
Input: tickets = [["JFK","BOS"],["JFK","AUS"],["AUS","JFK"]]
Output: ["JFK","AUS","JFK","BOS"]
AUS sorts before BOS, and taking it first still uses every ticket.

Constraints

  • 1 <= tickets.length <= 300
  • from.length == to.length == 3, uppercase letters
  • from != to
  • A valid itinerary starting at "JFK" always exists

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.