## Morgan Stanley Interview Question for Developer Program Engineers

Country: India
Interview Type: Phone Interview

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

``````time complexity is O(log n)

variation of binary search i.e.. reverse binary search.
check the target number is present in below index ranges i.e.. 2^n index range
0-1
2-3
4-7
8-15
16-31
32-63
.
.

if target number is found in any of the above range then apply binary search on that data

int start=0, end = 1;
if target <= a[end]
apply binary search for the range start and end
else
start = end +1;
end = end*2+1;``````

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

Can you please explain a bit more? How do you locate the range in array?

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

how will you store the data to start binary search on that? As we dont know the size of it.

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

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.

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

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

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

@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...

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

/*
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;
}

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

Wont fibonacci search yield O(log n)?

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

If fibonacci series behaves like a logarithmic series after some time, i.e its graph is similar to a log graph after 100k or 1 mil iterations then I guess it can be considered..

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

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.

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

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).

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

sorry its o(n) .. typo ... however if u are storing n intigers then u need o(n) space anyways !!

However I missed out the sorted part ... may be interviewer wanted to hear interpolation search ..

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.