Hard

Uber-styleGoogle-style

Cheapest Route Within a Stop Limit DSA Interview

Given one-way routes between cities each with a cost, find the cheapest total cost from a source city to a destination city using at most k intermediate stops.

Mock Interview with AI

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

Choose Python, JavaScript, Java, or C++, then solve while explaining your reasoning to the live interviewer.

Validation uses handwritten tests only. The MVP does not compile or run code, and it does not provide AI algorithm completion.

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
Handwritten tests and dry run
7
Debugging and self-correction
8
Complexity analysis
9
Follow-up performance

4. What Strong Candidates Should Demonstrate

✓Clarify stop-versus-edge counting, cost sign, and no-route behavior before coding.
✓Explain an exponential DFS baseline and improve to a stop-bounded relaxation approach.
✓Think aloud while implementing careful iteration-limited relaxation.
✓Validate with explicit expected outputs and a top-to-bottom handwritten dry run.
✓Analyze time and space complexity and handle a focused follow-up extension.

Evaluation Guide

This is an evaluation framework, not a single model answer. Strong designs may make different choices when their assumptions and trade-offs are explicit.

Problem clarification and contract

10%

Senior signals

✓Clarifies that k counts intermediate stops (so at most k+1 edges/flights are used), confirms costs are non-negative, and asks what to return when source equals destination.
✓Confirms whether multiple routes can exist between the same pair of cities with different costs.

Staff-level signals

◆Asks about the expected number of cities and routes to justify the chosen approach's complexity.

Common red flags

×Codes immediately while conflating 'stops' with 'edges used' without confirming the distinction.

Approach exploration and optimality

20%

Senior signals

✓Explains a DFS-enumeration baseline that explores all paths up to k stops, identifies the exponential blowup from revisiting overlapping subpaths, and improves to a stop-bounded Bellman-Ford-style relaxation that performs at most k+1 rounds of edge relaxation.
✓Explains why plain Dijkstra's algorithm does not directly respect a hard stop-count limit without modification, since it optimizes purely by cost.

Staff-level signals

◆Discusses why relaxing from a snapshot of the previous round's costs (rather than in-place updates) is necessary to correctly bound the number of edges used per round.

Common red flags

×Starts implementation without explaining an approach even after one interviewer prompt.
×Applies unmodified Dijkstra or plain BFS without addressing the stop-count constraint.

Think-aloud communication and pacing

10%

Senior signals

✓Explains the plan before coding and narrates the round-by-round relaxation and snapshot logic while implementing.
✓Paces the core solution to leave time for validation and the follow-up.

Common red flags

×Writes substantial code silently and cannot explain what the code is doing.

Implementation correctness

25%

Senior signals

✓Implements a correct k+1-round relaxation using a snapshot of costs from the previous round to avoid using more edges than allowed within a single round, returning -1 when the destination remains unreachable within the limit.
✓Handles source equal to destination (cost 0), k = 0 (direct flights only), no route at all, and multiple parallel routes between the same city pair.
✓Provides a convincing invariant argument for why exactly k+1 relaxation rounds bound the path to at most k intermediate stops.

Common red flags

×Relaxes edges in place within a round, allowing a single round to effectively use more than one additional edge and violating the stop limit.
×Final code contains a material correctness bug that the candidate does not identify.

Code quality and language fluency

15%

Senior signals

✓Produces readable, language-appropriate code with clear round-tracking, a snapshot/previous-cost array, and a sentinel for unreachable cities.

Common red flags

×Contains sentinel-value overflow or confusion between rounds and stops or syntax-level incoherence that prevents credible reasoning.

Handwritten validation, dry run, and debugging

10%

Senior signals

✓Provides explicit inputs and expected outputs before tracing the code from top to bottom, showing cost arrays after each relaxation round.
✓Covers source equal to destination, k = 0, an unreachable destination, and a case where a cheaper but longer route is excluded by the stop limit.
✓Finds and fixes an error independently, then re-validates the affected path.

Common red flags

×Claims the code works without a representative trace.

Complexity analysis and follow-up

10%

Senior signals

✓States time complexity proportional to k times the number of routes, and auxiliary space proportional to the number of cities, comparing this with the exponential DFS baseline.

Staff-level signals

◆Discusses how the approach would scale if k were very large relative to the number of cities.

Common red flags

×Cannot state the complexity of the implemented solution.
×Fails a reasonable follow-up despite having at least five minutes and receiving bounded clarification.

Trade-offs to articulate

DFS enumeration of all paths up to k stops is simple to state but can revisit overlapping subpaths exponentially many times.
A stop-bounded relaxation approach (limited-round Bellman-Ford style) achieves time proportional to k times the number of routes by processing a fixed number of rounds using a snapshot of the previous round's costs.
Unmodified Dijkstra's algorithm finds the globally cheapest route but does not respect a hard limit on the number of edges used, so it is not directly applicable without modification.

Practice follow-up questions

1.Coding follow-up: modify the solution to also return one actual cheapest route (the sequence of cities), not just its total cost, within the same stop limit.
2.Verbal extension: how would the approach change if route costs could change over time and queries needed to reflect the latest costs?

Want interactive feedback?

Practice this problem in the live coding workspace while the interviewer probes your clarification, algorithm, implementation, complexity, and handwritten tests.

Start Interview

Core Concepts

Shortest PathsGraphsDynamic ProgrammingComplexity Analysis