Cheapest Route Within a Stop Limit

1. Problem Statement

You are given one-way flight routes between cities, each with a cost, plus a source, a destination, and a maximum number of intermediate stops k. Find the cheapest total cost from source to destination using at most k intermediate stops, or -1 if no such route exists.

2. Live Coding Format

Work in the provided coding workspace while explaining your decisions to the live interviewer. Validation may use inline tests, examples, comments, or a verbal walkthrough.

3. Key Focus Areas

1
Problem clarification and contract
2
Approach exploration and optimality
3
Think-aloud communication and pacing
4
Implementation correctness
5
Code quality and language fluency
6
Tests and dry run
7
Debugging and self-correction
8
Complexity analysis
9
Follow-up performance

4. What Strong Candidates Should Demonstrate

Clarify how stops are counted, cost sign, and no-route behavior before coding.
Explain a brute-force baseline, show why it grows exponentially, and improve it to a polynomial-time approach that respects the stop limit.
Think aloud while implementing readable, correct code that counts stops correctly.
Validate with explicit expected outputs and a top-to-bottom dry run.
Analyze time and space complexity and handle a focused follow-up extension.

Want interactive feedback?

Practice this problem in the live coding workspace while the interviewer probes your clarification, implementation, trade-offs, and validation.

Continue to Dashboard

Core Concepts

Hidden because they name the technique, which a real interviewer would not tell you.

Show core concepts

Shortest PathsGraphsDynamic ProgrammingComplexity Analysis

Continue preparing

Build a complete software engineer mock interview plan

Explore this interview track →View the complete guide →

Prepare by company

Google interview guide

Related Coding / DSA