Fewest Bus Boardings Between Two Stops
Updated
Problem statement
A city runs routes.length buses. Bus i drives around the stops listed in routes[i] again and again, so once you are on it you can get off at any stop in that list.
You are standing at stop source and want to get to stop target. You can only move by bus. You can change from one bus to another at any stop that both of them visit.
Return the fewest buses you need to board. If source and target are the same stop, return 0. If no chain of buses gets you to target, return -1.
Function
numBusesToDestination(routes: int[][], source: int, target: int) → intExamples
Example 1
routes = [[5,20,33],[33,1,18],[20,18],[18,41]]source = 5target = 41return = 3Only bus 0 stops at 5, so you board it first (1 bus) and can reach 20 and 33. Bus 1 (shares stop 33) and bus 2 (shares stop 20) both reach 18, so 18 costs 2 buses. Only bus 3 stops at 41, and you board it at 18. That makes 3 buses.
Example 2
routes = [[4,10],[12,14]]source = 4target = 14return = -1Bus 0 visits stops 4 and 10. Bus 1 visits stops 12 and 14. The two buses share no stop, so you can never change from bus 0 to bus 1. The answer is -1.
Example 3
routes = [[6,2,8]]source = 9target = 9return = 0You already stand at the target stop, so you board no bus. The answer is 0, even though no bus stops at 9.
Constraints
1 <= routes.length <= 5001 <= routes[i].length <= 5000, and all theroutes[i].lengthvalues add up to at most5000.- The stops inside one
routes[i]are all different. 0 <= routes[i][j], source, target <= 999999
More Rippling Onsite Interview questions
- Filter, Sort, and Deduplicate Scheduled TasksPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Stateful Log Transform and SearchPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Camel CardsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Corporate Card Expense RulesOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Limit an Organization Tree's HeightPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Delivery Cost TrackerPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Maximum Currency Conversion Along a Simple PathPHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Top K Frequent WordsPHONE SCREEN · ONSITE INTERVIEW · Seen Aug 2026
- Future-Effective Employee SalaryONSITE INTERVIEW · Seen Aug 2026
- Filter and Sort Scheduled TasksONSITE INTERVIEW · Seen Jul 2026
Similar questions at other companies
- Jump Game IVZomato / Eternal · ONSITE INTERVIEWZomato / Eternal interview questions
- Largest Island After One FlipOracle · ONSITE INTERVIEWOracle interview questions
- Bus RoutesBloomberg LP · PHONE SCREENBloomberg LP interview questions
- Linked Merchants Within Two HopsStripe · PHONE SCREENStripe interview questions
- Insert an Employee into an Organization HierarchyWaymo · PHONE SCREENWaymo interview questions
- Shortest Path Through Numbers Sharing a DigitGoogle · PHONE SCREENGoogle interview questions
- Fewest Buses with the Full RouteMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Minimum Bus Routes to a DestinationPinterest · PHONE SCREEN · ONSITE INTERVIEWPinterest interview questions
- Process Shopping Records, Promotions, and Display OrderInstacart · PHONE SCREEN · ONSITE INTERVIEWInstacart interview questions
- Budgeted API Inference with Out-of-Order FeedbackOpenAI · ONSITE INTERVIEWOpenAI interview questions
Interview reports that mention this question
Rippling interview experiences
- Rippling No-Level Older Reports: 31 Experiences (Part 6 of 6)
- Rippling No-Level Onsite Loops: 24 Experiences (Part 5 of 6)
- Rippling No-Level Screens and Loops: 18 Experiences (Part 4 of 6)
- Rippling No-Level Coding Screens: 37 Experiences (Part 3 of 6)
- Rippling No-Level Design, Screens: 30 Experiences (Part 2 of 6)