Google Interview Question Developer Program Engineers
here if scores are integer than above sol will not work.
If they are double than how can u say that x+-5 will the next lower and higher number. There may be x-+(0.1 or 0.2 0r ......)
ya i got ur point.but y binary search.is it because we hav a sorted array ? i guess linear search is easier to implement.please correct if i am wrong. Thanks
Since the array is sorted, start at the center of the array discarding one half each time, till we find the element we want to count. Once we have the element, go back and forth in the entire array till all the occurrences of the element are found.
This will limit the search complexity to log(n).
It is actually the worst case scenario and the time complexity would be O(n) and not lg(n)
It is actually the worst case scenario and the time complexity would be O(n) and not lg(n)
<pre lang="java" line="1" title="CodeMonkey19340" class="run-this">/* Note : we don't need array b according to problem I am keeping to
test my program for finding occurrences of all score.*/
class BinarySearch {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a = new int[] { 10, 10, 10, 10, 10, 20, 20, 20, 30, 30, 40, 40,
100, 100, 100 };
int[] b = { 10, 20, 30, 40, 100 };
for (int i = 0; i < b.length; i++) {
float l = (float) b[i] - 0.5f;
float h = (float) b[i] + 0.5f;
int lowerIndex = binarySearch(a, 0, a.length - 1, l);
int highIndex = binarySearch(a, 0, a.length - 1, h);
System.out.println(b[i] + " repeated: " + (highIndex - lowerIndex)
+ " times");
}
}
private static int binarySearch(int[] a, int low, int high, float k) {
while (low <= high) {
//<= very Important
int mid = low + (high - low) / 2;
if (a[mid] < k) {
low = mid + 1;
} else if (a[mid] > k) {
high = mid - 1;
} else {
return mid;
}
}
return high;
}
}
</pre><pre title="CodeMonkey19340" input="yes">
</pre>
This is My second Logic as mentioned in first post.
A= { 10, 10, 10, 10, 10, 20, 20, 20, 30, 30, 40, 40, 100, 100, 100 };
If you want to find occurrence of 20.
1)binary search for 20-0.5 = 19.5
it will return lowIndex = 4.
2)BinarySearch for 20+0.5 =20.5
It will return highIndex = 7
Occurrence of 20 = highIndex - lowIndex = 7-4 =3
You are really good if you solve this on front of the interviewer on that day. Did you apply for New Grad or Jr. Position?
Right but was the position titled Developer Programs Engineer - New Grad?
Also do you have an email/skype? Would love to ask you some questions.
We can do one more optimization. We know input data is in range 0 to 100. In average case, data will be uniformly distributed in the given range.
Suppose we have to search for element 75. There is high probability that this element will be present near index |n*75/100|. Then instead of doing mid = (low+high)/2, we can do mid = (low+high)*75/100, in the first pass. For subsequent passes also some optimization can be applied, so that mid index is nearer to mid index at previous pass.
What you say?
It's a good point worth mentioning but be careful not to assume any average case; different apps will have different "average cases". Just say that depending on apps you might have particular distributions of elements in the array and that could be exploited for greater search efficiency.
<pre lang="c++" line="1" title="CodeMonkey21547" class="run-this">#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
int countSortedOccurrence(const vector<int> &vec, const int val)
{
const pair<vector<int>::const_iterator,
vector<int>::const_iterator> range =
equal_range(vec.begin(), vec.end(), val);
const int count = distance(range.first, range.second);
return count;
}
int main(int argc, char *argv[])
{
const int data[] = { 1, 1, 1, 40, 40, 40, 100, 100 };
const int num = sizeof(data) / sizeof(*data);
const vector<int> vec(data, data+num);
const int cnt40 = countSortedOccurrence(vec, 40);
printf("The value (40) occurs (%d) times.\n", cnt40);
const int cnt33 = countSortedOccurrence(vec, 33);
printf("The value (33) occurs (%d) times.\n", cnt33);
return 0;
}
</pre><pre title="CodeMonkey21547" input="yes">
</pre>
Sorry for the previous badly formatted code ...
Python implementation of the left and right limit bin_search discussed above.
def left_bsearch(array, range, elt):
i, j = range
if i >= j:
return None
p = (i+j) // 2
if array[p] == elt and (not p or array[p-1] < elt):
return p
range = (p+1, j) if array[p] < elt else (i, p)
return left_bsearch(array, range, elt)
def find_element_frequency(array, elt):
n = len(array)
left_idx = left_bsearch(array, 0, n, elt)
# Note that array[::-1] accesses the original array from the
# right. It does not reverse the array at all.
right_idx = n - 1 - left_bsearch(array[::-1], 0, n, elt)
return right_idx - left_idx + 1
Solution 1 : I said binary search for score in this example 40 which in turn will give and index and then have two pointer one goes left and one go right and count the 40.
- MaYanK July 29, 2010worst case O(n) if all numbers are 40.
Solution 2 : Modify the binary search such that when element does not exists it return s low index. and then do binary search 39.5 and 40.5 (score-0.5 and score +0.5)
searching 39.5 will give you index 2 which is one less than start index of 40.
searching 0.5 will give you index 6 which is one more than end index of 40.
He did not ask me to code this just want to have idea. I told him we need to handle some edge condition.