Quick Overview

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.

Find cheapest flight with at most K stops

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

## 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`.

Quick Answer: 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.

You are given a directed weighted graph representing flights between cities. Cities are labeled from 0 to n - 1. Each flight has a non-negative price. Given a source city src, a destination city dst, and an integer K, return the minimum total cost to travel from src to dst using at most K stops. A stop is an intermediate city between src and dst, so using at most K stops means you may take at most K + 1 flights. If no valid route exists, return -1.

Constraints

  • 1 <= n <= 100
  • 0 <= len(flights) <= n * (n - 1)
  • Each flight is represented as [from, to, price]
  • 0 <= from, to < n
  • from != to
  • 0 <= price <= 10000
  • 0 <= src, dst < n
  • 0 <= K <= n - 1
  • All flights are directed

Examples

Input: (4, [[0,1,100],[1,2,100],[2,3,100],[0,3,500]], 0, 3, 1)

Expected Output: 500

Explanation: With at most 1 stop, at most 2 flights are allowed. The route 0 -> 1 -> 2 -> 3 uses 2 stops, so it is invalid. The direct route 0 -> 3 costs 500.

Input: (4, [[0,1,100],[1,2,100],[2,3,100],[0,3,500]], 0, 3, 2)

Expected Output: 300

Explanation: With at most 2 stops, the route 0 -> 1 -> 2 -> 3 is allowed and costs 300, which is cheaper than the direct route.

Hints

  1. At most K stops means at most K + 1 edges. Consider tracking the best cost using a limited number of edges.
  2. A shortest path algorithm that ignores the number of flights taken may choose an invalid route. Try a bounded Bellman-Ford style relaxation.

Loading coding console...