Amazon Interview Question SDE1s
Country: United States
Interview Type: In-Person
If the array is infinite, that means we don't have proper bounds to apply binary search.
So in order to find position of key, first we find bounds and then apply binary search algorithm.
Let low and high be pointing to 1st element of array,
Now compare key with high index element,
->if it is greater than high index element then copy high index in low index and double the high index
->if it is smaller, then apply binary search on high and low indices found.
int find_position(int arr[],int key) // we don't know the size of array
{
int l=0,h=0,val;
val=arr[0];
while(val<k)
{
l=h;
h=2*h;
val=arr[h];
}
// after finding low and high indices, apply binary search between them
return binSearch(arr,l,h,k);
}
This would run in O(log n).
One thing to note is that if arr[h] happens to equal the key while you're finding the bounds, binSearch will be applied to a subarray where the element you want to find is at the very left index. Worst case, it will still be found in O(lgn), but we could also check if a[h] == k during finding the bounds. How valuable this is can be left up to discussion.
Following is my solution to the above mentioned problem.
Approach: Binary search; count the occurrence when a match is found
Complexity: O(logn)
public int noOfOccurence(int n, int a[])
{
int lo=0, hi=a.length-1, m;
while(lo <= hi)
{
if((hi - lo) == 1){
if(a[hi] == n) return 1;
if(a[lo] == n) return 1;
else return -1;
}
m = (lo+hi)/2;
if(a[m] > n){hi = m;}
else if(a[m] < n){lo = m;}
else{
int lt = m , rt = m;
int count = 0;
while((lt >= 0) && (rt < a.length)){
if((a[lt] == n)) count++;
if((a[rt] == n)) count++;
else return count-1;
lt--; rt++;
}
return count-1;
}
}
return -1;
}
Following is the solution to above mentioned problem.
Approach: Binary search; count the occurrence when match is found
Complexity: O(logn)
public int noOfOccurence(int n, int a[])
{
int lo=0, hi=a.length-1, m;
while(lo <= hi)
{
if((hi - lo) == 1){
if(a[hi] == n) return 1;
if(a[lo] == n) return 1;
else return -1;
}
m = (lo+hi)/2;
System.out.println("mid:"+m);
if(a[m] > n){hi = m;}
else if(a[m] < n){lo = m;}
else{
int lt = m , rt = m;
int count = 0;
while((lt >= 0) && (rt < a.length)){
if((a[lt] == n)) count++;
if((a[rt] == n)) count++;
else return count-1;
lt--; rt++;
System.out.println("count:"+count);
}
return count-1;
}
}
return -1;
}
Typical CS graduate answers...
The array is sorted, so use it to your advantage. Just index directly to the number you're looking for and then all you need to account for are duplicates that occurred earlier. For example, if you're looking for 151, set your left bound to array[151]. Now you can double your index to find the right bound and do your searching.
Consider the sample input sequence provided in the post by AJ (i. e. sparse value set), then explain where your algorithm breaks down.
Consider the input sequence proposed in the post by AJ (i.e. sparse value set). Indexing at the ith position, setting that as the left bound and beginning the subsearch from that point on won't work, as it is not guaranteed that all (or any) instances of the value i will be in the sequence a[i] .... a[2i]....a[4i].... etc.
As this is infinite array there won't be end boundary...
- So start searching at exponential index like search at index 2^n where n=0,1,2,3,.....
- Once index is found at index 'i' then
count = 1
index = i-1;
while a[i] == a[index] {
count ++
index --
}
index = i+1;
while a[i] == a[index] {
count ++
index++
}
here the value of count would be no. of occurrence of input number
As this is infinite array there won't be end boundary...
- So start searching at exponential index like search at index 2^n where n=0,1,2,3,.....
- Once index is found at index 'i' then
count = 1
index = i-1;
while a[i] == a[index] {
count ++
index --
}
index = i+1;
while a[i] == a[index] {
count ++
index++
}
here the value of count would be no. of occurrence of input number
/**
* Suppose you have an array with infinite numbers,
* which is sorted and there may be duplicates.
* Find the occurrence of a number.
*/
def findDuplicate(xs:Stream[Int], n:Int):Boolean = {
def helper(previous:Int, index:Int, upperBound:Option[Int]): Boolean = {
val value = xs(index)
if(value == n) {
value == xs(index-1) || value == xs(index+1)
}
else if(value < n) {
val upperValue = upperBound.getOrElse(3*index)
val nextIndex = index + (upperValue - index)/2
helper(index, nextIndex, upperBound)
}
else {
val nextIndex = previous + (index - previous)/2
helper(previous, nextIndex, Some(index))
}
}
helper(0, 1, None)
}
The solution instead to iterate on every single element of the list, is doubling the index to check each time, once the value at the index is greater than the value we are looking for, will move to the middle index between the current position and the previous and keep it doing recursively until it converges.
#include<stdio.h>
#include<string.h>
int main ()
{
int inf_array[] = {1,2,3,4,5,6,7,8,9,9,12,13,14,15,15,16,17,18,19,20,20};
int search_num = 20;
int array_size = sizeof inf_array / sizeof *inf_array;
int low, high, mid, idx, result;
low = 0;
result = -1;
high = array_size - 1;
mid = (array_size-1)/2;
printf("LOW MID HIGH VALUE\n");
while ( low <= high) {
printf("%d %d %d %d\n",low, mid, high, inf_array[mid]);
if ( inf_array[mid] == search_num ) {
result = mid;
// Keep any of the given 3 line based on your requirements.
high = mid-1; //first occurance of a number.
//low = mid+1; // Last occurance of a number.
//break; // just finding.
} else if ( inf_array[mid] > search_num ) {
high = mid-1;
} else {
low = mid+1;
}
mid = (low + high)/2;
}
if ( result < 0){
printf("Number [%d] does not exists in array.\n", search_num);
} else {
while ( (inf_array[result] == search_num) && (result < array_size) ){
printf("Number [%d] found at index - %d.\n", search_num,result);
result++;
}
}
}
public int[] product(int[] arr){
int[] returnArray = new int[arr.length];
int zeroElementIndex = -1;
int product = 1;
for(int i=0;i<arr.length;i++){
if(arr[i] == 0){
zeroElementIndex = i;
break;
}else{
product = product * arr[i];
}
}
if(zeroElementIndex != -1){
product =1;
for(int j=0;j<arr.length;j++){
if(j != zeroElementIndex)
{
returnArray[j] = 0;
product = product * arr[j];
}
}
returnArray[zeroElementIndex] = product;
}else{
for(int j=0;j<arr.length;j++){
returnArray[j] = product/arr[j];
}
}
return returnArray;
}
/**
This solution runs in O(n).
It traverse through entire array to calculate product. If it finds zero at any element, it will remember that index and breaks the loop.
Now there can be 2 cases:
1) Zero element found at any index: In this case it will set all other index as zero in resulting array and calculate product for zero index element.
2) No element is zero in array: Divide product with individual value of an array to calculate new array elements.
**/
public int[] product(int[] arr){
int[] returnArray = new int[arr.length];
int zeroElementIndex = -1;
int product = 1;
for(int i=0;i<arr.length;i++){
if(arr[i] == 0){
zeroElementIndex = i;
break;
}else{
product = product * arr[i];
}
}
if(zeroElementIndex != -1){
product =1;
for(int j=0;j<arr.length;j++){
if(j != zeroElementIndex)
{
returnArray[j] = 0;
product = product * arr[j];
}
}
returnArray[zeroElementIndex] = product;
}else{
for(int j=0;j<arr.length;j++){
returnArray[j] = product/arr[j];
}
}
return returnArray;
}
Double the index until you find a larger element, then binary search between the last two indices.
- Anonymous February 20, 2015