How should I practice Cheapest Flights Within K Stops?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Goldman Sachs onsite interview problems in FastPrep.

Is Cheapest Flights Within K Stops associated with Goldman Sachs?

FastPrep tags this as a Goldman Sachs onsite interview coding practice problem when the problem catalog has that company and stage context.

Problem · Array

Cheapest Flights Within K Stops

Learn this problem

● Medium

Goldman SachsFULLTIMEONSITE INTERVIEW

Problem statement

There are n cities labeled from 0 to n - 1. Each directed flight [from, to, price] travels from one city to another for the given price.

Return the minimum price of a route from src to dst that uses at most k intermediate stops. Return -1 if no such route exists.

Function

findCheapestPrice(n: int, flights: int[][], src: int, dst: int, k: int) → int

Examples

Example 1

n = 4flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]]src = 0dst = 3k = 1return = 700

With at most one intermediate stop, the cheapest valid route is 0 -> 1 -> 3.

Example 2

n = 3flights = [[0,1,100],[1,2,100],[0,2,500]]src = 0dst = 2k = 0return = 500