## Google Interview Question for Software Engineers

• 1
of 1 vote

Country: United States

Comment hidden because of low score. Click to expand.
2
of 2 vote

``````private 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);
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

Why no one is commenting on their code or explaining it, it's really frustrating.
Don't get the point of just pasting a block of code

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);
}``````

Comment hidden because of low score. Click to expand.
0
of 4 vote

Isn't it LIS(longest increasing subsequence)

Comment hidden because of low score. Click to expand.
0

Yes it is!

Comment hidden because of low score. Click to expand.
1
of 1 vote

No, check the array [5,6,4,2,8]

The LIS will get 3, while the binary search should get 2

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);``````

}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.