Find a number which equals to the index

Given an array of positive and negative numbers sorted in ascending order.Find a number which is equal to the index of that number in array.
ex: Array = {-3,-1,0,1,4}
ans: a[4]=4
We can do it by linear search in O(n) time or by doing binary search in O(logN) time.

public class FixedPoint {
 public static void main(String[] args) {
  int[] a = { -10, -5, 0, 3, 7 };
  int fixedPoint = getFixedPointNumber(a, 0, a.length - 1);

  if (fixedPoint != -1) {
   System.out.println("Number is : " + fixedPoint);
  } else {
   System.out.println("There is Number satisying the condition.");
  }
 }

 /**
  * Returns a number a[i] which satisfies the condition a[i]=i
  * 
  * @param a
  * @param low
  * @param high
  * @return
  */
 private static int getFixedPointNumber(int[] a, int low, int high) {

  if (a == null || a.length == 0 || low < 0 || high >= a.length
    || low > high)
   return -1;

  int mid = (low + high) / 2;

  if (a[mid] == mid) {
   return mid;
  } else if (a[mid] < mid) {
   return getFixedPointNumber(a, mid + 1, high);
  } else {
   return getFixedPointNumber(a, low, mid - 1);
  }
 }

}

Array inplace shuffle

Given an array:

[a_1, a_2, ..., a_N, b_1, b_2, ..., b_N, c_1, c_2, ..., c_N ]

convert it to:

[a_1, b_1, c_1, a_2, b_2, c_2, ..., a_N, b_N, c_N]

in-place using constant extra space.

Refer : http://www.ardendertat.com/2011/10/18/programming-interview-questions-9-convert-array/

http://arxiv.org/PS_cache/arxiv/pdf/0805/0805.1598v1.pdf

Find the Minimum length Unsorted Subarray, sorting which makes the complete array sorted

Given an unsorted array arr[0..n-1] of size n, find the minimum length subarray arr[s..e] such that sorting this subarray makes the whole array sorted.

Examples:
1) If the input array is [10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60], your program should be able to find that the subarray lies between the indexes 3 and 8.

2) If the input array is [0, 1, 15, 25, 6, 7, 30, 40, 50], your program should be able to find that the subarray lies between the indexes 2 and 5.

Solution:
1) Find the candidate unsorted subarray
a) Scan from left to right and find the first element which is greater than the next element. Let s be the index of such an element. In the above example 1, s is 3 (index of 30).
b) Scan from right to left and find the first element (first in right to left order) which is smaller than the next element (next in right to left order). Let e be the index of such an element. In the above example 1, e is 7 (index of 31).

2) Check whether sorting the candidate unsorted subarray makes the complete array sorted or not. If not, then include more elements in the subarray.
a) Find the minimum and maximum values in arr[s..e]. Let minimum and maximum values be min and max. min and max for [30, 25, 40, 32, 31] are 25 and 40 respectively.
b) Find the first element (if there is any) in arr[0..s-1] which is greater than min, change s to index of this element. There is no such element in above example 1.
c) Find the last element (if there is any) in arr[e+1..n-1] which is smaller than max, change e to index of this element. In the above example 1, e is changed to 8 (index of 35)

3) Print s and e.

Refer : http://www.geeksforgeeks.org/archives/8858

Average of a stream of numbers

Given a stream of numbers, print average (or mean) of the stream at every point. For example, let us consider the stream as 10, 20, 30, 40, 50, 60, …

  Average of 1 numbers is 10.00
  Average of 2 numbers is 15.00
  Average of 3 numbers is 20.00
  Average of 4 numbers is 25.00
  Average of 5 numbers is 30.00
  Average of 6 numbers is 35.00
  ..................

Refer : http://www.geeksforgeeks.org/archives/15658

Find Next Palindrome Number

Given a number, find the next smallest palindrome larger than the number. For example if the number is 125, next smallest palindrome is 131.
Java program : 

public class NextPalindrome {
 public static void main(String[] args) {
  int n = 2133;

  // temp variable to perform operations on n
  int temp = n;
  // calculate the number of digits
  int digits = 0;
  while (temp != 0) {
   temp = temp / 10;
   digits++;
  }

  // edge case if the given number contains all 9 s like 9 or 99 or 999
  // or...,round off to next number
  int divider = (int) Math.pow(10, digits);
  if ((n + 1) % divider == 0) {
   n = n + 1;
   digits++;
  }
  if (digits == 0)
   return;

  // handling the special case of single digit numbers
  if (digits == 1) {
   System.out.println("Next higher palindrome is : " + n + 1);
   return;
  }

  // create array of size digits to store the digits of the given number
  int[] a = new int[digits];
  temp = n;
  for (int i = digits - 1; i >= 0 && temp != 0; i--) {
   a[i] = temp % 10;
   temp = temp / 10;
  }

  // now array contains the digits in same order as of number
  int nextPalindrome = 0;
  boolean isPalindrome = false;// used for track whether we got palindrome
  // or not
  while (!isPalindrome) {
   // create mirror image of the given number
   createMirrorImage(a);
   nextPalindrome = constructNumber(a);
   if (nextPalindrome <= n) {
    int middle = (int) Math.ceil(digits / 2);
    // if the middle digit is 9 then round off to the next higher
    // number
    if (digits % 2 == 0) {
     if (a[digits / 2] == 9) {
      a[middle] = 0;
      a[middle - 1] = 0;
      a[middle - 2] += 1;
     } else {
      a[middle] += 1;
      a[middle - 1] += 1;
     }
    } else {
     if (a[middle] == 9) {
      a[middle] = 0;
      a[middle - 1] = a[middle - 1] + 1;
     } else {
      a[middle] += 1;
     }

    }
   } else {
    isPalindrome = true;
   }
  }
  System.out.println("Next higher palindrome is : " + nextPalindrome);
 }

 private static int constructNumber(int[] a) {
  int num = 0;
  for (int i = 0; i < a.length; i++) {
   num = num * 10 + a[i];
  }
  return num;
 }

 private static void createMirrorImage(int[] a) {
  int length = a.length;
  for (int i = 0, j = length - 1; i <= j; i++, j--) {
   a[j] = a[i];
  }
 }
}

Refer :  http://www.ardendertat.com/2011/12/01/programming-interview-questions-19-find-next-palindrome-number/

Median of integer stream

Given a stream of unsorted integers, find the median element in sorted order at any given time. So, we will be receiving a continuous stream of numbers in some random order and we don’t know the stream length in advance. Write a function that finds the median of the already received numbers efficiently at any time. We will be asked to find the median multiple times. Just to recall, median is the middle element in an odd length sorted array, and in the even case it’s the average of the middle elements.
Refer : 
http://www.ardendertat.com/2011/11/03/programming-interview-questions-13-median-of-integer-stream/

http://www.geeksforgeeks.org/archives/14873

Missing element in an array

This question can be solved efficiently with a very clever trick. There is an array of non-negative integers. A second array is formed by shuffling the elements of the first array and deleting a random element. Given these two arrays, find which element is missing in the second array. Here is an example input, the first array is shuffled and the number 5 is removed to construct the second array.

Approach I :

The naive way to solve it is for every element in the second array, check whether it appears in the first array. Note that there may be duplicate elements in the arrays so we should pay special attention to it. The complexity of this approach is O(N^2). A more efficient solution is to sort the first array, so while checking whether an element in the first array appears in the second, we can do binary search. But we should still be careful about duplicate elements. The complexity is O(NlogN). If we don’t want to deal with the special case of duplicate numbers, we can sort both arrays and iterate over them simultaneously. Once two iterators have different values we can stop. The value of the first iterator is the missing element. This solution is also O(NlogN). 

Approach II :

We can use a hashtable and store the number of times each element appears in the second array. Then for each element in the first array we decrement its counter. Once hit an element with zero count that’s the missing element. The time complexity is optimal O(N) but the space complexity is also O(N), because of the hashtable. Ideally we would like to have constant space complexity.

Approach III : One possible solution is computing the sum of all the numbers in array1 and array2, and subtracting array2′s sum from array1′s sum. The difference is the missing number in array2. However, this approach is somewhat problematic. What if the arrays are too long, or the numbers are very large. Then overflow will occur while summing up the numbers.

Approach IV :  initialize a variable to 0, then XOR every element in the first and second arrays with that variable. In the end, the value of the variable is the result, missing element in array2.

Let’s analyze why this approach works. What happens when we XOR two numbers? We should think bitwise, instead of decimal. XORing a 4-bit number with 1011 would flip the first, third, and fourth bits of the number. XORing the result again with 1011 would flip those bits back to their original value. So, if we XOR a number two times with some number nothing will change. We can also XOR with multiple numbers and the order would not matter. For example, say we XOR the number n1 with n2, then XOR the result with n3, then XOR their result with n2, and then with n3. The final result would be the original number n1. Because every XOR operation flips some bits and when we XOR with the same number again, we flip those bits back. So the order of XOR operations is not important. If we XOR a number with some number an odd number of times, there will be no effect.

Above we XOR all the numbers in array1 and array2. All numbers in array2 also appear in array1, but there is an extra number in array1. So the effect of each XOR from array2 is being reset by the corresponding same number in array1 (remember that the order of XOR is not important). But we can’t reset the XOR of the extra number in array1, because it doesn’t appear in array2. So the result is as if we XOR 0 with that extra number, which is the number itself. Since XOR of a number with 0 is the number. Therefore, in the end we get the missing number in array2. The space complexity of this solution is constant O(1) since we only use one extra variable. Time complexity is O(N) because we perform a single pass from the arrays. 

Source : http://www.ardendertat.com/2011/09/27/programming-interview-questions-4-find-missing-element/

Next higher number with the same digits

Given a number, find the next higher number using only the digits in the given number. For example if the given number is 1234, next higher number with same digits is 1243.

The naive approach is to generate the numbers with all digit permutations and sort them. Then find the given number in the sorted sequence and return the next number in sorted order as a result. The complexity of this approach is pretty high though, because of the permutation step involved. A given number N has logN+1 digits, so there are O(logN!) permutations. After generating the permutations, sorting them will require O(logN!loglogN!) operations. We can simplify this further, remember that O(logN!) is equivalent to O(NlogN). And O(loglogN!) is O(logN). So, the complexity is O(N(logN)^2).

Let’s visualize a better solution using an example, the given number is 12543 and the resulting next higher number should be 13245. We scan the digits of the given number starting from the tenths digit (which is 4 in our case) going towards left. At each iteration we check the right digit of the current digit we’re at, and if the value of right is greater than current we stop, otherwise we continue to left. So we start with current digit 4, right digit is 3, and 4>=3 so we continue. Now current digit is 5, right digit is 4, and 5>= 4, continue. Now current is 2, right is 5, but it’s not 2>=5, so we stop. The digit 2 is our pivot digit. From the digits to the right of 2, we find the smallest digit higher than 2, which is 3. This part is important, we should find the smallest higher digit for the resulting number to be precisely the next higher than original number. We swap this digit and the pivot digit, so the number becomes 13542. Pivot digit is now 3. We sort all the digits to the right of the pivot digit in increasing order, resulting in 13245. This is it, here’s the code:

 public static void main(String[] args) {
  int n = 12543;

  // Count the number of digits in the number
  int numberOfDigits = 0;
  int temp = (int) n;
  while (temp != 0) {
   temp = temp / 10;
   numberOfDigits++;
  }

  // counting the number of digits is helpful in creating the array with
  // enough memory
  int[] a = new int[numberOfDigits];

  int i = numberOfDigits;
  while (n != 0) {// Storing the number in the array.
   int digit = (int) n % 10;
   n = n / 10;
   a[--i] = digit;
  }

  // At each iteration we check the right digit of the current digit we’re
  // at,
  // and if the value of right is greater than current we stop, otherwise
  // we continue to left.
  for (i = numberOfDigits - 1; i > 0; i--) {
   if (a[i] > a[i - 1]) {
    break;
   }
  }

  // Now i-1 will be the pivot element
  // Find the minimum element from i-1 to end which is higher than element
  // at position i-1
  int minIndex = i - 1;
  int minValue = a[i];
  for (temp = i; temp < numberOfDigits; temp++) {
   if (a[temp] < minValue && a[temp] > a[i - 1]) {
    minValue = a[temp];
    minIndex = temp;
   }
  }

  // swap the both digits
  temp = a[i - 1];
  a[i - 1] = a[minIndex];
  a[minIndex] = temp;

  // now sort the digits from last position to i
  countSort(a, i, numberOfDigits - 1);

  // calculating the number from array elements
  n = 0;
  for (i = 0; i < numberOfDigits; i++) {
   n = n * 10 + a[i];
  }

  System.out.println("Next higher number is : " + n);
 }

Note that if the digits of the given number is monotonically increasing from right to left, like 43221 then we won’t perform any operations, which is what we want because this is the highest number obtainable from these digits. There’s no higher number, so we return the given number itself. The same case occurs when the number has only a single digit, like 7. We can’t form a different number since there’s only a single digit.

The complexity of this algorithm also depends on the number of digits, and the sorting part dominates. A given number N has logN+1 digits and in the worst case we’ll have to sort logN digits. Which happens when all digits are increasing from right to left except the leftmost digit, for example 1987. For sorting we don’t have to use comparison based algorithms such as quicksort, mergesort, or heapsort which are O(KlogK), where K is the number of elements to sort. Since we know that digits are always between 0 and 9, we can use counting sort, radix sort, or bucket sort which can work in linear time O(K). So the overall complexity of sorting logN digits will stay linear resulting in overall complexity O(logN). Which is optimal since we have to check each digit at least once.

Move set of elements to destination location in an array

Move a set of elements (represented by start and end indexed) in an array to a given destination location (destination index).

Example:
Let say our array is {9, 7, 5, 8, 1, 5, 4, 8, 10, 1}
move_set (array, start = 1, end = 3, destination = 8)


Should rearrage the array such that the new array looks like {9, 1, 5,4, 8, 10, 7, 5, 8, 1}


This is just like exchanging first and second subset where first subset is from 1(start) to 3(end) and second subset is 4(end+1) to 8(destination)


Refer  : Swap two words in a given sentence.

Maximum contiguous product in an Array

Given an array of natural numbers (+ve, 0, -ve) find the maximum product of continuous elements.


input  : a = { 11, 4, 5, -2, 0, -3, -4, 4, 2, 3, 5, -7 };
output : 3360(From index positions 7 to 12)

class MaximumContiguousProduct {

 public static void main(String[] args) {
  int[] a = { 11, 4, 5, -2, 0, -3, -4, 4, 2, 3, 5, -7 };
  int product = getMaximumProduct(a);
  System.out.println(product);
 }

 /**
  * Track zero positions and calculate maximum product till zero
  * 
  * @param a
  * @return
  */
 public static int getMaximumProduct(int[] a) {

  if (a == null || a.length == 0)
   return 0;

  int start = 0;
  int maxSubArrayProduct = 0;
  int maxProduct = -3421545;
  for (int i = 0; i < a.length; i++) {
   if (a[i] == 0) {// if ith element is zero then send i-1 element as
    // end position
    maxSubArrayProduct = getMaxProductInSubArray(a, start, i - 1);
    start = i + 1;// skip the ith element.
   } else if (i == a.length - 1) {
    maxSubArrayProduct = getMaxProductInSubArray(a, start,
      a.length - 1);
   }
   if (maxSubArrayProduct > maxProduct)
    maxProduct = maxSubArrayProduct;
  }
  return maxProduct;
 }

 // in this sub array check if array contains even number of -ve numbers or
 // odd.
 // If it is even number,max product is product of all numbers
 // else we will get two products.
 private static int getMaxProductInSubArray(int[] a, int start, int end) {

  if (a == null || a.length == 0 || start > end)
   return 0;
  else if (start == end)
   return a[start];

  int numberOfNegativeNumbers = 0;
  int totalProduct = 1;
  for (int i = start; i <= end; i++) {
   if (a[i] < 0)
    numberOfNegativeNumbers++;
   totalProduct = totalProduct * a[i];
  }

  if (numberOfNegativeNumbers % 2 == 0)// handling case for even number of
   // negative numbers.
   return totalProduct;

  // for odd number of -ve numbers,total prod value is -ve.calculate prod1
  // and prod2
  int prod1 = 1;
  int i = start;
  while (a[i] > 0) {// calculating till we trace first -ve number
   prod1 = prod1 * a[i];
   i++;
  }
  int prodRem1 = totalProduct / (prod1 * a[i]);

  int prod2 = 1;
  i = end;
  while (a[i] > 0) {// calculating till we trace first -ve number
   prod2 = prod2 * a[i];
   i--;
  }

  int prodRem2 = totalProduct / (prod2 * a[i]);

  return prodRem1 > prodRem2 ? prodRem1 : prodRem2;
 }
}

Contiguous subarray with sum zero

Given an array with + and - numbers, including zero, Write an algorithm to find all the possible sub arrays which sum up to zero.
For example, if given array is
20 , -9 , 3 , 1, 5 , 0, -6 , 9
Then possible sub arrays are:
-9, 3, 1, 5
0
1, 5, 0, -6
Solution: 

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class ZeroSumContiguousSubArray {

 public static void main(String[] args) {
  int[] a = {20 , -9 , 3 , 1, 5 , 0, -6 , 9};
  System.out.println("actual array elements are :");
  printArray(a,0,a.length-1);  
  getSubArraysWithZeroSum(a);
 }

 private static void getSubArraysWithZeroSum(int[] a) {
  
  if(a==null || a.length==0) return;
    
  
  //construct a temporary array with sums
  int[] temp = new int[a.length+1];
  //add '0' as first element in the temporary array to simplify the code and cover edge conditions.
  temp[0] = 0;
  temp[1]=a[0];
  for(int i=2;i<temp.length;i++){   
   temp[i]=temp[i-1]+a[i-1];
  }
  
  //construct a hash map with sum as keys and list of positions as values;
  Map<Integer,List<Integer>> map = new HashMap<Integer, List<Integer>>();
  
  for(int i=0;i<temp.length;i++){
   if(map.get(temp[i])==null){
    List list = new ArrayList<Integer>();
    list.add(i);
    map.put(temp[i], list);
   }else{
    List list = map.get(temp[i]);
    list.add(i);
    map.put(temp[i], list);
   }
  }   
   //Retrieve the lists from map and check if list size is greater than one.
   //if the list size greater than one,get combinations and call print methods
  for(List<Integer> list : map.values()){
   if(list.size()>1){
    getCombinations(a,list);
   }
  }
 }

 private static void getCombinations(int[] a, List<Integer> list) {
  //select two elements from the list and call print method with element positions as starting and ending
  for(int i=1;i<list.size();i++){//here we can modify the code to select any two elements instead of side by side elements so that it prints all combinations
   printArray(a, list.get(i-1), list.get(i)-1);
  }  
 }
 
 private static void printArray(int[] a,int start,int end) {
  System.out.println();
  for(int i=start;i<=end;i++){
   System.out.print("  "+a[i]);
  }
  System.out.println();
 }  
}

Count number of min elements on right of each element in an array

You have an array like ar[]= {1,3,2,4,5,4,2}. 
You need to create another array  ar_low[] such that ar_low[i] = number of elements lower than or equal to ar[i] in ar[i+1:n-1].
So the output of above should be {0,2,1,2,2,1,0}

Algorithm :
1)Conside original array a[]
2)Construct a sorted list with the array elements(O(nlogn))
3)Traverse across all elements of the original array 'a' and find it's position(right occurence) in the sorted list using binary search.
  -position in the sorted list returns the number of elements in the less than the current element on right side.
  -after remove the current element from the sorted list.
PS: list is preferred datastructure because there are so many insertion and deletion operations.

public static int[] createLowArray(int[] a) {
  if (a == null || a.length == 0)
   return null;
  int length = a.length;
  int[] minArray = new int[length];

  // constructing a list from the array elements
  ArrayList<Integer> list = new ArrayList<Integer>();
  for (int i = 0; i < a.length; i++) {
   list.add(a[i]);
  }
  // sort the array 1 2 2 3 4 4 5
  Collections.sort(list);

  // traverse across all elements of the array and do the binary search in
  // the sorted list for it's position
  // after getting position(right occurrence),remove the element from the sorted list
  for (int i = 0; i < length; i++) {
   int pos = Collections.binarySearch(list, a[i]);
   // getting the right occurrence of the element position
   // we can iterate through elements to modify binary search to return
   // right occurrence
   while (pos < list.size()-1  && list.get(pos + 1) == list.get(pos)) {    
     pos++;    
   }
   minArray[i] = pos;
   list.remove(pos);// remove the element from the sorted list
  }
  return minArray;
 }

Note : Position count starts from 0. 

ex: {1,2,3,4} ...position of '1' is zero............

In the below approach,we are checking element position in the modified list(after deletion operation in the previous iteration).

given array is : ar[]= {1,3,2,4,5,4,2}.

construct a list with array elements and sort it.Now list contains :1,2,2,3,4,4,5

Now traverse through array elements from i=0 to n-1(start to end)

store result in result[] array.

list is 1-2-2-3-4-4-5

for i=0, a[0]=1,search for a[0] position in the list(right occurrence).a[0]=1 position in list is '0'

    add '0' to result.===>result[0]=0;

remove the element a[0] from the list.now list contains 2-2-3-4-4-5

for i=1,a[1]=3,search for a[1] position in the list(right occurence).a[1]=3 position in list is '2'

  add '2' to result====>result[1]=2

remove the element a[1] from the list.now list contains 2-2-4-4-5

for i=2,a[2]=2,search for a[2] position in the list(right occurence).a[2]=2 position in list is '1'

  add '1' to result====>result[2]=1

remove the element a[2] from the list.now list contains 2-4-4-5

for i=3,a[3]=4,search for a[3] position in the list(right occurence).a[3]=4 position in list is '2'

  add '2' to result====>result[3]=2

remove the element a[3] from the list.now list contains 2-4-5

for i=4,a[4]=5,search for a[4] position in the list(right occurence).a[4]=5 position in list is '2'

  add '2' to result====>result[4]=2

remove the element a[4] from the list.now list contains 2-4

for i=5,a[5]=4,search for a[5] position in the list(right occurence).a[5]=4 position in list is '1'

  add '1' to result====>result[5]=1

remove the element a[5] from the list.now list contains 2

for i=6,a[6]=2,search for a[6] position in the list(right occurence).a[6]=2 position in list is '0'

  add '0' to result====>result[6]=0

remove the element a[6] from the list.now list is empty.

resultant array contains : 

from all conditions : 

add '0' to result.===>result[0]=0;

add '2' to result====>result[1]=2

add '1' to result====>result[2]=1

add '1' to result====>result[3]=2

add '2' to result====>result[4]=2

add '1' to result====>result[5]=1

add '0' to result====>result[6]=0

expected result   {0,2,1,2,2,1,0}

actual result ==>{0,2,1,2,2,1,0}

 If we use java arraylist,it will find the element position in O(logn) time complexity using binarysearch.

Arraylist implements RandomAccess marker interface which facilitate it to find in O(long)

Refer : http://download.oracle.com/javase/6/docs/api/java/util/Collections.html#binarySearch(java.util.List, T)

This method runs in log(n) time for a "random access" list (which provides near-constant-time positional access). 

But problem of using arrayList is,when ever an element is removed from the list,all subsequent has to be moved.

If the given array is already sorted,it will reach worst case O(n*n).Because we need to move all elements as we find element to be removed at starting position.




Simple approach : Start with two loops,for each element count the number of minimum elements which are less than the element