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.

What difficulty level is this interview question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Uber.

What role is this question designed for?

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

Find cheapest flight with at most K stops

Q: Find cheapest flight with at most K stops

This question evaluates graph algorithm proficiency and problem-modeling skills, specifically working with directed weighted graphs to optimize path cost under a constraint on intermediate stops.

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.

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.

Find cheapest flight with at most K stops

Quick Overview

Problem

Inputs

Output

Notes / Clarifications

Example

Comments (0)

Find cheapest flight with at most K stops

Quick Overview

Problem

Inputs

Output

Notes / Clarifications

Example

Comments (0)