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 medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Stripe.

What role is this question designed for?

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

How to find the cheapest flight within K stops

Quick Overview

This question evaluates understanding of graph algorithms and constrained shortest-path modeling, focusing on reasoning about weighted directed edges, transfer limits, and cost optimization within a travel network; it belongs to the Coding & Algorithms domain.

Company: Stripe

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Problem 1: Minimize multi-person debt settlement Given a group of people with multiple loan records, find the minimum number of transactions to settle all debts so everyone's balance is zero. Core idea: First compute each person's net balance, and only focus on those whose net amount is non-zero. Then use backtracking or greedy matching to cancel positive and negative amounts against each other. For example, if someone owes 50 and another is owed 50, a single transaction settles both — minimizing the total number of transactions. Follow-up: If the debt relationships are very complex, involving hundreds of people, can your algorithm still maintain efficiency? Problem 2: Cheapest flights within K stops Given a list of flights with prices, find the lowest-cost path from source to destination within K stops. Approach: This is a classic graph shortest-path problem. You can solve it with dynamic programming where dp[i][k] represents the minimum fare to reach node i within k steps. Alternatively, use a modified Dijkstra's algorithm with a priority queue that also tracks the current number of stops, ensuring you don't exceed K stops while finding the lowest price. Follow-up: If the airline network is very large, or you need to support real-time price updates, how would you optimize?

Quick Answer: This question evaluates understanding of graph algorithms and constrained shortest-path modeling, focusing on reasoning about weighted directed edges, transfer limits, and cost optimization within a travel network; it belongs to the Coding & Algorithms domain.

There are `n` cities (numbered `0..n-1`) and a list of directed flights. `flights[i] = [u, v, price]` means there is a flight from city `u` to city `v` with cost `price` (`price > 0`). Multiple different flights may connect the same pair of cities. Given a source `src`, destination `dst`, and integer `k`, return the **minimum total price** to travel from `src` to `dst` using **at most `k` stops** (i.e., at most `k + 1` flight segments). If it is impossible to reach the destination within the limit, return `-1`. If `src == dst` the answer is `0` (no flights needed).

Constraints

1 <= n; cities are numbered 0..n-1
0 <= len(flights); flights[i] = [u, v, price] with 0 <= u, v < n and price > 0
0 <= src, dst < n
0 <= k (k is the max number of stops; at most k+1 flight segments)
Edges are directed; multiple edges may connect the same (u, v) pair

Examples

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

Expected Output: 700

Explanation: With at most 1 stop, the path 0->1->3 costs 100+600=700. The cheaper-per-edge route 0->1->2->3 (100+100+200=400) needs 2 stops, which exceeds the limit, so 700 is the best feasible answer.

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

Expected Output: 200

Explanation: With 1 stop allowed, 0->1->2 costs 100+100=200, cheaper than the direct flight 0->2 at 500.

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

Expected Output: 500

Explanation: With 0 stops, only a single direct segment is allowed, so the only option is 0->2 at 500.

Input: (2, [[0,1,50]], 0, 1, 0)

Expected Output: 50

Explanation: A single direct flight reaches the destination within 0 stops.

Input: (2, [], 0, 1, 5)

Expected Output: -1

Explanation: No flights exist, so the destination is unreachable regardless of the stop budget.

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

Expected Output: -1

Explanation: Reaching city 2 requires 2 segments (1 stop), but only 0 stops are allowed, so it is unreachable.

Input: (1, [], 0, 0, 0)

Expected Output: 0

Explanation: Source equals destination, so no flights are needed and the cost is 0.

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

Expected Output: 3

Explanation: Parallel edges connect the same city pairs; the algorithm picks the cheapest at each hop: 0->1 (1) + 1->2 (1) + 2->3 (1) = 3 within 2 stops.

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

Expected Output: 100

Explanation: The cheap chain to city 4 needs 3 stops; with only 1 stop allowed, the direct flight 0->4 at 100 is the only feasible option.

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

Expected Output: 20

Explanation: With 3 stops allowed, the 4-segment chain 0->1->2->3->4 (5*4=20) is feasible and far cheaper than the direct flight at 100.

Hints

k stops means at most k + 1 flight segments. Track the number of segments used in your search state, not just the current cost.
A plain Dijkstra that settles each node once can miss the cheapest answer, because a pricier path with fewer stops may be the only one that stays within the budget. Allow re-visiting a node if you can reach it using fewer segments than before.
Bellman-Ford is a clean alternative: relax all edges exactly k+1 times using a snapshot of distances from the previous round, so each round adds one more segment.
Handle src == dst (answer 0) and the unreachable case (return -1).

Quick Overview