Algorithms for coding interview

BinarySearch.java

class Solution {
    public int search(int[] nums, int target) {
        
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            // if target is found
            if(nums[mid] == target){
                return mid;
            }
            // if target is greater than the middle element.
            else if(nums[mid] < target){
                left = mid + 1;
            }
            // if target is less than the middle
            else{
                right = mid - 1;
            }
        }
        return -1;
    }
}

BubbleSort.java

class Solution {
    public int[] sortArray(int[] nums) {
        bubbleSort(nums, nums.length);
        return nums;
    }
    
    // TC is O(n^2) and space complexity is O(1)
    public void bubbleSort(int[] array, int size){
        for(int i = 0; i < size; i++){
            // flag
            int swapped = 0;
            for(int j = 0; j < size - i - 1; j++){
                if(array[j] > array[j + 1]){
                    // swap
                    int swap = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = swap;
                    swapped = 1;
                }
            }
            // if list is already in ascending order
            if(swapped == 0) break;
        }
    }
}

BuildingMaxHeap.java

// Building max heap
public class Main {
    
    static int array[] = { 1, 3, 5, 4, 6, 13, 10, 
                      9, 8, 15, 17 };
    static int size = array.length;
    
    public static void main(String[] args) {
        
        buildMaxHeap(array, size);
        extractMax(array);
        increaseKey(array, 1, 90);
        printHeap(array, size);
    }
    
    static void maxHeapify(int[] array, int root, int size){
        // initialize largest as root
        int largest = root;
        // left and right child position in the array
        int left = 2 * root + 1;
        int right = 2 * root + 2;
        // we will check which element is largest (parent or left child or right child)
        if(left < size && array[left] > array[largest]){
            largest = left;
        }
        if(right < size && array[right] > array[largest]){
            largest = right;
        }
        // if parent is not the largest then swap parent with largest
        if(largest != root){
            int swap = array[root];
            array[root] =  array[largest];
            array[largest] = swap;
            // recursively heapify affected subtree
            maxHeapify(array, largest, size);
        }
    }
    
    static void buildMaxHeap(int[] array, int size){
        // last non-leaf
        int startIndex = (size / 2) - 1;
        for(int root = startIndex; root >= 0; root--){
            maxHeapify(array, root, size);
        }
    }
    
    static void printHeap(int[] array, int size){
        System.out.println("The heap is : ");
        // printing heap level wise
        for (int root = 0; root < size; root++){
            System.out.println(array[root]);
        }
    }
    
    // extracting max element and removing it from the tree (TC : O(logn))
    static void extractMax(int[] array){
        // if heap is empty
        if(size < 0){
            System.out.println("heap is empty");
        }
        int max = array[0];
        array[0] = array[size - 1];
        // decrease the size to delete the element
        size -= 1;
        maxHeapify(array, 0, size);
        System.out.println(max  + " is the maximum element.");
    }
    
    // for increasing the value of a particular node (TC : O(logn))
    static void increaseKey(int[] array, int index, int quantity){
        if(quantity < array[index]){
            System.out.println("you cannot decrease the value");
        }
        array[index] = quantity;
        // making it max heap again
        while(index > 0 && array[index/2] < array[index]){
            int swap = array[index];
            array[index] = array[index/2];
            array[index/2] = swap;
            index /= 2;
        }
    }
}

DijsktraAlgorithm.java

public class Main {
    
    static final int V = 9; 
    
    public static void main(String[] args) {
        int graph[][] = {{ 0, 4, 0, 0, 0, 0, 0, 8, 0 }, 
                         { 4, 0, 8, 0, 0, 0, 0, 11, 0 }, 
                         { 0, 8, 0, 7, 0, 4, 0, 0, 2 }, 
                         { 0, 0, 7, 0, 9, 14, 0, 0, 0 }, 
                         { 0, 0, 0, 9, 0, 10, 0, 0, 0 }, 
                         { 0, 0, 4, 14, 10, 0, 2, 0, 0 }, 
                         { 0, 0, 0, 0, 0, 2, 0, 1, 6 }, 
                         { 8, 11, 0, 0, 0, 0, 1, 0, 7 }, 
                         { 0, 0, 2, 0, 0, 0, 6, 7, 0 }};
        dijsktra(graph, 0);
    }
    
    static int selectMinDistance(int[] distance, boolean[] isIncluded){
        int vertex = -1;
        int minimum = Integer.MAX_VALUE;
        for(int i = 0; i < V; i++){
            if(isIncluded[i] == false && distance[i] < minimum){
                vertex = i;
                minimum = distance[i];
            }
        }
        return vertex;
    }
    
    static void printSolution(int[] distance){
        System.out.println("Vertex \t Distance from Source"); 
        for (int i = 0; i < V; i++) 
            System.out.println(i + "\t" + distance[i]);
    }
    
    static void dijsktra(int[][] graph, int source){
        int[] distance = new int[V];
        Arrays.fill(distance, Integer.MAX_VALUE);
        boolean[] isIncluded = new boolean[V];
        Arrays.fill(isIncluded, Boolean.FALSE);
        distance[source] = 0;
        for(int i = 0; i < V; i++){
            int u = selectMinDistance(distance, isIncluded);
            isIncluded[u] = true;
            for(int j = 0; j < V; j++){
                if(graph[u][j] != 0 && isIncluded[j] == false &&
                   distance[u] != Integer.MAX_VALUE &&
                   distance[u] + graph[u][j] < distance[j]){
                    distance[j] = distance[u] + graph[u][j];
                }
            }
        }
        printSolution(distance);
    }
}

FractionalKnapsack.java

public class Main {
    public static void main(String[] args) {
        
        // weight, profit of items and capacity of bag
        int[] weight = {2,3,5,7,1,4,1};
        int[] profit = {10,5,15,7,6,18,3};
        int capacity = 15;
        double maxProfit = greedyKnapsack(weight, profit, capacity);
        System.out.println(maxProfit);
    }
    
    static class Item{
        
        double weight, profit, profitPerUnitOfWeight;
        public Item(int weight, int profit){
            this.weight = weight;
            this.profit = profit;
            profitPerUnitOfWeight = profit / weight;
        }
    }
    
    static double greedyKnapsack(int[] weight, int[] profit, int capacity){
        
        // here we are creating a list of Item object so that we can sort them.
        List<Item> items = new ArrayList<>();
        for(int i = 0; i < weight.length; i++){
            items.add(new Item(weight[i], profit[i]));
        }
        items.sort((Item first, Item second) -> Double.compare(second.profitPerUnitOfWeight, first.profitPerUnitOfWeight));
        
        // we'll try to fill the bag with the object that has maximum profit per unit of weight
        double totalProfit = 0;
        for(Item item : items){
            double currentWeight = item.weight;
            double currentProfit = item.profit;
          
            // if we can take the whole object
            if(capacity - currentWeight >= 0){
                capacity -= currentWeight;
                totalProfit += currentProfit;
            }
          
            // if we can take only a portion of it
            else{
                double fraction = capacity / currentWeight;
                totalProfit += currentProfit * fraction;
                break;
            }
        }
        return totalProfit;
    }
}

HeapSort.java

// Building max heap
public class Main {
    
    static int array[] = { 1, 3, 5, 4, 6, 13, 10, 
                      9, 8, 15, 17 };
    static int size = array.length;
    
    public static void main(String[] args) {
        
        buildMaxHeap(array, size);
        heapSort(array);
        printHeap(array, size);
    }
    
    static void maxHeapify(int[] array, int root, int size){
        // initialize largest as root
        int largest = root;
        // left and right child position in the array
        int left = 2 * root + 1;
        int right = 2 * root + 2;
        // we will check which element is largest (parent or left child or right child)
        if(left < size && array[left] > array[largest]){
            largest = left;
        }
        if(right < size && array[right] > array[largest]){
            largest = right;
        }
        // if parent is not the largest then swap parent with largest
        if(largest != root){
            int swap = array[root];
            array[root] =  array[largest];
            array[largest] = swap;
            // recursively heapify affected subtree
            maxHeapify(array, largest, size);
        }
    }
    
    static void buildMaxHeap(int[] array, int size){
        // last non-leaf
        int startIndex = (size / 2) - 1;
        for(int root = startIndex; root >= 0; root--){
            maxHeapify(array, root, size);
        }
    }
    
    static void printHeap(int[] array, int size){
        System.out.println("The heap is : ");
        // printing heap level wise
        for (int root = 0; root < size; root++){
            System.out.println(array[root]);
        }
    }
  
    static void heapSort(int[] array){
        int heapSize = size;
        for(int i = array.length - 1; i > 0; i--){
            int swap = array[0];
            array[0] = array[i];
            array[i] = swap;
            heapSize -= 1;
            maxHeapify(array, 0, heapSize);
        }
    }
}

HuffmanEncoding.java

public class Main {
    public static void main(String[] args) {
        int numberOfCharacters = 4;
        char[] characterArray = {'a', 'b', 'c', 'd'};
        int[] frequencyArray = {50, 35, 5, 5};
        buildHuffmanTree(characterArray, frequencyArray, numberOfCharacters);
    }
    
    static void buildHuffmanTree(char[] characterArray, int[] frequencyArray , int numberOfCharacters){
        
        // for taking characters with less frequency first
        PriorityQueue<HuffmanNode> pq = new PriorityQueue<>(
            (HuffmanNode first, HuffmanNode second) ->
            first.frequency - second.frequency);
        
        for(int i = 0; i < numberOfCharacters; i++){
            HuffmanNode newNode = new HuffmanNode(frequencyArray [i], characterArray[i], null, null);
            pq.add(newNode);
        }
        
        // optimal merge pattern
        HuffmanNode root = null;
        while(pq.size() > 1){
            HuffmanNode first = pq.poll();
            HuffmanNode second = pq.poll();
            int frequency = first.frequency + second.frequency;
            HuffmanNode newNode = new HuffmanNode(frequency, '+', first, second);
            root = newNode;
            pq.add(newNode);
        }
        printCode(root, ""); 
    }
    
    static void printCode(HuffmanNode root, String s) 
    {   
        if(root == null) return;
        if (root.left == null && root.right == null) { 
            System.out.println(root.character + ":" + s);
        } 
        printCode(root.left, s + "0"); 
        printCode(root.right, s + "1"); 
    } 
}

class HuffmanNode{
    int frequency;
    char character;
    HuffmanNode left;
    HuffmanNode right;
    
    public HuffmanNode(int frequency, char character, 
                       HuffmanNode left, HuffmanNode right){
        this.frequency = frequency;
        this.character = character;
        this.left = left;
        this.right = right;
    }
}

InsertionSort.java

class Solution {
    public int[] sortArray(int[] nums) {
        // j = 1, because single element is always sorted
        for(int j = 1; j < nums.length; j++){
            // picking it up so that we don't loose this value
            int key = nums[j];
            // we start from the previous element
            int i = j - 1;
            // we continue finding the correct place for key
            while(i >= 0 && nums[i] > key){
                nums[i + 1] = nums[i];
                i -= 1;
            }
            //after finding correct place of the key, we insert it.
            nums[i + 1] = key;
        }
        return nums;
    }
}

JobSequencing.java

public class Main {
    public static void main(String[] args) {
        int[] deadline = {2, 1, 2, 1, 3};
        int[] profit = {100, 19, 27, 25, 15};
        char[] ids = {'a', 'b', 'c', 'd', 'e'};
        int timeAvailable = 3;
        jobScheduling(ids, deadline, profit, timeAvailable);
    }
    
    static void jobScheduling(char[] ids, int[] deadline, int[] profit, int timeAvailable){
        int numberOfJobs = ids.length;
        List<Job> jobs = new ArrayList<>();
        for(int i = 0; i < numberOfJobs; i++){
            Job newJob = new Job(ids[i], deadline[i], profit[i]);
            jobs.add(newJob);
        }
        jobs.sort((Job first, Job second) -> second.profit - first.profit);
        boolean[] isAvailable = new boolean[timeAvailable];
        char[] assignedJob = new char[timeAvailable];
        for(int i = 0; i < numberOfJobs; i++){
            for(int j = Math.min(timeAvailable - 1, jobs.get(i).deadline - 1); j >= 0; j--){
                // slot is available
                if(isAvailable[j] == false){
                    isAvailable[j] = true;
                    assignedJob[j] = jobs.get(i).id;
                    break;
                }
            }
        }
        for(char job : assignedJob){
            System.out.print(job + " ");
        }
    }
}
class Job{
    char id;
    int deadline;
    int profit;
    public Job(char id, int deadline, int profit){
        this.id = id;
        this.deadline = deadline;
        this.profit = profit;
    }
}

Knapsack.java

public class Main {
    public static void main(String[] args) {
        int[] weight = {10, 20, 30};
        int[] profit = {60, 100, 120};
        int capacity = 50;
        int quantity = weight.length;
        System.out.println(knapsack(weight, profit, capacity, quantity));
    }
    
    static int knapsack(int[] weight, int[] profit, int capacity, int quantity){
        int[][] dp = new int[quantity + 1][capacity + 1];
        for(int i = 0; i <= quantity; i++){
            for(int j = 0; j <= capacity; j++){
                if(i == 0 || j == 0) dp[i][j] = 0;
                else if(weight[i - 1] <= j){
                    dp[i][j] = Math.max(
                        profit[i - 1] + dp[i - 1][j - weight[i - 1]],
                        dp[i - 1][j]);
                }
                else dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[quantity][capacity];
    }
}

LinearSearch.java

public class Main {
    public static void main(String[] args) {
        int[] array = {10, 20, 30, 40, 50};
        int target = 30;
        System.out.print(linearSearch(array, target));
    }
  
    // search the array linearly
    public static int linearSearch(int[] array, int target){
        for(int i = 0; i < array.length; i++){
            if(array[i] == target){
                return i;
            }
        }
        return -1;
    }
}

LongestCommonSubsequence.java

public class Main {
    public static void main(String[] args) {
        String s1 = "pqprqrp";
        String s2 = "qpqrr";
        char[] first = s1.toCharArray();
        char[] second = s2.toCharArray();
        System.out.println("Length of LCS is "+ longestCommonSubsequence(first, second));
    }
    
    static int longestCommonSubsequence(char[] first, char[] second){
        int m = first.length;
        int n = second.length;
        int[][] dp = new int[m + 1][n + 1];
        for(int i = 0; i <= m; i++){
            for(int j = 0; j <= n; j++){
                // three conditions for solving longest common subsequence problem
                if(i == 0 || j == 0) dp[i][j] = 0;
                else if(first[i - 1] == second[j - 1]) dp[i][j] = 1 + dp[i - 1][j - 1];
                else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[m][n];
    }
}

MatrixChainMultiplication.java

public class Main {
    public static void main(String[] args) {
        int[] array = {1, 2, 1, 4, 1};
        System.out.println( 
            "Minimum number of multiplications required is "
            + matrixChainMultiplication(array)); 
    }
    
    static int matrixChainMultiplication(int[] array){
        int size = array.length;
        int dp[][] = new int[size][size];
        int cost;
        int j;
        
        // cost is zero when we multiply one matrix.
        for(int i = 1; i < size; i++){
            dp[i][i] = 0;
        }
        
        // l is chain of length 2
        for(int l = 2; l < size; l++){
            for(int i = 1; i < size - l + 1; i++){
                j = i + l - 1;
                if(j == size) continue;
                dp[i][j] = Integer.MAX_VALUE;
                // finding the split
                for(int k = i; k <= j - 1; k++){
                    cost = dp[i][k] + dp[k + 1][j] + array[i - 1] * array[k] * array[j];
                    if(cost < dp[i][j]){
                        dp[i][j] = cost;
                    }
                }
            }
        }
        return dp[1][size - 1];
    }
}

MatrixChainMultiplicationTd.java

public class Main {
    public static void main(String[] args) {
        int[] array = {1, 2, 1, 4, 1};
        System.out.println( 
            "Minimum number of multiplications required is "
            + memoizedMatrixChain(array)); 
    }
    
    static int memoizedMatrixChain(int[] array){
        int size = array.length;
        int dp[][] = new int[size][size];
        for(int i = 1; i < size; i++){
            for(int j = 1; j < size; j++){
                dp[i][j] = Integer.MAX_VALUE; 
            }
        }
        return lookUpChain(dp, array, 1, size - 1);
    }
    
    static int lookUpChain(int[][] dp, int[] array, int i, int j){
        if(dp[i][j] < Integer.MAX_VALUE){
            return dp[i][j];
        }
        else if(i == j){
            return 0;
        }
        else{
           for(int k = i; k < j; k++){
               int cost = lookUpChain(dp, array, i, k) +
                          lookUpChain(dp, array, k + 1, j) + 
                          array[i - 1] * array[k] * array[j];
               if(cost < dp[i][j]){
                   dp[i][j] = cost;
               }
           }
        }
        return dp[i][j];
    }
}

MergeSort.java

class Solution {
    public int[] sortArray(int[] nums) {
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }
    
       /**
       * [10, 20, 30, 40, 1, 5, 6, 9]
       * p = 0(index of first element of first sorted list)
       * q = 3(index of last element of first sorted list)
       * r = 7(index of last element of second sorted list)
       */
    
    // TC = O(n), SC = O(n) for merge process
    public void merge(int[] array, int p, int q, int r){
        
        // n1 and n2 are number of elements in first and second list
        int n1 = q - p + 1;
        int n2 = r - q;
        
        // for copying each sorted list into seperate list
        // later we'll use this for comparision
        int[] a1 = new int[n1 + 1];
        int[] a2 = new int[n2 + 1];
        
        for(int i = 0; i < n1; i++){
            a1[i] = array[p + i];
        }
        
        for(int j = 0; j < n2; j++){
            a2[j] = array[q + j + 1];
        }
        
        // last element of each lists
        a1[n1] = Integer.MAX_VALUE;
        a2[n2] = Integer.MAX_VALUE;
        
        // two pointers for two lists
        int i = 0;
        int j = 0;
        
        // comparing and merging two lists
        for(int k = p; k <= r; k++){
            if(a1[i] < a2[j]){
                array[k] = a1[i];
                i += 1;
            }
            else{
                array[k] = a2[j];
                j += 1;
            }
        }
    }
    
    // SC = (logn) for stack where n is number of funtion calls
    public void mergeSort(int[] array, int p, int r){
        if(p < r){
            // for dividing array into two sub-arrays
            int q = (p + r) / 2;
            //divide
            mergeSort(array, p, q);
            mergeSort(array, q + 1, r);
            // conquer
            merge(array, p, q, r);
        }
    }
}

MultistageGraph.java

public class Main {
    
    static final int INF = Integer.MAX_VALUE;
    static final int N = 8;
    
    public static void main(String[] args) {
        
        int[][] graph = {{INF, 1, 2, 5, INF, INF, INF, INF}, 
        {INF, INF, INF, INF, 4, 11, INF, INF}, 
        {INF, INF, INF, INF, 9, 5, 16, INF}, 
        {INF, INF, INF, INF, INF, INF, 2, INF}, 
        {INF, INF, INF, INF, INF, INF, INF, 18}, 
        {INF, INF, INF, INF, INF, INF, INF, 13}, 
        {INF, INF, INF, INF, INF, INF, INF, 2}}; 
  
        System.out.println(shortestDistance(graph));
    }
    
    static int shortestDistance(int[][] graph){
        int[] distance = new int[N];
        distance[N - 1] = 0;
        for(int i = N - 2; i >= 0; i--){
            distance[i] = INF;
            for(int j = i + 1; j < N; j++){
                // no edge condition
                if(graph[i][j] == INF){
                    continue;
                }
                // recursive equation
                distance[i] = Math.min(distance[i], graph[i][j] + distance[j]);
            }
        }
        return distance[0];
    }
}

PrimsMST.java

public class Main {
    
    static final int V = 5;
    
    public static void main(String[] args) {
        
        int graph[][] = {{ 0, 2, 0, 6, 0 }, 
                         { 2, 0, 3, 8, 5 },
                         { 0, 3, 0, 0, 7 }, 
                         { 6, 8, 0, 0, 9 }, 
                         { 0, 5, 7, 9, 0 }}; 
        primsMst(graph);
    }
    
    static int selectMinVertex(int[] value, boolean[] isIncluded){
        int vertex = -1;
        int minimum = Integer.MAX_VALUE;
        for(int i = 0; i < V; i++){
            if(isIncluded[i] == false && value[i] < minimum){
                vertex = i;
                minimum = value[i];
            }
        }
        return vertex;
    }
    
    static void printMST(int parent[], int graph[][]) 
    { 
        System.out.println("Edge \tWeight"); 
        for (int i = 1; i < V; i++) 
            System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]); 
    }
    
    static void primsMst(int[][] graph){
        
        // stores MST, (1->2) parent of 2 is 1 so we'll store 1 at index 2 in parent
        int[] parent = new int[V];
        // used for edge relaxation
        int[] value = new int[V];
        // fill the array with infinity
        Arrays.fill(value,Integer.MAX_VALUE);
        // true -> vertex is included in MST
        boolean[] isIncluded = new boolean[V];
        // initialise the array with false.
        Arrays.fill(isIncluded, Boolean.FALSE);
        // start node has no parent
        parent[0] = -1;
        // so that start node gets picked first
        value[0] = 0;
        
        for(int i = 0; i < V - 1; i++){
            // it selects best vertex by applying greedy method
            int u = selectMinVertex(value, isIncluded);
            isIncluded[u] = true;
            // relaxing adjacent vertices
            for(int j = 0; j < V; j++){
                /**
                * edge is present from u to j.
                * vertex j is not included in MST.
                * edge weight is smaller than current edge weight
                */
                if(graph[u][j] != 0 && isIncluded[j] == false && graph[u][j] < value[j]){
                    value[j] = graph[u][j];
                    parent[j] = u;
                }
            }
        }
        // print the constructed MST 
        printMST(parent, graph); 
    }
}

QuickSort.java

class Solution {
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }
    
       /**
       * [5, 7, 6, 1, 3, 2, 4]
       * p = 0(index of first element of first sorted list)
       * r = 7(index of last element of second sorted list) and it will be the initial pivot
       * after first pass the array will look something like this [1, 3, 2, 4, 7, 6, 5]
       */
    public int partition(int[] nums, int p, int r){
        // last element of the array
        int x = nums[r];
        // i will start at index -1
        int i = p - 1;
        /**
        * loop through the array and move all the smaller elements
        * to the left of the last element and larger elements to the
        * right of the last element.
        */
        for(int j = p; j < r; j++){
            if(nums[j] <= x){
                i++;
                // swap nums[i] with nums[j]
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
        // swap the last element with its correct position
        int temp = nums[i + 1];
        nums[i + 1] = nums[r];
        nums[r] = temp;
        // return the pivot index
        return i + 1;
    }
    
    public void quickSort(int[] nums, int p, int r){
        if(p < r){
            int q = partition(nums, p, r);
            quickSort(nums, p, q - 1);
            quickSort(nums, q + 1, r);
        }
    }
}

SubsetSum.java

public class Main {
    public static void main(String[] args) {
        int[] set = {6, 3, 2, 1};
        int sum = 5;
        int length = set.length;
        if(isSubsetSum(set, sum, length)) System.out.println("Found a subset with given sum");
        else System.out.println("No subset with given sum");
    }
    
    static boolean isSubsetSum(int[] set, int sum, int length){
        
        boolean[][] dp = new boolean[length + 1][sum + 1];
        // if sum == 0 then it is always true
        for(int i = 0; i <= length; i++) dp[i][0] = true;
        // if set is empty
        for(int j = 1; j <= sum; j++) dp[0][j] = false;
        for(int i = 1; i <= length; i++){
            for(int j = 1; j <= sum; j++){
                // if sum required is less than element
                if(j < set[i - 1]) dp[i][j] = dp[i - 1][j];
                else dp[i][j] = dp[i - 1][j - set[i - 1]] || dp[i - 1][j];
            }
        }
        return dp[length][sum];
    }
}