Interviews

Min Cost of Flight

user profile image
System made a post.

Min cost of flight from start to end if allowed at most k transfers.
Given all the flights in a string:
A->B,100,
B->C,100,
A->C,500,
If k = 1,from A to C the best route is A->B->C at the cost of 200.


public int minCost(String flights, String from, String to, int k) {
        if(from == to) return 0;
        if(flights.isEmpty()) return -1;

        int[][] edges = parseString(flights,from, to);
        Map minCostSet = new HashMap<>();
        minCostSet.put(0, 0);

        Queue prev = new ArrayDeque<>(); //previous level of nodes
        prev.add(0);

        while(k >= 0 && !prev.isEmpty()) {  //BFS
            Queue current = new ArrayDeque<>();
            for(int source: prev) {
                for(int destination = 0; destination < edges.length; destination++) {
                    if(edges[source][destination] > 0) {
                        int minCost = minCostSet.containsKey(destination) ? minCostSet.get(destination) : Integer.MAX_VALUE;
                        int newCost = Math.min(minCost, minCostSet.get(source) + edges[source][destination]);
                        if (minCost > newCost) {
                            minCostSet.put(destination, newCost);
                            current.add(destination);
                        }
                    }
                }
            }
            prev = current;
            k--;
        }
        return minCostSet.containsKey(edges.length - 1) ? minCostSet.get(edges.length - 1): -1;
    }

    private int[][] parseString(String flights, String start, String end) {
        Map map = new HashMap<>();
        List edges = new ArrayList<>();
        String[] f = flights.split(",");
        map.put(start, 0);
        map.put(end, -1);
        for(int i = 0; i < f.length; i+=2) {
            int idx = f[i].indexOf('-');
            String src = f[i].substring(0, idx);
            String des = f[i].substring(idx + 2);
            if(!map.containsKey(src)) {
                map.put(src, map.size() - 1);
            }
            if(!map.containsKey(des)){
                map.put(des, map.size() - 1);
            }
            if(map.get(src) != -1) {    //exclude flights that departs from the ultimate destination
                edges.add(new int[]{map.get(src), map.get(des), Integer.parseInt(f[i + 1])});
            }
        }
        int n = map.size();
        int[][] graph = new int[n][n];
        for(int[] edge: edges) {
            if(edge[1] == -1) edge[1] = n - 1;
            graph[edge[0]][edge[1]] = edge[2];
        }
        return graph;
    }



One-on-One Algorithm and Coding Training

One-on-One System Design Training

One-on-One Mock Interview

Get one-to-one training from Google Facebook engineers


Top-notch Professionals

Learn from Facebook, Google, Uber senior engineers interviewed 100+ candidates.aonecode.com
Most recent interview questions and system design topics gathered from aonecode alumnus.
One-to-one online classes. Get feedbacks from real interviewers.


Customized Private Class

Already a coding expert? - Advance straight to hard interview topics of your interest.
New to the ground? - Develop basic coding skills with your own designated mentor.
Days before interview? - Focus on most important problems in target company question bank.


Free Consultation

aonecoding@gmail.com