mock interview quick select

mock interview quick select

/*
  let me know when you are ready
Problem**: Let's say 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.)

Set:
O(N) time
O(N) space

3, 1, 1, 3
index swap[0, 3]
2, 1, 2, 3
O(N) time
O(1) space (in-place)

3, 1, 1, 3
1, 3, 2, 2
Double for-loop: O(N^2)
Sorted array: O(NlogN)
In-place sorting: Quicksort, heapsort
3 1 1 3 [1, 3]
1 1 3 3   2
[1,1] [3,3]

T(N) = T(N / 2) + N
			 T(N/4) + N/2 + N
       1 + N + N/2 + N/4 + ... 1
    =  O(N)
    
    
    
3 1 2 3 4 5
1 2 3 3 4 5
1 2 3 3 4 5
    3 3 4 5
    3 3
    
    
1 1 1 1 1 1 1 [1, 7]
1 1 1 1 1 1 1 [1, 4]
1 1 1 1 1 1 1 [1, 2]

*/

public static int findDuplicate(int[] arr) {
  int lo = 1;
  int hi = arr.length - 1;
  while (lo < hi) {
    int pivotVal = (hi - lo) / 2;  // pivot value is not index, 1 to N 
    int pivotIdx = partition(arr, pivotVal, lo - 1, hi);
    int left = pivotIdx - lo;    
    
    if (left == pivotVal) {
      // Left is valid, so go to right
      lo = pivotVal;
    } else {
      // Go to left
      hi = pivotVal - 1;
    }
  }
  
  return arr[lo];
}

private static void swap(int[] arr, int a, int b) {
  int temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
}

// duplicate check -> piggy back extra function -
// interviewk
private static int partition(int[] arr, int midVal, int lo, int hi) {  // - partition by value -> 1 - N, 4, 2, 1
  /* [lower, greater or equal] */
  int lower = lo;
  for (int i = lo; i < hi; i++) { // [1, 1,1, 1,1, 1] - middle 
    if (arr[i] < midVal) {
      swap(arr, i, lower);
      lower++;
    }
  }
  
  return lower + 1;
}

/*
kth largest in unsorted array (or kth smallest, or median)
[5 2 1 3 6]
[2 1 3* 5 6]
[2 1]
[1 2*]

T(N) = T(N / 2) + N
*/