Dijkstra and Bellman ford algorithm

Coding keep your coding sharp
1

Question

cheapest-flights-within-k-stops

We discussed Dijkstra’s and Bellman ford approaches.

Is it for me?

Are you an engineering manager who wants to keep your coding skills sharp?
Are you Software engineer who wants to move sometime in 1+ years?

If you answered YES to any of the questions - You have come to the right place.

How to Join Us

Join us and practice coding
Every Saturday 11:00 am pst

**To JOIN just click Launch Meeting - Zoom

#systemdesign #interview #softwareengineering #facebook #google #amazon #computerscience #algorithms #datastructures

2

// Depth-First-Search with Memoization

class Solution {

private int[][] adjMatrix;
private HashMap<Pair<Integer, Integer>, Long> memo;

public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
    
    this.adjMatrix = new int[n][n];
    this.memo = new HashMap<Pair<Integer, Integer>, Long>();
    
    for(int[] flight: flights) {
        this.adjMatrix[flight[0]][flight[1]] = flight[2];
    }
    
    long ans = this.findShortest(src, k, dst, n);
    return ans >= Integer.MAX_VALUE ? -1 : (int)ans;
}

public long findShortest(int node, int stops, int dst, int n) {
    if(node == dst)
        return 0;
    
    if(stops < 0)
        return Integer.MAX_VALUE;
    
    Pair<Integer, Integer> key = new Pair<Integer, Integer>(node, stops);
    
    if(this.memo.containsKey(key))
        return this.memo.get(key);
    
    long ans = Integer.MAX_VALUE;
    for(int i=0;i<n;i++) {
        int wt = this.adjMatrix[node][i];
        
        if(wt > 0) {
            ans = Math.min(ans, this.findShortest(i, stops-1, dst, n) + wt);
        }  
    }
    
    this.memo.put(key, ans);
    return ans;
}

}