Related Coding / DSA
Cheapest Route Within a Stop Limit
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.
1. Problem Statement
You have two identical bulbs and a building with F floors (numbered 1 to F). There is some unknown critical threshold T (1 ≤ T ≤ F + 1) such that: - A bulb survives if dropped from any floor ≤ T - 1. - A bulb breaks if dropped from any floor ≥ T. - T = F + 1 means the bulb survives from every floor in the building. A broken bulb cannot be reused. Return the minimum number of drops needed in the worst case to guarantee identifying T. Start with any clarifying questions, then explain your approach.
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
- 1Two-bulb constraint modelling
- 2Why binary search fails with only two bulbs
- 3Triangular-step strategy derivation
- 4Optimal step-size calculation
- 5Worst-case drop count analysis
4. What Strong Candidates Should Demonstrate
- ✓Model the two-bulb constraint: after the first bulb breaks you must use a linear scan with the second.
- ✓Derive the triangular-step strategy: drop the first bulb at intervals of n, n-1, n-2, … floors.
- ✓Compute the optimal step size for a given floor count (smallest n with n*(n+1)/2 ≥ F).
- ✓Analyse worst-case drops and compare with naive binary search (which requires more than two bulbs).
Want interactive feedback?
Practice this problem in the live coding workspace while the interviewer probes your clarification, implementation, trade-offs, and validation.
Continue to DashboardCore Concepts
Math / CombinatoricsSearch StrategyWorst-Case Optimisation
Continue preparing
Build a complete software engineer mock interview plan
Prepare by company
Related Coding / DSA
Count Connected Land Regions in a Grid
Given a 2D grid of land and water cells, count the number of distinct connected land regions, where cells are connected horizontally or vertically.
Related Coding / DSA
Count Contiguous Runs Summing to a Target
Given a sequence of integers (possibly negative) and a target sum, count how many contiguous subarrays sum exactly to the target.
Related Coding / DSA
Currency Conversion via Exchange Rate Graph
Given a list of direct exchange rates, find the effective conversion rate between any two currencies by multiplying rates along a path in a directed graph.