## Josh Interview Question for Software Engineer / Developers

• 3

Country: India
Interview Type: In-Person

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

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 = 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 we found x = 40 = A.

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 = 40 != 45, we can conclude that x = 45 doesn't exist in the array.

``Please ignore the previous post with text format error.``

EDIT:

``Code in C++ and clearer explanation can be found here: http://www.capacode.com/?p=86``

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

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;
}
}
}``````

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

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;

}``````

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

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 = 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 we found x = 40 = A.

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 = 40 != 45, we

can conclude that x = 45 doesn't exist in the array.

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

-1
Sorry for text format error! Please ignore it.

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

good solution!!!

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.