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 Expedia.

What role is this question designed for?

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

Find a Canonical Shortest Round Trip Through Flights

Quick Overview

Find a directed flight route that leaves a starting airport and returns in the fewest hops, using a canonical tie-break among equal routes. The problem examines graph reachability, shortest-cycle reasoning, lexicographic ordering, duplicate edges, self-loops, impossible cases, and adjacency-processing cost.

Company: Expedia

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

## Find a Canonical Shortest Round Trip Through Flights ### Problem Implement `shortestRoundTrip(flights, start) -> route`. Each element of `flights` is a directed flight `[from, to]`. Return a route that starts at `start`, follows one or more listed flights, and returns to `start` using the minimum possible number of flights. Include `start` at both ends of the returned array. If several shortest round trips exist, return the lexicographically smallest full airport sequence. Airport codes compare by ordinary ASCII order at the first differing character; if one code is a prefix of another, the shorter code comes first. Return an empty array if no round trip exists. ### Portable Contract - `flights` is a JSON array of two-string arrays `[from, to]`. - `0 <= flights.length <= 8,000`. - Each airport code contains `1` through `8` uppercase ASCII letters `A` through `Z`. - There are at most `4,000` distinct airport codes across `flights` and `start`. - Flights are directed. Duplicate flight pairs are allowed but do not create a different airport sequence. - A self-loop `[start, start]` is a valid one-flight round trip and returns `[start, start]`. - Do not modify `flights`. - Let `B` be the compact UTF-8 JSON byte length of `[flights,start]`: no whitespace outside strings, with every quote, comma, and bracket counted. Inputs satisfy `B <= 160,000`. - Let `R` be the compact UTF-8 JSON byte length of the returned string array under the same rule. Inputs guarantee `R <= 64,000`, so the serialized input plus result is at most `224,000` bytes. - Target `O((V + E) log E)` time or better and `O(V + E)` auxiliary space for distinct airports `V` and listed flights `E`. All four languages use only strings and homogeneous nested string arrays: `list[list[str]]` and `list[str]` in Python, arrays in JavaScript, `List<List<String>>` and `List<String>` in Java, and `vector<vector<string>>` and `vector<string>` in C++. ```hint Separate reachability from tie-breaking First determine how many flights are needed to get back to the start; then use that information to compare only choices that can still complete a shortest route. ``` ```hint Direct every search correctly Distances to the start are easier to compute when incoming and outgoing adjacency are not confused. ``` ### Examples ```text flights = [["SFO", "LAX"], ["LAX", "SEA"], ["SEA", "SFO"], ["LAX", "SFO"]] start = "SFO" route = ["SFO", "LAX", "SFO"] ``` ```text flights = [["A", "C"], ["C", "A"], ["A", "B"], ["B", "A"]] start = "A" route = ["A", "B", "A"] ``` ```text flights = [["A", "B"], ["B", "C"]] start = "A" route = [] ``` ### Discussion Requirements - Explain why a depth-first search can find some round trip but does not by itself guarantee the shortest one. - State how the algorithm guarantees one canonical answer among equal-length routes. - Cover duplicate flights, a self-loop, an airport that cannot return, and multiple shortest cycles. - Account for the cost of sorting or otherwise ordering adjacency lists.

Quick Answer: Find a directed flight route that leaves a starting airport and returns in the fewest hops, using a canonical tie-break among equal routes. The problem examines graph reachability, shortest-cycle reasoning, lexicographic ordering, duplicate edges, self-loops, impossible cases, and adjacency-processing cost.

Each element of `flights` is a directed flight `[from, to]` between two airport codes. Starting from the airport `start`, return a route that follows one or more listed flights and comes back to `start` using the fewest possible flights. The returned array lists every airport in visit order and includes `start` at both ends, so a route of `k` flights returns `k + 1` codes. If several different routes tie for the fewest flights, return the **lexicographically smallest full airport sequence**. Sequences are compared element by element from the front; two airport codes compare by ordinary ASCII order at the first differing character, and if one code is a prefix of the other, the shorter code comes first (so `"AA"` precedes `"AAB"`, and `"AAB"` precedes `"B"`). Return an empty array if no round trip exists. Additional rules: - Flights are directed: `["A", "B"]` does not let you fly from `B` to `A`. - Duplicate flight pairs may appear in `flights`; they do not create a different airport sequence. - A self-loop `["X", "X"]` is a valid one-flight round trip, so `start = "X"` returns `["X", "X"]`. - `start` is an airport code and does not have to appear anywhere in `flights`. - Do not modify `flights`. ### Example 1 ``` Input: flights = [["SFO","LAX"],["LAX","SEA"],["SEA","SFO"],["LAX","SFO"]] start = "SFO" Output: ["SFO","LAX","SFO"] ``` `SFO -> LAX -> SFO` uses 2 flights. `SFO -> LAX -> SEA -> SFO` also gets home, but it uses 3, so the 2-flight route wins. ### Example 2 ``` Input: flights = [["A","C"],["C","A"],["A","B"],["B","A"]] start = "A" Output: ["A","B","A"] ``` `A -> B -> A` and `A -> C -> A` both use 2 flights, the minimum. The tie-break compares the two full sequences `["A","B","A"]` and `["A","C","A"]` position by position; `"B"` precedes `"C"`, so the first one is returned. ### Example 3 ``` Input: flights = [["A","B"],["B","C"]] start = "A" Output: [] ``` No listed flight ever returns to `A`, so there is no round trip.

Constraints

0 <= flights.length <= 8,000
flights[i] is a two-element array [from, to] of airport codes
Each airport code contains 1 through 8 uppercase ASCII letters A through Z
There are at most 4,000 distinct airport codes across flights and start
start is an airport code and need not appear in flights
Flights are directed; duplicate flight pairs are allowed but do not create a different airport sequence
A self-loop [start, start] is a valid one-flight round trip and returns [start, start]
Do not modify flights
Let B be the compact UTF-8 JSON byte length of [flights, start]: no whitespace outside strings, with every quote, comma, and bracket counted. Inputs satisfy B <= 160,000
Let R be the compact UTF-8 JSON byte length of the returned string array under the same rule. Inputs guarantee R <= 64,000, so the serialized input plus result is at most 224,000 bytes
Target O((V + E) log E) time or better and O(V + E) auxiliary space for V distinct airports and E listed flights

Examples

Input: ([],'A')

Expected Output: []

Input: ([['A','A']],'A')

Expected Output: ['A','A']

Hints

A round trip has two halves: getting away from `start`, and getting back to it. One of those halves can be answered for every airport at once by a single search -- decide which half, and which direction that search has to run in.
Once you know, for every airport, how many flights it still needs to reach `start`, an airport is usable at a given step only when that number equals the number of flights you have left to spend. Every candidate route then has the same length, which is what makes a step-by-step choice safe.
Decide once, up front, what order you will consider each airport's onward flights in, and make sure repeated flight pairs cannot disturb that order.

Quick Overview