Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
nice algo! small improvement is that you also have to take care
of boundary cases, i.e.,
if you search for '2' in {5,4,3,2,1}, the index i can become
negative, this can be fixed as follows:
for (i=0; i<arr.length;)
{
if (arr[i]==p)
{found = 1;
break;
}
i += abs(p - arr[i]);
}
you cannot do divide and conquer per se. The solution is not log n. It is just a heuristic approach which is better than O(n).
Since the numbers differ from each other in the magnitude of one. Take the first number and find the difference of it with the search number. move that many positions and check if that has the required number. Repeat this process until either u get the number or run out of length.
Consider the array a[0...n] Let i , j (i<j) be two indices. and you are looking for P
a[i]...a[j] can contain P if and only if
P > MIN( a[i] - (j-i) , a[j] - (j-i) )
and P < MAX( a[i] + (j-i) , a[j] + (j-i) )
Now you can do some kind of divide and conquer and reject ranges in which P cannot lie. Worst case will still be O(N).
The worst case here is O(n).
In order to search for the desired element we have to achieve less than n complexity, which essentially means we cant afford to make sequential search. Now 3 cases may arise in the given array:
1. it may be in increasing order eg: 3,4,5,6,7,8,9,10
2. it may be in decreasing order eg: 3,2,1,0,-1,-2,-3
3. it must allow repetition eg: 3,4,5,4,3,2,3,4,5,6,7,8,9,10,9
Lets take the 3rd case and search for 7.
- Tiscaaao! October 21, 2011