Cracking the Coding Interview

Saptarshi Chatterjee

·

Follow

27 min read

·

Dec 15, 2018

--

Share

1. Given a directed, acyclic graph of N nodes. Find all possible paths from node 0 to node N-1, and return them in any order.

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> result = new ArrayList();
        find(graph, result, new ArrayList(), 0);
        return result;
    }
    public void find(int[][] graph, List<List<Integer>> result, List<Integer> running, int index) {
        running.add(index);//just adding node as it's acyclic.Would check visited otherwise
        if(index == graph.length -1 )
            result.add(running); //able to reach last node.hence ans 
        else
            for(int node : graph[index])//for every connected node, same DFS.check visited for cyclic
                find(graph, result, new ArrayList(running), node);
    }
}

2. Find Pivot Index: sum of elements at lower indexes is equal to the sum of elements at higher indexes.

class Solution {
    public int pivotIndex(int[] nums) {
        int right = 0, left = 0;
        for(int i = 0; i < nums.length; i++) right += nums[i];
        for(int i = 0; i < nums.length; i++){
            if(i>0) left +=  nums[i-1]; //for i=0 left=empty,
            right -= nums[i];//for i=0 right all but ind 0
            if(left == right) return i;
        }
        return -1;
    }
}

3. Given coins of different denominations and a total amount of money, compute the number of combinations that make up that amount. Amount = 5, coins = [1, 2, 5] Sol => 4 . 5=5,5=2+2+1, 5=2+1+1+1, 5=1+1+1+1+1

class Solution {
    HashMap<String, Integer> memo = new HashMap<String, Integer>();
    public int solve(int[] coins, int amount, int startFrom) {
        //0$left, so we can reach 1 way
        if(amount == 0) return 1;
        //already -ve amount means this combination wont work
        if(startFrom < 0 || amount < 0) return 0;
        //Moving right to left, map key where starting and how much left
        int exist = memo.getOrDefault(startFrom+"#"+amount, -1);
        //If already computed dont recompute
        if(exist >= 0) return exist;
        //If we take this, remaining amount adjusted,DONT move left 
        // so that we can take this again
        int taken =  solve(coins, amount-coins[startFrom], startFrom );
        //If we dont take this remaining amount stays same but move to left
        int notTaken = solve(coins, amount, startFrom -1 );
        int memoOnStartAndAmount = taken + notTaken…