Sunday, 23 May 2021

Java Program To Search For A Range In Sorted Array

Problem:
We need to find first and last positions of an element in a sorted array.  In case element is not present, we need to return [-1, -1].

Input:
    A = [5, 7, 7, 8, 8, 10]
    B = 8
Output:
    [3, 4]
This is an interview question which is asked in companies like Google & Microsoft. You can find the question in popular sites like InterviewBit & LeetCode.

We can use modified version of binary search to find the range of the element. For leftmost element, we should move left side even when we find B & keep on updating the leftmost position. Same goes for rightmost element. In that case we need to keep on moving towards right side even when we encounter B. 

We are doing two binary searches, so overall time complexity would be O(log n).

Here is the fully working Java solution of the problem.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    // DO NOT MODIFY THE LIST. IT IS READ ONLY
    public ArrayList<Integer> searchRange(final List<Integer> A, int B) {
        int leftPos = findLeftMost(A, B);
        int rightPos = findRightMost(A, B);
        ArrayList<Integer> result = new ArrayList<Integer>();
        result.add(leftPos);
        result.add(rightPos);
        return result;
    }
    
    private int findLeftMost(final List<Integer> A, int B){
        int pos = -1;
        int lowerBound = 0;
        int upperBound = A.size() - 1;
        while(upperBound >= lowerBound){
            int mid = lowerBound + ((upperBound - lowerBound)/ 2);
            if(B <= A.get(mid)){
                if(A.get(mid) == B){
                    pos = mid;
                }
                upperBound = mid - 1;
            } else {
                lowerBound = mid + 1;
            }
        }
        return pos;
    }
    
    private int findRightMost(final List<Integer> A, int B){
        int pos = -1;
        int lowerBound = 0;
        int upperBound = A.size() - 1;
        while(upperBound >= lowerBound){
            int mid = lowerBound + ((upperBound - lowerBound) / 2);
            if(B >= A.get(mid)){
                if(A.get(mid) == B){
                    pos = mid;
                }
                lowerBound = mid + 1;
            } else {
                upperBound = mid - 1;
            }
        }
        return pos;
    }
}

Friday, 21 May 2021

Java Program to Invert the Binary Tree

Inverting a binary tree is common interview question.

Input:

     1
   /   \
  2     3
 / \   / \
4   5 6   7
Output:

    1
   /   \
  3     2
 / \   / \
7   6 5   4
We can use recursion to swap left & right sub-trees. Time complexity would be O(n) as we will be doing a full traversal of the binary tree. You can find the Java solution below:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.*;
import java.lang.*;
import java.io.*;

//Definition for binary tree
class TreeNode {
   int val;
   TreeNode left;
   TreeNode right;
   TreeNode(int x) {
      val = x;
      left=null;
      right=null;
   }
}

class Solution {
    public TreeNode invertTree(TreeNode A) {
        TreeNode curr = A;
        if(curr != null){
            TreeNode temp = curr.left;
            curr.left = curr.right;
            curr.right = temp;
            invertTree(curr.left);
            invertTree(curr.right);
        }
        return curr;
    }
}

Java Program to Solve Median of Two Sorted Array Problem

Median of two sorted arrays is a common problem which is asked in companies like Amazon, Google, Microsoft & Goldman Sachs. You can find the question in InterviewBit or LeetCode.

Problem: 
We have two sorted arrays A and B of size m and n respectively. We need to find the median of these two sorted arrays ( median of the array formed by merging both arrays ). The run time complexity should be O(log (m+n)).

Input:
A : [1 4 6]
B : [2 5]
Output: 4

Input:
A : [1 3 5]
B : [2 4 6]
Output: 3.5 ( (3 + 4) / 2.0 = 3.5 )

We can actually merge the two arrays & find out the median. But it will take O(m+n) time complexity.

We know the size of the median partition. In above cases it is 3. Median of 5 elements is 3 & median of 6 elements is avg of 3rd & 4th elements.
But left side elements in the partition can be part of both the arrays.
So we need to find indexes in both arrays where combined left side elements count is same as median partition. And elements in left hand side of each partition is less than the right side partitions of both arrays.

We can use binary search on the smaller size array to find the partition index. So time complexity will be O(log(min(m, n))).

You can find the working Java program for this problem below.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    // DO NOT MODIFY BOTH THE LISTS
    public double findMedianSortedArrays(final List<Integer> a, final List<Integer> b) {
        if(a.size() > b.size()){
            return findMedianSortedArrays(b, a);
        }
        int start = 0;
        int end = a.size() - 1;
        while(start <= end){
            int partition = (end + start) / 2 ;
            int bPartition = (a.size() + b.size() - 1) / 2 - partition - 1;
            int aRightValue = partition == a.size()-1 ? Integer.MAX_VALUE : a.get(partition + 1);
            int bRightValue = bPartition == b.size()-1 ? Integer.MAX_VALUE : b.get(bPartition + 1);
            int aLeftValue = partition < 0 ? Integer.MIN_VALUE : a.get(partition);
            int bLeftValue = bPartition < 0 ? Integer.MIN_VALUE : b.get(bPartition);
            if(aLeftValue <= bRightValue && bLeftValue <= aRightValue){
                if((a.size() + b.size()) % 2 == 1){
                    return Math.max(aLeftValue, bLeftValue);
                } else {
                    return (Math.max(aLeftValue, bLeftValue) + 
                           Math.min(aRightValue, bRightValue)) / 2.0;
                }
            } else if(aLeftValue > bRightValue){
                end = partition - 1;
            } else {
                start = partition + 1;
            }
        }
 
        int totalSize = a.size() +  b.size();
        // either A is empty or partition elements are less than starting element of A
        if(totalSize % 2 == 1) {
            return b.get(totalSize / 2);
        } else {
            int leftValue = b.get((totalSize - 1)/ 2);
            int rightValue = b.get(totalSize / 2);
            if(!a.isEmpty() && a.get(0) < rightValue) {
                rightValue = a.get(0);
            }
            return (leftValue +  rightValue) / 2.0;
        }
    }
}

Saturday, 15 May 2021

Java Program For Shortest Unique Prefix Problem

Shortest Unique Prefix is an interview question which you can find in websites like GeeksForGeeks & InterviewBit. It is asked in Google interviews. Basically we need to find shortest unique prefix to represent each word in the list.

Input: [zebra, dog, duck, dove]
Unique Prefix of each word is as below:
zebra = z
dog = dog
duck = du
dove = dov
Output: {z, dog, du, dov}

To solve it, we will use a Trie implementation. For our example, Trie tree will look like below:

                root
                / \
               /   \
              /     \
            (d, 3)   (z, 1)
           / \          \
          /   \          \
         /     \          \
        (o, 2)  (u, 1)     (e, 1)
      /  \         \            \
(g,1)/    \         \            \
    /      \         \            \ 
   Leaf     (v, 1)       (c, 1)       (b, 1)
   (dog)     \          \               \
              \          \               \
               \(e, 1)    \(k, 1)         \   
                 Leaf      Leaf             (r, 1)
                 (dove)    (duck)              \
                                                \
                                                 \(a, 1)
                                                 Leaf
                                                 (zebra)

Then for each word, we will do a depth first traversal & find the first node where letter count is 1. Then the path from root to that node is the unique prefix for that word. Below you can find the working solution of the problem written in Java. Time complexity of this solution in (n * m) where n is word count & m is max letter count in a word.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    public ArrayList<String> prefix(ArrayList<String> A) {
        TrieNode root = new TrieNode();
        for(String s : A){
            root.insert(s, root);
        }
        ArrayList<String> results = new ArrayList<String>();
        for(String s : A){
            List<Character> path = new ArrayList<Character>();
            getPrefixes(root, results, path, s, 0);
        }
        return results;
    }
    
    private void getPrefixes(TrieNode node, List<String> results, List<Character> path,
    String word, int index){
        TrieNode curr = node.children.get(word.charAt(index));
        path.add(curr.value);
        if(curr.count == 1){
            StringBuilder sb = new StringBuilder();
            for (Character c: path) {
                sb.append(c);
            }
            results.add(sb.toString());
        } else {
            getPrefixes(curr, results, path, word, index + 1);
        }
        path.remove(path.size() - 1);
    }
    
    static class TrieNode {
        Map<Character, TrieNode> children = new HashMap<Character, TrieNode>();
        int count = 0;
        char value;
        
        public void insert(String word, TrieNode root){
            TrieNode curr = root;
            for(char c : word.toCharArray()){
                TrieNode child = null;
                if(curr.children.containsKey(c)){
                    child = curr.children.get(c);
                    child.count = child.count + 1;
                } else {
                    child = new TrieNode();
                    child.count = child.count + 1;
                    child.value = c;
                    curr.children.put(c, child);
                }
                curr = child;
            }
        }
    }
}

Friday, 14 May 2021

Better Explanation Of Order of People Heights Problem And Java Program To Solve It

Order of People Heights is an interview question that is asked in Google. You can find the question in websites like InterviewBit & CareerCup. But the problem is that you won't find a good explanation of the problem anywhere. Let me try to describe the problem statement clearly.

Input : 
Heights: 5 3 2 6 1 4
InFronts: 0 1 2 0 3 2

We have two input arrays of same size n. n is the number of people that we have. Now first array gives us the actual height of the person at index i. Second array gives us the number of taller persons who should be in front of i th person(left hand side of the index). There are no duplicates in the Heights array.

Index 0 :  value (5, 0) is correct as no taller person is on left hand side
Index 1 :  value (3, 1) is correct as only 5 is taller than 3
Index 2 :  value (2, 2) is correct as 5 & 3 are on the left side of 2
Index 3 :  value (6, 0) is correct as all left hand heights are less than 6
Index 4 :  value (1, 3) is wrong as we have total 4 taller (5, 3, 2 & 6) heights instead of 3
Index 5 :  value (4, 2) is correct as 5 & 6 are the two taller heights on the left hand side

We need to rearrange the heights so that it maintains the order correctly as per InFronts array. In the above example (1, 3) is not having the correct order.

Hope you have a better understanding of the problem now.

To solve this, first we will sort the heights from shortest to tallest.

Input : 
Heights: 1 2 3 4 5 6
InFronts: 3 2 1 2 0 0

From above,  you can see 1 is the shortest height & it has been moved to index 0. Now we can take a empty array of size n & put 1 at (3+1) = 4 th position or 3rd index. Why? Because we need at least three empty positions before 1 to insert three taller elements. And we can't move 1 on the right hand side after 3rd index. Then we would have to fill that with a shorter element than 1 to maintain InFronts value of 3. But 1 is the shortest height & there is no other element which is shorter than that. That way, we can finalize the shortest height position. And then we can take the next shortest height & follow the same steps.

The final order would be

Heights : 5 3 2 1 6 4
Infronts: 0 1 2 3 0 2

We need to return only the Heights array.

Below you can find a Java implementation of the solution with above approach. Its time complexity is O(n^2 + n log n) & space complexity is O(n). Regarding time complexity, O(n log n) is the time taken to sort the elements using TreeMap . We have one inner loop used to populate results array which will take O(n^2) time complexity. In a future post, I will try to give a more optimized solution using tree data structure. But this solution works well & easy to understand.

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    public ArrayList<Integer> order(ArrayList<Integer> A, ArrayList<Integer> B) {
        
        ArrayList<Integer> results = new ArrayList<Integer>();
        for(int i=0; i<A.size(); i++){
            results.add(-1);
        }
        
        //using TreeMap to sort the key by ascending order
        TreeMap<Integer, Integer> sortedHeights = new TreeMap<Integer, Integer>();
        for(int i=0; i<A.size(); i++){
            sortedHeights.put(A.get(i), B.get(i));
        }
        
        for(int height : sortedHeights.keySet()){
            int inFront = sortedHeights.get(height);
            int pos = 0;
            int i = 0;
            while(inFront > pos || results.get(i) != -1){
                if(results.get(i) == -1 || results.get(i) > height){
                    pos++;
                }
                i++;
            }
            results.set(i, height);
        }
        
        return results;
    }
}

Sunday, 9 May 2021

How To Use Flash Drive In Both macOS And Windows Laptop

I have Mac OS & Windows laptops. I use both of them quite frequently. Now I have an external hard drive that I want to use for both Mac & Windows laptops. Basically the flash drive should be able to transfer or copy/paste files from Windows laptop to MacOS. Or I should be able to do vice versa & transfer files from Mac OS to Windows laptop.

So I needed a file format that is supported by latest versions of Windows & macOS. That way I don't need to install any third party software to support the flash drive file system. exFAT file system came to the rescue. It is supported by both Windows & mac OS. So you don't need to reformat or use a third party software when you are switching between the two operating systems.

By the way, it doesn't work seamlessly with Linux distributions. You might need to see if you can use some third party software to make it work in machines using Ubuntu or other Linux distributions.

Saturday, 8 May 2021

Java Program For Sum Root to Leaf Numbers

Sum Root to Leaf Numbers is a popular interview problem which is asked in companies like Google & Microsoft. You can find this question in LeetCode & InterviewBit.

We have been given a binary tree where each node can contain any number between 0-9.

    2
   / \
  4   8

For the above tree, there are two root to leaf paths, 2->4 = 24 & 2->8 = 28. So result should be 24 + 28 =  52. In InterviewBit problem, we need to get the remainder after dividing the result by 1003 (result % 1003) to restrict number overflow. Number overflow can happen if tree has a lot of depth.

Below you can find the working Java solution for this problem. It will do a pre-order traversal & do a backtracking to find all possible solutions & add them to result. Time complexity is O(n) as we need to traverse the full tree once. Space complexity is constant O(1) if we don't consider recursion stack.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;

//Definition for binary tree
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
        left=null;
        right=null;
    }
}

class Solution {
    public int sumNumbers(TreeNode A) {
        String currentSum = "";
        //Like Integer, BigInteger object is also immutable. Assigning new object refrence
        //inside method won't change method argument. So using an array of BigInteger.
        BigInteger[] result = new BigInteger[]{BigInteger.valueOf(0)};
        calculateSumRootToLeaf(A, currentSum, result);
        result[0] = result[0].remainder(BigInteger.valueOf(1003));
        return result[0].intValue();
    }
    private void calculateSumRootToLeaf(TreeNode node, String currentSum, BigInteger[] result){
        currentSum = currentSum + "" + node.val;
        if(node.left == null && node.right == null){
            result[0] = result[0].add(new BigInteger(currentSum));
        } else {
            if(node.left != null){
                calculateSumRootToLeaf(node.left, currentSum, result);
            }
            if(node.right != null){
                calculateSumRootToLeaf(node.right, currentSum, result);
            }
        }
        currentSum = currentSum.substring(0, currentSum.length() - 1);
    }
}

Saturday, 1 May 2021

Java Program for Least Common Ancestor Of A Binary Tree

This is common interview question. There can be a variant where we would have to find Least Common Ancestor (LCA) of a Binary Search Tree (BST). But here we will concentrate our solution for a normal unordered Binary Tree. This question is asked in companies like FaceBook, Google, Adobe, Microsoft & Amazon. You can find the problem in LeetCode or InterviewBit.
So basically we have two values B & C. And we need to find the LCA of the nodes represented by these two values. There is no guarantee that B & C exist in the tree. In case any value is missing, we should return -1 from the method.

       _______10______
       /              \
    ___6__          ___11__
   /      \        /      \
   17      _2_     7        8
         /   \
         12    4
In the tree above, 6 is the lowest common ancestor of 17 and 4.
For the solution, we will be traversing the tree twice, one for B & one for C. We will store paths to B & C separately in ArrayList variables. In case B or C is missing, that path will be empty. Once we have calculated the path, we will compare the paths & find the first element where there is a diversion or the value is equal to B or C. That will give us the LCA of the binary tree for these two values. Time complexity of this solution is O(n).

Here is a working Java code implementation of this problem.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
import java.util.*;
import java.lang.*;
import java.io.*;


//Definition for binary tree
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
       val = x;
       left=null;
       right=null;
    }
}

class Solution {
    public int lca(TreeNode A, int B, int C) {
        List<Integer> path1 = new ArrayList<Integer>();
        List<Integer> path2 = new ArrayList<Integer>();
        TreeNode temp = A;
        findPathToValue(temp, path1, B);
        //resetting starting index
        temp = A;
        findPathToValue(temp, path2, C);
        if(path1.size() == 0 || path2.size() == 0){
            return -1;
        }
        int smallerSize = Math.min(path1.size(), path2.size());
        int i=0;
        for(;i<smallerSize; i++){
            if(!path1.get(i).equals(path2.get(i))){
                break;
            }
        }
        return path1.get(i - 1);
    }
    
    private boolean findPathToValue(TreeNode temp, List<Integer> path, int value){
        path.add(temp.val);
        if(temp.val == value){
            return true;
        }
        if(temp.left != null && findPathToValue(temp.left, path, value)){
            return true;
        }
        if(temp.right != null && findPathToValue(temp.right, path, value)){
            return true;
        }
        path.remove(path.size() - 1);
        return false;
    }
}

Java Program To Solve Maximum Size Rectangle In Binary Matrix

Given a binary matrix, find max rectangle with all 1's. A : [ 1 1 1 0 0 1 1 0 1 1 1 0 ] Output : 6 Dynamic programmi...