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.