GOOGLE | L5 | BANGALURU |
Anonymous User
1950
GoogleSystem DesignLow Level DesignObject-Oriented DesignInterview

Google mostly prefer Graphs, Trees and String questions.

  1. Given 2 cities you have to find the minimum price of flights to go from 1 city to another. You can change a maximum of 2 cities in between. You are given price between 2 cities
  2. If there is one thread changing the prices of flights and multiple threads reading the flights price map to calculate minimum price, What will you do?

CODE :

int minPriceBwCities( String departure, String arraival){
  int noOfHolds = 0;
  int minPrice = Integer.MAX_VALUE;
  
  //currentstop, priceTillNow, noOfHolds
  Queue< Pair<String, int[]> > stops = new LinkedList<>();

  stops.add(new Pair{departure, new int [0, 0]});

  while(!stops.isEmpty()){
    //currentstop, priceTillNow, noOfHolds
    Pair<String, int[]> curruntStop = stops.poll();

    if( currentStop.getValue()[0]> minPrice || currentStop.getValue()[1] > 2 ) continue;

    List<Pair<String, int[]>> nextStops = departureArraivalMap.get(curruntStop.getKey());
    // arraival , price
    
    for(Pair<String, Integer> nextStop : nextStops) {

      if(nextStop.getKey() == arraival){
        minPrice=Math.min(minPrice, currentStop.getValue()[0]+nextStop.getValue());
      }
      else{
        
if(currentStop.getValue()[0]+NextStop.getValue() < minPrice && currentStop.getValue()[1] <2){  

         		stops.add(new Pair(nextStop.getKey(), new int(currentStop.getValue()[0]+NextStop.getValue(), currentStop.getValue()[1]+1) )),      
        }
      }
    }
  }
  return minPrice;
}

Above code will give TLE :

It should be done using DP

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<vector<int>> dp(k+2, vector<int>(n,INT_MAX));
        for(int i=0;i<=k+1;i++)dp[i][src]=0;
        for(int i=1;i<=k+1;i++) {
            for(auto &f: flights) {
                int start = f[0];
                int end = f[1];
                int cost = f[2];
                if(dp[i-1][start]!=INT_MAX) {
                    dp[i][end]= min(dp[i][end], dp[i-1][start]+cost);
                }
            }
        }
        return dp[k+1][dst]==INT_MAX?-1:dp[k+1][dst];
    }
};
Comments (9)