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

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.

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

Expected Output: -1

Explanation: With K = 0, only direct flights are allowed. There is no direct flight from 0 to 2.

Input: (3, [[0,1,10],[1,2,20]], 1, 1, 0)

Expected Output: 0

Explanation: The source and destination are the same city, so the minimum cost is 0 without taking any flights.

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

Expected Output: 700

Explanation: At most 3 flights are allowed. The route 0 -> 2 -> 3 -> 4 costs 700. The cheaper route 0 -> 1 -> 2 -> 3 -> 4 costs 400 but uses 4 flights, so it is invalid.

Input: (3, [[0,1,200],[0,1,50],[1,2,50],[0,2,120]], 0, 2, 1)

Expected Output: 100

Explanation: There are duplicate flights from 0 to 1. Taking the cheaper one, then 1 -> 2, costs 50 + 50 = 100.

Solution

def solution(n, flights, src, dst, K):
    INF = 10**15
    costs = [INF] * n
    costs[src] = 0

    # We may take at most K + 1 flights.
    # Each iteration allows paths using one additional flight.
    for _ in range(K + 1):
        next_costs = costs[:]
        for u, v, price in flights:
            if costs[u] != INF and costs[u] + price < next_costs[v]:
                next_costs[v] = costs[u] + price
        costs = next_costs

    return -1 if costs[dst] == INF else costs[dst]

Time complexity: O((K + 1) * E), where E is the number of flights. Space complexity: O(n).

Hints

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

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.