Find cheapest flight with at most K stops

Q: Find cheapest flight with at most K stops

This is a Coding & Algorithms interview question from Uber for Software Engineer roles. View the full question and solution on PracHub.

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

Problem

You are given a directed weighted graph representing flights between cities.

Inputs

An integer n : number of cities, labeled 0..n-1 .
A list flights , where each element is [from, to, price] meaning there is a flight from city from to city to that costs price .
Two integers src and dst : the start and destination cities.
An integer K : the maximum number of stops allowed, where a stop is an intermediate city between src and dst .
- Equivalently, you may take at most K+1 flights (edges).

Output

Return the minimum total cost to travel from src to dst using at most K stops. If it is not possible, return -1.

Notes / Clarifications

You may assume all price values are non-negative integers.
The route must follow the directed edges as given in flights .

Example

n = 4
flights = [[0,1,100],[1,2,100],[2,3,100],[0,3,500]]
src = 0, dst = 3, K = 1

The cheapest valid route is 0 -> 1 -> 2 -> 3 is not allowed (2 stops), so the answer is 500 via 0 -> 3.