Coding - Cheapest Flights Within K Stops

Here is the full interview question "Coding - Cheapest Flights Within K Stops" asked at Uber:

Problem Statement: There are n cities connected by some number of flights. You are given an array flights where flights[i] = [from_i, to_i, price_i] indicates a flight from city from_i to city to_i with a price of price_i.

You are also given three integers: src, dst, and k. Return the cheapest price from city src to city dst with at most k stops. If there is no such route, return -1.

Examples:

1. Example 1: Input: n = 4, flights = [[0,1,100],[2,1,10],[1,2,100],[0,3,1000],[2,0,50]], src = 0, dst = 2, k = 0 Output: 50 Explanation: The cheapest price from city 0 to city 2 with at most 0 stops is 50. You can go directly from city 0 to city 2.

2. Example 2: Input: n = 3, flights = [[0,1,10],[1,2,20],[0,2,30]], src = 0, dst = 2, k = 1 Output: 20 Explanation: The cheapest price from city 0 to city 2 with at most 1 stop is 20. You can go from city 0 to city 1, then city 1 to city 2.

3. Example 3: Input: n = 4, flights = [[0,1,1],[1,2,2],[2,3,1]], src = 0, dst = 3, k = 2 Output: 4 Explanation: The cheapest price from city 0 to city 3 with at most 2 stops is 4. You can go from city 0 to city 1, then city 1 to city 2, and then city 2 to city 3.

Constraints:

• 1 <= n <= 100
• 0 <= flights.length <= (n * (n - 1) / 2)
• 0 <= src, dst <= n - 1
• src != dst
• 1 <= price_i <= 10^5
• k >= 0

Hints:

• You can model this problem as a graph and use Dijkstra's algorithm or Bellman-Ford algorithm to solve it.

Solution: `python from heapq import heappush, heappop from collections import defaultdict

class Solution: def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int: graph = defaultdict(list) for u, v, w in flights: graph[u].append((v, w))

    dist = [float('inf')] * n
    dist[src] = 0
    
    for _ in range(k + 1):
        temp = dist.copy()
        for u in range(n):
            for v, w in graph[u]:
                if dist[u] != float('inf'):
                    temp[v] = min(temp[v], dist[u] + w)
        dist = temp
    
    return -1 if dist[dst] == float('inf') else dist[dst]

`

I found this problem on LeetCode. The problem statement, examples, constraints, and hints are from the LeetCode problem page. The solution is a Python code snippet that uses Dijkstra's algorithm to solve the problem.