How to merge two sorted arrays into a sorted array.

Problem:

You are given 2 sorted integer arrays, you need to merge these 2 arrays and result should also be sorted array. Example is below.

      static Integer[] firstList = {1,2,2,4,5,12,12,23,63,65,235,624};  
      static Integer[] secondList = {2,3,5,6,7,22,23,24,52,66,67,68,77,78,89,98};  

If above are the 2 integer lists, output would be:

Output: 1 2 2 2 3 4 5 5 6 7 12 12 22 23 23 24 52 63 65 66 67 68 77 78 89 98 235 624

This is also very good interview coding question because interviewer can access how efficiently you can merge and sort the arrays at the same time. As always there could be many solutions of this problem. This time instead of listing all not so good solutions first, I am giving only best solution.

Here it is:

1. Iterate through both the arrays until anyone reached it's full length.
2. Compare indexed elements from each array and add them to result array accordingly.
3. Iterate both the arrays for remaining elements after first iteration.
4. Add the elements from the array to result array accordingly.

1:       public static void merge2ArraysAsSortedArray() {  
2:            Integer[] resultList = new Integer[firstList.length+secondList.length];  
3:            int i=0, j=0, k=0;  
4:            while (i<firstList.length && j < secondList.length) {  
5:                 if(firstList[i] <= secondList[j]){  
6:                      resultList[k++] = firstList[i++];  
7:                 } else {  
8:                      resultList[k++] = secondList[j++];  
9:                 }  
10:            }  
11:            while (i<firstList.length) {  
12:                 resultList[k++] = firstList[i++];  
13:            }  
14:            while (j<secondList.length) {  
15:                 resultList[k++] = secondList[j++];  
16:            }  
17:            printList(resultList);  
18:       }  
19:       public static void printList(Integer[] list){  
20:            for (Integer integer : list) {  
21:                 System.out.printf("%d ",integer);  
22:            }  
23:            System.out.printf("%n");  
24:       }  

This is a good solution because time complexity of this solution is O(N) where N is the sum of lengths of both the given arrays. There is one more solution I found on internet, which is not more efficient then the first one but it's more neat and short.

Here take a look.

1:  public static void mergeArraysAsSortedArray() {  
2:            Integer[] resultList = new Integer[firstList.length+secondList.length];  
3:            int i=firstList.length-1, j=secondList.length-1, k=resultList.length;  
4:            while(k > 0){  
5:                 resultList[--k] = (j<0 || (i>=0 && firstList[i] >= secondList[j])) ? firstList[i--]: secondList[j--];  
6:            }  
7:            printList(resultList);  
8:       }  

So here they were, Let me know if anyone of you have any better solution.

Find all the Pairs in Integer Array whose sum is equal to a given number.

Problem:

As heading says, The problem is to find all the Pairs in Integer Array whose sum is equal to a given number. for example if integer arrays is {4,5,6,2,1} and given number is 9 then answer should be (4,5).

This is again an interesting problem to solve and have many correct solutions but interview would look for the most efficient one and thought process behind it.

Brute Method:

1. Loop through the list twice; second loop will start from first loop index +1.
2. Compare the sum of inner index element and outer index element with given sum value.
3. And print the pair if match is found.

1:  public static void findPairs(){  
2:            for (int i=0;i<intList.length;i++) {  
3:                 for (int j=i+1;j<intList.length;j++) {  
4:                      if(sum.equals(intList[i]+intList[j])){  
5:                           System.out.printf("(%d, %d) %n",intList[j],intList[i]);  
6:                      }  
7:                 }  
8:            }  
9:            System.out.println("");  
10:       }  

Now this solution will give you exact result but time complexity of this method is O(N²).

To reduce the time complexity, we can add up some space complexity and reach to the solution.
One way of doing this would be to use HashSet.

1. Loop through the list.
2. Search the target value (given number - element from the list) in a given Set.
3. If set contains the target value; print it pair (element from the list and target) otherwise add the target to the set.

1:       public static void findPairsWithSet(){  
2:            Set<Integer> set = new HashSet<Integer>(intList.length);  
3:            for (int i=0;i<intList.length;i++) {  
4:                 Integer target = sum - intList[i];  
5:                 if(set.contains(target)){  
6:                      System.out.printf("(%d, %d) %n",intList[i],target);  
7:                 } else{  
8:                      set.add(intList[i]);  
9:                 }  
10:            }  
11:            System.out.println("");  
12:       }  

This reduces the time complexity to O(N) because contains method's complexity for a Set is O(1). But you will need extra space to save the Set so it will increase the space complexity of this method to O(N) which is bad in case of very large integer array.

Best solution would be to Sort the array and maintain the 2 pointers in the array.

1. Sort the array in ascending order.
2. Maintain 2 pointers, one at beginning and second one at the tail.
3. Keep increasing the first pointer and decreasing the tail pointer if a match is found.
4. If addition of first index element and second index element is less than given number; increase the first pointer.
5. Similarly if addition of  first index element and second index element is greater than given number; decrease the second pointer
6. Keep doing Step 3,4,5 until both pointer cross each other.

1:       public static void findPairsWithSorting(){  
2:            Arrays.sort(intList);  
3:            int left=0;  
4:            int right = intList.length -1;  
5:            while(left < right){  
6:                 Integer addition = intList[left] + intList[right];  
7:                 if(addition.equals(sum)){  
8:                      System.out.printf("(%d, %d) %n",intList[left],intList[right]);  
9:                      left++;  
10:                      right--;  
11:                 } else if(addition.compareTo(sum) <0){  
12:                      left++;  
13:                 } else {  
14:                      right-- ;  
15:                 }  
16:            }  
17:       }  

This is the best solution in my opinion because first of Arrays.sort uses two pivot quick sort algorithm, so complexity of this method would be ~O(N).

Try out this methods with your examples and please do let me know in comments below if there is an even better solution to this problem.

Most Occurred Integer in the List

Problem:

You are given a list of integers and you need to find the most occurred integer or sometime it is called most popular element in the list.

 static Integer[] intList = {5,21,21,3,4,5,5,3,6,7,65,5,21,21,21,4,4,4,4,4,4,4,4,4,4};  

This is very common interview question and can have multiple correct solution, but interviewer expect you to give the most efficient solution.

One solution would be to

1. Iterate through the list twice 
2. Compare the elements inside the second iteration
3. Increment the counter.
4. Compare the counter with previously saved maxOccurred variable.
5. And if counter is greater than previous value, save the counter value to maxOccurred variable.

1:       public static void mostOccurentElement(){  
2:            Integer mostOccurentElement=0;  
3:            Integer mostOccurences = 0;  
4:            for (Integer number : intList) {  
5:                 int count = 0;  
6:                 for (Integer number2 : intList) {  
7:                      if(number.equals(number2)){  
8:                           count++;  
9:                      }   
10:                 }  
11:                 if(count > mostOccurences){  
12:                      mostOccurences = count;  
13:                      mostOccurentElement = number;  
14:                 }  
15:            }  
16:            System.out.println("Most Occured element = "+mostOccurentElement+" Most occurnces are : "+mostOccurences);  
17:       }  

Output of above solution:
Most Occurred element = 4 Most occurrences are : 11

Complexity of this method is O(N²) where N is length of this list. Better solution would be to avoid the second for loop. Second solution would be:

1. Iterate through the list once.
2. Get and populate the value as number of occurrences of each element into the map.
3. Iterate through the map 
4. Compare each value with previously saved maxOccurred variable.
5. And if value is greater than previous value, save the counter value to maxOccurred variable.

1:       public static void mostOccurentElementByMap(){  
2:            Map<Integer, Integer> map = new HashMap<Integer, Integer>();  
3:            Integer mostOccurentElement=0;  
4:            Integer mostOccurences = 0;  
5:            for (Integer number : intList) {  
6:                 if(map.containsKey(number)){  
7:                      Integer integer = map.get(number);  
8:                      map.put(number, integer+1);  
9:                 } else {  
10:                      map.put(number, 1);  
11:                 }  
12:            }  
13:            Set<Entry<Integer, Integer>> entrySet = map.entrySet();  
14:            for (Entry<Integer, Integer> entry : entrySet) {  
15:                 if(mostOccurences < entry.getValue()){  
16:                      mostOccurences = entry.getValue();  
17:                      mostOccurentElement = entry.getKey();  
18:                 }  
19:            }  
20:            System.out.println("Most Occured element = "+mostOccurentElement+" Most occurnces are : "+mostOccurences);  
21:       }  

Output of above solution:
Most Occurred element = 4 Most occurrences are : 11

Complexity of this method is O(N) where N is length of this list. The space complexity is also N. I will add new better solution if I could also reduce the space complexity. If anyone of you have better solution, please do suggest in comment section.

Tree Traversal

Here is the tree which we are going to traverse in many ways.  Here is the very broad definition of what tree represents in data structure.
In java it is represented as TreeNode which consists of data (40 for root node) and left and right node.

1:  package com.research.tree;  
2:  public class TreeNode   
3:  {   
4:       int data;   
5:       TreeNode left;   
6:       TreeNode right;   
7:       TreeNode(int data)   
8:       {   
9:            this.data=data;   
10:       }   
11:  }   

There are many traversal techniques to traverse a tree but in most of the interviews these 6 traversals are asked to perform. Here is each one in detail. First three traversals (pre-order, post-order, and in-order) are also called Depth-First search because the search tree is deepened as much as possible on each child before going to the next sibling.

• Pre-Order:
  1. Display the data part of the root (or current node).
  2. Traverse the left subtree by recursively calling the pre-order function.
  3. Traverse the right subtree by recursively calling the pre-order function.
  4. Here is the result of pre-order traversal of above tree

                     40, 20, 10, 84, 30, 60, 50, 70
                5. Pictorial representation:

       6. Program: We are using recursion as described above to programmatically traverse the tree.

1:       public void preOrder(TreeNode node){  
2:            if(node != null){  
3:                 System.out.print(node.data+", ");  
4:                 preOrder(node.left);   
5:                 preOrder(node.right);  
6:            }  
7:       }  

• Post-Order:
  1. Traverse the left subtree by recursively calling the post-order function.
  2. Traverse the right subtree by recursively calling the post-order function.
  3. Display the data part of the root (or current node).
  4. Here is the result of pre-order traversal of above tree

                     84, 10, 30, 20, 50, 70, 60, 40
                5. Pictorial representation:

6. Program: We are using recursion as described above to programmatically traverse the tree.

1:       public void postOrder(TreeNode node){  
2:            if(node != null){  
3:                 postOrder(node.left);  
4:                 postOrder(node.right);  
5:                 System.out.print(node.data+", ");  
6:            }  
7:       }  

• In-Order:
  1. Traverse the left subtree by recursively calling the in-order function.
  2. Display the data part of the root (or current node).
  3. Traverse the right subtree by recursively calling the in-order function.
  4. Here is the result of pre-order traversal of above tree

                    10, 84, 20, 30, 40, 50, 60, 70
                5.Pictorial representation:

6. Program: We are using recursion as described above to programmatically traverse the tree.

1:       public void inOrder(TreeNode node){  
2:            if(node != null){  
3:                 inOrder(node.left);  
4:                 System.out.print(node.data+", ");  
5:                 inOrder(node.right);  
6:            }  
7:       }  

• Level Order:
• Display the data part of the root.
• Traverse the tree top to bottom and left to right
• Displaying each node, left node first.
• Here is the result of level order traversal of above tree

40,20,60,10,30,50,70,84

• Pictorial Representation:

• Program:
• Create a queue (linked list)
• Add root node to the queue.
• Loop the queue while it is not empty.
• Poll the first node from the queue.
• Print the data of extracted node.
• Add the left node to queue if it’s not empty
• Add the right node to queue if it’s not empty

1:       public void levelOrder(TreeNode node){  
2:            Queue<TreeNode> queue = new LinkedList<TreeNode>();  
3:            queue.add(node);  
4:            while(!queue.isEmpty()){  
5:                 TreeNode tempNode = queue.poll();  
6:                 System.out.print(tempNode.data+",");  
7:                 if(tempNode.left != null)  
8:                      queue.add(tempNode.left);  
9:                 if(tempNode.right != null)  
10:                      queue.add(tempNode.right);  
11:            }  
12:       }  

• Reverse Level Order:
• Display the data part of the bottom first node.
• Traverse the tree bottom to top and left to right
• Displaying each node, left node first.
• Here is the result of reverse level order traversal of above tree

84, 10, 30, 50, 70, 20, 60, 40

• Pictorial Representation:

• Program:
• Create a queue (linked list)
• Create a Stack.
• Add root node to the queue.
• Loop the queue while it is not empty.
• Poll the first node from the queue.
• Add the extracted node to stack.
• Add the right node to queue if it’s not empty
• Add the left node to queue if it’s not empty
• Now stack is full with node in level order (to-bottom, right-left). But stack performs First-In-Last-Out (FILO).
• Loop the stack while it is not empty
• Pop the first node out of stack and print its data element.

1:       public void reverseLevelOrder(TreeNode node){  
2:            Queue<TreeNode> queue = new LinkedList<TreeNode>();  
3:            Stack<TreeNode> stack = new Stack<TreeNode>();  
4:            queue.add(node);  
5:            while(!queue.isEmpty()){  
6:                 TreeNode tempNode = queue.poll();  
7:                 if(tempNode.right != null)  
8:                      queue.add(tempNode.right);  
9:                 if(tempNode.left != null)  
10:                      queue.add(tempNode.left);  
11:                 stack.add(tempNode);  
12:            }  
13:            while(!stack.isEmpty()){  
14:                 System.out.print(stack.pop().data+",");  
15:            }  
16:       }  

Junit Test Class to test all traversal techniques: 

1:  package com.research.tree;  
2:  import org.junit.Before;  
3:  import org.junit.Test;  
4:  public class BinaryTest {  
5:       TreeNode rootNode;  
6:       @Before  
7:       public void setUp(){  
8:            rootNode=new TreeNode(40);   
9:            TreeNode node20=new TreeNode(20);   
10:            TreeNode node10=new TreeNode(10);   
11:            TreeNode node30=new TreeNode(30);   
12:            TreeNode node60=new TreeNode(60);   
13:            TreeNode node50=new TreeNode(50);   
14:            TreeNode node70=new TreeNode(70);  
15:            TreeNode node84=new TreeNode(84);   
16:            rootNode.left=node20;   
17:            rootNode.right=node60;   
18:            node20.left=node10;   
19:            node20.right=node30;   
20:            node60.left=node50;   
21:            node60.right=node70;   
22:            node10.right = node84;  
23:       }  
24:       @Test  
25:       public void testPreOrder(){  
26:            BinaryTree bTree = new BinaryTree();  
27:            bTree.preOrder(rootNode);  
28:       }  
29:       @Test  
30:       public void testPostOrder(){  
31:            BinaryTree bTree = new BinaryTree();  
32:            bTree.postOrder(rootNode);  
33:       }  
34:       @Test  
35:       public void testInOrder(){  
36:            BinaryTree bTree = new BinaryTree();  
37:            bTree.inOrder(rootNode);  
38:       }  
39:       @Test  
40:       public void testLevelOrder(){  
41:            BinaryTree bTree = new BinaryTree();  
42:            bTree.levelOrder(rootNode);  
43:       }  
44:       @Test  
45:       public void testReverseLevelOrder(){  
46:            BinaryTree bTree = new BinaryTree();  
47:            bTree.reverseLevelOrder(rootNode);  
48:       }  
49:       @Test  
50:       public void testSpiralOrZigzagLevelOrder(){  
51:            BinaryTree bTree = new BinaryTree();  
52:            bTree.spiralOrZigzagLevelOrder(rootNode);  
53:       }  
54:  }  

How to create a LinkedList in Java.

How to create a LinkedList in Java.

I am assuming that everyone knows what is linked list? Click here to know more about linked list. 

Functionality of this program:

1. Create a Node class which will represent the Singly Linked List.
   • Value at linked list node
   • Next Node
2. Singly Linked List Implementation Class
   • Head: First node of the linked list. Initial value is null.
   • Tail: Last node of the linked list. Initial value is null.
   • add Method: This method adds a node at the end of the linked list.
   • addAfter Method: adds a node after a given node.
   • deleteAfter Method: deletes a node after a given node.
   • deleteFront Method: deletes the head node which is also is the starting point of the linked list. After this method second node of the linked list becomes the head node.
   • reverse Method: revers the given linked list.
   • traverse Method: prints the full linked list.
3. Result of this program:

1:  package com.research.list.linkedlist;  
2:  public class Node<T> implements Comparable<T> {  
3:       private T value;  
4:       private Node<T> nextRef;  
5:       public T getValue() {  
6:            return value;  
7:       }  
8:       public void setValue(T value) {  
9:            this.value = value;  
10:       }  
11:       public Node<T> getNextRef() {  
12:            return nextRef;  
13:       }  
14:       public void setNextRef(Node<T> nextRef) {  
15:            this.nextRef = nextRef;  
16:       }  
17:       public int compareTo(T arg) {  
18:            if(arg == this.value){  
19:             return 0;  
20:           } else {  
21:             return 1;  
22:           }  
23:       }  
24:  }  

1:  package com.research.list.linkedlist.singly;  
2:  import org.springframework.stereotype.Component;  
3:  import com.research.list.linkedlist.Node;  
4:  public class SinglyLinkedListImpl<T> {  
5:       Node<T> head;  
6:       Node<T> tail;  
7:       public void add(T element){  
8:            Node<T> node = new Node<T>();  
9:            node.setValue(element);  
10:            if(head == null){  
11:                 head = node;  
12:                 tail = node;  
13:            } else {  
14:                 tail.setNextRef(node);  
15:                 tail = node;  
16:            }  
17:       }  
18:       public void addAfter(T element, T after){  
19:            Node<T> node = new Node<T>();  
20:            node.setValue(element);  
21:            Node<T> tmp = head;  
22:            Node<T> refNode = null;  
23:            while(true){  
24:                 if(tmp == null)  
25:                      break;  
26:                 if(tmp.compareTo(after) == 0){  
27:                      refNode=tmp;  
28:                      break;  
29:                 }  
30:                 tmp = tmp.getNextRef();  
31:            }  
32:            if(refNode != null){  
33:                 node.setNextRef(tmp.getNextRef());  
34:                 if(tmp.compareTo(tail.getValue()) == 0)  
35:                      tail=node;  
36:                 tmp.setNextRef(node);  
37:            }  
38:       }  
39:       public void deleteFront(){  
40:            if(head == null){  
41:                 System.out.println("UnderFlow");  
42:            } else{  
43:                 Node<T> tmp = head;  
44:                 head = tmp.getNextRef();  
45:                 if(head == null){  
46:                      tail = null;  
47:                 }  
48:            }  
49:       }  
50:       public void deleteAfter(T after){  
51:            Node<T> tmp = head;  
52:            Node<T> refNode = null;  
53:            while(true){  
54:                 if(tmp == null)  
55:                      break;  
56:                 if(tmp.compareTo(after) == 0){  
57:                      refNode=tmp;  
58:                      break;  
59:                 }  
60:                 tmp=tmp.getNextRef();  
61:            }  
62:            if(refNode != null){  
63:                 tmp = refNode.getNextRef();  
64:                 refNode.setNextRef(tmp.getNextRef());  
65:                 if(refNode.getNextRef() == null){  
66:                      tail = refNode;  
67:                 }  
68:            }  
69:       }  
70:       public void reverse(){  
71:            Node<T> currentNode = head;  
72:            Node<T> nextNode = null;  
73:            Node<T> previousNode = null;  
74:            while(currentNode != null){  
75:                 nextNode = currentNode.getNextRef();  
76:                 currentNode.setNextRef(previousNode);  
77:                 previousNode = currentNode;  
78:                 currentNode = nextNode;  
79:            }  
80:            head = previousNode;  
81:       }  
82:       public void traverse(){  
83:            Node<T> tmp = head;  
84:            while(true){  
85:                 if(tmp == null)  
86:                      break;  
87:                 System.out.print(tmp.getValue()+",");  
88:                 tmp=tmp.getNextRef();  
89:            }  
90:            System.out.println("");  
91:       }  
92:       public static void main(String[] args) {  
93:            SinglyLinkedListImpl<Integer> linkedList = new SinglyLinkedListImpl<Integer>();  
94:            linkedList.add(3);  
95:            linkedList.add(45);  
96:            linkedList.add(12);  
97:            linkedList.add(32);  
98:            linkedList.add(49);  
99:            linkedList.add(98);  
100:            linkedList.add(90);  
101:            linkedList.add(42);  
102:            linkedList.traverse(); // 1: Traverse - initial Linked List  
103:            linkedList.addAfter(21, 90);  
104:            linkedList.traverse(); // 2: Traverse - after adding 21 after 90  
105:            linkedList.addAfter(67, 42);  
106:            linkedList.traverse(); // 3: Traverse - after adding 67 after 42  
107:            linkedList.deleteAfter(49);  
108:            linkedList.traverse(); // 4: Traverse - after deleting number after 49  
109:            linkedList.deleteFront();  
110:            linkedList.traverse(); // 5: Traverse - after deleting front number from linked list  
111:            linkedList.reverse();  
112:            linkedList.traverse(); // 6: Traverse - after reversing the linked list  
113:       }  
114:  }