I was asked this question 787. Cheapest Flights Within K Stops in a FAANG company and I wrote the below solution.

After few hours I received a rejection email. Out of disbelief I asked the recruiter, if the interviewer gave any feedback. She was kind enough to provide the feedback, saying "the solution I provided is not the most optimal one". Can you please let me know if there is a much efficient solution?

class Solution:
    def findCheapestPrice(self, n, flights, src, dst, k) -> int:
        graph = [[] for _ in range(n)]
        for s,d,c in flights:
            graph[s].append((c,d))
        
        q = [(0,0,src)]
        heapq.heapify(q)
        best = {}
        while q:
            cost, stops, dest = heapq.heappop(q)
            if dest == dst:
                return cost
            
            if stops > k:
                continue
            for a_cost, node in graph[dest]:
                new_cost = (a_cost + cost)
                if (node,stops) not in best or new_cost < best[(node,stops)]:
                    heapq.heappush(q, (new_cost, stops+1, node)) 
                    best[(node,stops)] = new_cost
        return -1

Update: Read all your comments with respect to the additional complexity created by the heap. I am wondering, the advantage with heap is, It lets you exit early if the destination is found before K steps. Also, when the 'k' is small the log factor is negligble....

Butttttttttttttttt ...............If the world has come to this that the interviewers want the most optimized solution for a hard Leetcode problem, then I guess I will never get a job :) :) :)