Morgan Stanley Interview Question Developer Program Engineers
Country: India
Interview Type: Phone Interview
how will you store the data to start binary search on that? As we dont know the size of it.
To expand on algos' answer:
He gives O(log(n)) as the runtime. I explain how to get that:
Suppose the target number is in the range 2^(m-1) -> 2^m - 1.
Then, m comparisons would have to be done first as per algos' algo. So, this takes theta(m) time.
Then, binary search on the range would take O(m) time ( Why? See below. )
Binary search takes O(log(size of range)) time. O(log(size of range)) = O(log( 2^m - 1 - 2^(m-1)) = O( log(2^(m-1) )) + O(1 - 2^(1-m)) = O(m-1) + O(1 - 2^(1-m)) = O(m)
So, the total search time would take O(m) time (theta(m) + O(m) = O(m)).
Suppose the size of the array is n. In the worst-case, the target number would be in the last range and the last range would be "full", i.e. there are numbers in every spot. Then, the last range ends at index 2^(x)-1. And 2^(x)-1 = n-1, so, x = log(n). So, worst-case m would be log(n). So, the search time is O(log(n)), just as algos said.
assuming that data is in array, and applying binary search logic on that array, so time complexity is O(log n).
if data is NOT in array and is stored some where like file, stream data coming or something else then it takes O(n) time to read the full data
@Algo: just a corner case:
suppose there are 38 elements in array but some how we dont know the limit of array.
u found index = 16 to 32 and element not found
now u tried to make range 33 to 64 but element array[64] doesn't exist
how efficiently would you go back to element array [38]
one possible case handling I think is:
in case array [64] not present go for mid of 32 and 64 for MaxSearchRange= 48
array [48] also doesn't exist the go for array [40]... and so on...
/*
Algo:---
lets say the array hit an exception at index p so element is 2^p -1 or entry greater or equal to k;
so we will search 2^p-1 tp 2^p -2 because 2^p -1 hit an exception
run O(logn)
*/
#include<iostream>
#include<vector>
using namespace std;
template<typename T>
int reverse_binary_search(const std::vector<T> &array ,const T &k)
{
int p=0;
while(true)
{
try{
T val=array.at((1 << p) -1);
if(val == k)
{
return ((1 << p)-1);
}
else if( val > k)
{
break;
}
}
catch(exception &e )
{
break;
}
++p;
}
int l=1 <<(p -1);
int r=(1 << p) -2;
while(l <=r)
{
int m =l+((r - l) >> 1);
try
{
T val =array.at(m);
if(val == k)
return m;
else if(val > k)
r=m-1;
else
l=m+1;
}catch(exception &e)
{
r=m-1;
}
}
return -1;
}
int main()
{
int arr[]={1,2,3,4,5,6};
std::vector<int>myvector(arr,arr+sizeof(arr)/sizeof(arr[0]));
int a=reverse_binary_search(myvector,12);
cout<<"index ="<<a<<endl;
return 0;
}
question: in this particular case why don't we change the the base to a higher number like 3,4 or 5.. So that the range becomes: 0-2,3-8,9-16.....; 0-3,4,-15,16-63..... and so on.. in the inner loop we could go in for something smaller, i guess. complexity stays O(logn) but this log ll be base 3 or 4 or 5 instead of 2.
Hashtable would take up a lot of space. The question says the size is not known, that itself shows the input is very large. Moreover, you say the space is O(1). The space is O(n).
- algos March 30, 2013