FastPrepFastest Flight Route Between Airports

Fastest Flight Route Between Airports

Airbnb logoAirbnb● MediumINTERNPHONE SCREEN

Updated

Problem statement

You are planning a trip between airports. Each airport has a three-letter code, such as SFO. You are given a list of one-way flights, where flights[i] = [fromi, toi] is a flight from airport fromi to airport toi that takes hours[i] hours.

Find the fastest way to get from origin to destination. The time of a route is the sum of the hours of its flights. You can take any number of flights, and there is no waiting time between them.

Return the airports on the fastest route, in order, starting with origin and ending with destination. If there is no way to reach destination, return an empty list.

Function

fastestRoute(flights: List<List<String>>, hours: int[], origin: String, destination: String) → List<String>

Examples

Example 1

flights = [["SFO","LAX"],["LAX","JFK"],["SFO","JFK"],["SFO","SEA"],["SEA","JFK"]]hours = [1,5,7,2,5]origin = "SFO"destination = "JFK"return = ["SFO","LAX","JFK"]

There are three ways to fly from SFO to JFK. The direct flight takes 7 hours. Going through SEA takes 2 + 5 = 7 hours. Going through LAX takes 1 + 5 = 6 hours, so it is the fastest route, even though it uses two flights.

Example 2

flights = [["BOS","ORD"],["ORD","DEN"],["DEN","BOS"]]hours = [3,2,4]origin = "DEN"destination = "ORD"return = ["DEN","BOS","ORD"]

Flights are one-way. The flight from ORD to DEN cannot be used to go from DEN to ORD. The only route is DEN to BOS (4 hours), then BOS to ORD (3 hours), for a total of 7 hours.

Example 3

flights = [["ATL","MIA"],["MIA","ATL"]]hours = [2,2]origin = "ATL"destination = "SEA"return = []

No flight lands at SEA, so there is no route from ATL to SEA. The answer is an empty list.

Constraints

  • 1 <= flights.length <= 104
  • flights[i].length == 2
  • hours.length == flights.length
  • 1 <= hours[i] <= 100
  • Every airport code in flights, origin and destination is exactly 3 uppercase English letters.
  • fromi != toi
  • No two flights have the same from and to airports.
  • origin != destination
  • There is at most one fastest route from origin to destination.

More Airbnb Phone Screen questions

Similar questions at other companies

Interview reports that mention this question

Airbnb interview experiences

All Airbnb interview questionsSee Airbnb hiring insights
Saved
class Solution {
    public List<String> fastestRoute(List<List<String>> flights, int[] hours, String origin, String destination) {
      // Write your code here.
    }
}
Checking account…