Josh Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
Here is a code for the same.
#include<iostream>
using namespace std;
int findE(int a[],int s,int e,int k,int m){
if(s>e) return m; //return the neighbor
m=(s+e)/2;
if(m%2){
if(a[m]==k) return m;
if(a[m]<k) return findE(a,m+2,e,k,m);
return findE(a,s,m-2,k,m);
}
else{
if(m-1>=0&&a[m-1]==k) return m-1;
if(m+1<=e&&a[m+1]==k) return m+1;
if(m-1>=0&&a[m-1]<k) return findE(a,m+1,e,k,m);
if(m-1>=0&&a[m-1]>k) return findE(a,s,m-3,k,m);
if(m+1<=e&&a[m+1]<k) return findE(a,m+3,e,k,m);
if(m+1<=e&&a[m+1]>k) return findE(a,s,m-1,k,m);
}
}
int main(){
int a[]={0,1,2,3,8,5,10,7,4,9,6};
int n=11;
int k=7;
int t=findE(a,0,n-1,k,-1);
if(a[t]==k){
cout<<"found at "<<t;
}
else{
//we need to check the neighbors of t
if(t-1>=0&&a[t-1]==k) cout<<"found at "<<t-1;
else if(t+1<n&&a[t+1]==k) cout<<"found at "<<t+1;
else{
int m;
//it has been swapped with some other element. so,if k>a[t] search for a[t+1] else search for a[t-1] and check the neighbors of the returned ind.
if(t-1>=0&&a[t]>k) m=findE(a,0,n-1,a[t-1],-1);
else if(t+1<n&&a[t]<k) m=findE(a,0,n-1,a[t-1],-1);
if(m-1>=0&&a[m-1]==k) cout<<"found at "<<m-1;
else if(m+1<n&&a[m+1]==k) cout<<"found at "<<m+1;
else cout<<"not found";
}
}
}
here's the recursive implementation in C for above approach:
int flag=0;
int search(int list[], int lo, int hi, int key)
{
int mid;
if (lo > hi)
{
return hi;
}
mid = (lo + hi) / 2;
if (list[mid] == key)
{ flag=1;
return mid;
}
else if (list[mid] > key)
{
search(list, lo, mid - 1, key);
}
else if (list[mid] < key)
{
search(list, mid + 1, hi, key);
}
}
int search(int list[],int x,int size){
int l=0,r;
if(size%2==0){
r=size-2;
}
else r=size-1;
int pos=search(list,x,l,r);
if(flag){
return pos;
}
if(list[pos+1]==x){
return pos+1;
}
pos=search(list,list[pos+1],l,r);
if(list[pos+1]==x){
return pos+1;
}
else return -1;
}
Observation: odd positions are not swapped, and are still sorted. They will help us to locate the element x that we are looking for.
First, do a binary search on these odd positions. If we can find x, then we are done.
If not, then we consider the last range that our binary search ends up with. That range must be (k, k+2), where k is some odd
number.
In the original array, x must be there at position k+1 (if such x exists). Now we check for the position k+1 in the modified array A.
If A[k+1] == x (this position is not swapped), then we are done.
If A[k+1] != x, then either x doesn't exist or x was swapped.
We check whether x was swapped: Which element that x was swapped with? x must have been swapped with A[k+1], since an
element may be swapped only one!
Let y = A[k+1]. Now we do second binary search for y on only odd positions. This 2nd binary search will end up with an other range
(p,p+2) where p is some odd number.
Since x and y were swapped together, x must be in the positions A[p+1], otherwise x doesn't exist.
Time complexity: O(log n) for 2 binary seach calls.
Example:
=======
With this modified array: 10, 20, 30, 80, 50, 100, 70, 40, 90, 60 and we are looking for x= 40.
First binary search on odd positions to look for 40 will end up with the range (3,5). Check the element on y = A[4] = 80. Thus, if x
exists, x must have been swapped with y= 80.
Now second binary search on odd positions to look for y = 80 will end up with the range (7,9). Check A[8] we found x = 40 = A[8].
If we want to look for, say, x = 45. The second binary search will end up with the same range (7,9) as above. But A[8] = 40 != 45, we
can conclude that x = 45 doesn't exist in the array.
Observation: odd positions are not swapped, and are still sorted. They will help us to locate the element x that we are looking for.
First, do a binary search on these odd positions. If we can find x, then we are done.
If not, then we consider the last range that our binary search ends up with. That range must be (k, k+2), where k is some odd number.
In the original array, x must be there at position k+1 (if such x exists). Now we check for the position k+1 in the modified array A.
If A[k+1] == x (this position is not swapped), then we are done.
If A[k+1] != x, then either x doesn't exist or x was swapped.
We check whether x was swapped: Which element that x was swapped with? x must have been swapped with A[k+1], since an element may be swapped only once!
Let y = A[k+1]. Now we do second binary search for y on only odd positions. This 2nd binary search will end up with an other range (p,p+2) where p is some odd number.
Since x and y were swapped together, x must be in the positions A[p+1], otherwise x doesn't exist.
Time complexity: O(log n) for 2 binary search calls.
Example:
=======
With this modified array: 10, 20, 30, 80, 50, 100, 70, 40, 90, 60 and we are looking for x= 40.
First binary search on odd positions to look for 40 will end up with the range (3,5). Check the element on y = A[4] = 80. Thus, if x exists, x must have been swapped with y= 80.
Now second binary search on odd positions to look for y = 80 will end up with the range (7,9). Check A[8] we found x = 40 = A[8].
If we want to look for, say, x = 45. The second binary search will end up with the same range (7,9) as above. But A[8] = 40 != 45, we can conclude that x = 45 doesn't exist in the array.
EDIT:
- ninhnnsoc October 03, 2014