Google Interview Question
Software EngineersCountry: United States
static int countPossibleMatches(int[] array, int left, int right, int min, int max) {
if (right < left) {
return 0;
} else if (right == left) {
return (array[left] >= min && array[left] <= max? 1 : 0);
} else {
int middle = (left + right) / 2;
int count = (array[middle] >= min && array[middle] <= max ? 1 : 0);
count += countPossibleMatches(array, left, middle - 1, min, Math.min(array[middle], max));
count += countPossibleMatches(array, middle + 1, right, Math.max(array[middle], min), max);
return count;
}
}
static int countPossibleMatches(int[] array) {
return countPossibleMatches(array, 0, array.length - 1, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
This will produce unstable search depending on how you define midpoint. If it is with Math.ceil() then we can find 5 but not 4. However if it is with Math.round() you can find 4 but not 5.
function binarySearch(array, elm){
function binarySearchIter(arr, index){
let midpoint = Math.round(arr.length / 2);
let left = arr.slice(0, midpoint);
let right = arr.slice(midpoint);
if (arr[midpoint] === elm){
return index + midpoint;
}
else if (arr.length <= 1){
return -1;
}
else {
let leftRes = binarySearchIter(left, index);
let rightRes = binarySearchIter(right, index + midpoint);
return leftRes > -1 ? leftRes : rightRes;
}
}
return binarySearchIter(array, 0);
}
- Ilya April 22, 2019