April 8, 2018 quick select algorithm mock interview

Quick select algorithm mock interview

9:12 pm
10:25 pm

/*

You have a list of N+1 integers between 1 and N. 
You know there's at least one duplicate, but there might be more. 
For example, if N=3, your list might be 3, 1, 1, 3 or it might be 1, 3, 2, 2. 
Print out a number that appears in the list more than once. 
(That is, in the first example, you can print '1' or '3' -- 
you don't have to print both.)

Pigeon Hold Principle
*/

3, 1, 1, 3 -> duplicate, 
no duplicate, N + 1, between 1 and N -> N numbers
at least one duplication 
assume that there is one duplicate number - how many times? k times
brute force solution: 
iterate the array once -> put number 
counting sort using array -> 
arr[index] = 1 -> arr[0] -> arr[N] -> O(N) -> find the solution
linear time, extra
1 -> 0   -> space complexity O(N)
N -> N - 1
  
  next solution:
  constraints:
Constant space, not allow to modify the original array, i.e. input from CD

possible -> O(nlogn) sort -> sort the array in ascending order
space complexity -> in place sorting i.e. quick sort

4, 3,| 1, 2-> draw 
4 |3
3, 4, | 1, 2 -> 
  
  3, 1, 1, 3
  |  -  -  -   find one return 
     |  -  - 
  time complexity: O(n^2)
  space complexity: O(1)
3, 1, 1, 3    
         pivot value
< 3
left side, right side
         <- pivot value ->
-> sort one -> 
partition - two partition -> 
    /*
     1  3   5  22   33   5  2    8    7
     																	pivot
		           low while<pivot                               
    												hi>=pivot
     1  3   5  2   33   5   22    8    7
               low
               							hi
     * */
    
    
int inplacePartitionPivotLastPosition(int[] numbers )  // [4,  1, 2]
  {
    if(numbers == null || numbers.Length == 0) // false
    {
      return -1;
    }
    
    var length = numbers.Length; // 3
    
    var pivotValue = numbers[length - 1]; // 2
    
    var start = 0;   // 0
    var end = length - 1; // 2
    while(start < end) // 
    {
      var startValue = numbers[start]; // 4
      var endValue = numbers[end]; // 2
      
      /*
      if(startValue > pivotValue && endValue < pivotValue)  // swap
      {
        // swap two values
        swap(numbers, start, end);
      }
      
      // one of break
      if(startValue < pivotValue)  // should = equal sign
        start++; 
      if(endValue >= pivotValue) // true
        end--; // 2, 1, 0
    }
    */
    while(start < end) // 
    {            
      while(numbers[start] < pivotValue)  // should = equal sign
        start++; 
      while(end >= 0 && numbers[end] >= pivotValue) // true
        end--; // 2, 1, 0
      
      if(start < end)  // swap
      {
        // swap two values
        swap(numbers, start, end);                
      }            
    }
    
    return end;       
  }
/*
0    1,   2
5,   1,   3

test case: 
0  1  2  3
1, 1, 1, 1, 
s        e 
pivot value is 1 
*/
    
    
    /*
n=3, 1 2 3 are possible numbers, length=4
1    3     3     2
                pivot
1    2     3     3              
     pivot

left side should have how many elements if duplicates? 1
right side should have how many elements if duplicates? 1

n + n/2 + n/4 +..  = O(n)
1 + 1/2 + 1/4 + ... < 2
pivot value is 2 -> 1

*/

class Solution {
  	0  1  2  3  4
    1  2  2  3  2
  	low=0, high=4
      mid=0+(4-0)/2=2;  	
    ct = smallerAndEqualTo2 = 4   
    high=2
    mid=0+(2-0)/2=1;
    ct = smallerAndEqualTo1 = 1
    low=mid+1=1+1
    public static int findDuplicate(int[]nums){
        int low=0, high=nums.length-1;
        while(low<high){
            int mid=low+(high-low)/2;
            int ct=countSmallerAndEqualToMidNums(nums, mid);
            
            if(ct>mid){//too many numbers
                high=mid;
            }
            else{
                low=mid+1;
            }
        }
        return low;
    }
    
    public static int countSmallerAndEqualToMidNums(int[]nums, int mid){
        int ct=0;
        
        for (int i=0; i<nums.length; i++)        
        {    
            if(nums[i]<=mid){
                ct++;
            }
        }    
        return ct;
    }
}