## Adobe Interview Question for MTSs

• -2

Country: India
Interview Type: In-Person

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

``````int findElement(int value, int array[]){
return(modifiedBinarySearch(value, array, 0, array.length);
}

// Modified binary search function that detects rotation in array
// and compensates accordingly.
int modifiedBinarySearch(int value, int array[], int start, int end){
// Base case for recursive method
if(end - start <= 1){
if(array[start] == value)
return(start);
else if(array[end] == value)
return(end);
else
return(-1);
}
int mid = (start + end) / 2;
// Another exit base case
if(array[mid] == value)
return(mid);
if (array[start] < array[mid]) &&
array[start] < value && array[mid] > value)
// First half of array is not rotated and value is within its range
return(value, array, start, mid);
if (array[start] > array[mid]) &&
(array[start] < value || array[mid] > value))
// First half of array is rotated and value is within its range
return(value, array, start, mid);
if (array[mid] < array[end]) &&
array[mid] < value && array[end] > value)
// Second half of array is not rotated and value is within its range
return(value, array, mid, end);
if (array[mid] > array[end]) &&
(array[mid] < value || array[end] > value))
// Second half of array is rotated and value is within its range
return(value, array, mid, end);
// Value is not is array
return(-1);
}``````

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

private static int circularBinSearch ( int key, int low, int high )
{
if (low > high)
{
}

int mid = (low + high) / 2;
steps++;

if (A[mid] == key)
{
return mid;
}
else if (key < A[mid])
{
return ((A[low] <= A[mid]) && (A[low] > key)) ?
circularBinSearch(key, mid + 1, high) :
circularBinSearch(key, low, mid - 1);
}
else // key > A[mid]
{
return ((A[mid] <= A[high]) && (key > A[high])) ?
circularBinSearch(key, low, mid - 1) :
circularBinSearch(key, mid + 1, high);
}
}

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

This one works in log n

``````private static int _findInRotatedArray(int[] arr, int n, int leftIndex, int rightIndex){
int len = rightIndex - leftIndex + 1;
if(len == 1) return arr[leftIndex] == n ? leftIndex : -1;
boolean isRotated = arr[leftIndex] > arr[rightIndex];
if(!isRotated && !(arr[leftIndex] <= n && arr[rightIndex] >= n)) return -1;
int left = _findInRotatedArray(arr, n, leftIndex, (int) (rightIndex - Math.ceil(len/2)));
return left > -1 ? left :_findInRotatedArray(arr, n, (int) (leftIndex + Math.floor(len/2)), rightIndex);
}``````

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

``````bool search(int a[],int begin,int end,int x)
{
if(begin > end)
{
return false;
}
else
{
int middle = (begin+end)/2;
if(a[middle] == x)
{
cout<<middle;
return true;
}
else
{
if(a[begin] > a[middle])
{
if(x < a[middle])
{
return search(a,begin,middle-1,x);
}
else
{
if(x < a[begin])
{
return search(a,middle + 1,end,x);
}
else
{
return search(a,begin,middle-1,x);
}
}
}
else
{
if(x > a[middle])
{
return  search(a,middle + 1,end,x);
}
else
{
if(x < a[begin])
{
return search(a,middle+1,end,x);
}
else
{
return search(a,begin,middle-1,x);
}
}
}
}
}
}``````

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

for 10 20 30 5 8 9 12 14 .. if we search 12 will it give correct answer ??

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

``````int findElement(int a[],int n, int val)
{
int start = 0;
int end = n-1;
int mid = (start+end)/2;
while(start <= end)
{
if(a[mid] == val)
return mid;

// if mid value is less than search value.
if(a[mid] < val)
{
// check if end value is smaller than search value.
// if it is we need to search in start to mid-1
// else search in mid+1 to end
if(a[end] < val)
end = mid-1;
else
start = mid+1;
}
// mid value is greater than search value.
else
{
// if mid is greater than end i.e. sub-array after this is not in increasing order (contais pivot element)
// search in mid+1 to end.
// Else search in start to mid-1.
if(a[mid] > a[end])
start = mid+1;
else
end = mid -1;
}
mid = (start+end)/2;
}
}
int main()
{
int a[] = {90,100,110,10,20,30,40,50,60,70,80};
int size = sizeof(a)/sizeof(a[0]);
int n;
while(true)
{
cout<<"\nENTER NUMBER : ";
cin>>n;
cout<<"\nFOUND AT : "<<findElement(a,size,n)<<"\n\n";
}
}``````

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

compare mid element with the first and last to decide where is the incorrect order present in the array(1st half r 2nd half) and do it until you will reach a stage where the mid element is known to be in incorrect order(rotated part)

2) After that,do binary search selecting any of the 2halves(in the upper stack like division we did) until you find the element.

Example:
Suppose, in 7 8 9 0 1 2 3 4 5 6
->mid element is 2
2<7 => first half is incorrect
So, the mid element is in the rotated part of array

->Now,compare x with last element in the rotated part. Supposing 9 here,
9>6 => 9 is in the 1st half of the array
and then by using binary search in the 1st part of array,we can search for a given element in O(log n) time complexity

Correct me if i an wrong.. :)

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

int[] array = { 5, 6, 10, 11, 12, 1, 2, 3 };
int lengthOfArray = array.length;
int begIndex = 0;
int endIndex = 0;
int searchElement = 10;//element need to be search

if (array[0] < array[lengthOfArray / 2]) {
if (searchElement <= array[lengthOfArray / 2]
&& searchElement >= array[0]) {
begIndex = 0;
endIndex = (lengthOfArray / 2) - 1;

} else if (searchElement <= array[0]) {
begIndex = lengthOfArray / 2;
endIndex = lengthOfArray - 1;
}
}

else {
if (searchElement >= array[lengthOfArray / 2]
&& searchElement <= array[0]) {
begIndex = (lengthOfArray / 2);
endIndex = lengthOfArray - 1;

} else if (searchElement >= array[lengthOfArray / 2]
&& searchElement >= array[0]) {
begIndex = 0;
endIndex = (lengthOfArray / 2);
}

}

for (int i = begIndex; i <= endIndex; i++) {
if (array[i] == searchElement) {

System.out.println(searchElement + " is at location :"
+ (i + 1));
break;
}
}

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

#include<iostream>
#include<cmath>
#include<cstdlib>
using namespace std;
boolean search(int a[],int left,int right,int value)
{ int mid=(left+right)/2;
boolean t,m,p,q;
if(a[mid]==value)
{
return true;
}
else if(left<=right)
{ if(a[mid]>a[0])
{ if(value>a[0])
t=search(a,left,mid,value);
else
m= search(a,mid+1,right,value);
}
else if(a[mid]<a[0])
{ if(value<a[0])
p= search(a,mid+1,right,value);
else
q=search(a,left,mid,value);
}
}
else
return false;

return p||q||t||m?true:false

}
int main()
{ int a[]={ 10,12,15,17,2,4,5,6,8,9};
boolean x= search(a,0,9,3);
if(x)
cout<<"present\n";
else
cout<<"not present \n";
system("pause");
return 0;
}

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

Logic:
1. Array is given with n elements. and we have to search an element say x.
2. take the mid element.
Its for sure, one half of array will be in correct order.
find half array with correct order. You can find it by comparing mid element with either
first element or last element.
3. If x lies in half array with correct order, do the binary search on this half.
Otherwise, repeat step 2 and 3.
for ex: 7 8 9 0 1 2 3 4 5 6 and suppose we have to search element say 9.
here the correct half order is 2 3 4 5 6 and 9 is not part of it.
so again we will process first half array 7 8 9 0 1
here correct half order is 7 8 9 and element 9 lies in this.
so we will perform binary search on this.

This complete process will take log(n) time.

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

I cannot figure out how can we determine the correct half order by just comparing it with first and last element of that half.

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

@nitin: (We will say elements are in correct order if they are in increasing order from left to right )
Now
->Take the middlemost element
->compare it with first element
if first element is less that the middle element ,first half is in
correct order

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

So sry
Continue:
if middle element is less than last element,then this part is in correct order.
Let's take an example:
5 6 7 8 9 1 2
Here middle element is 8.As 5<8,clearly first half is in correct order.
Please let me know in case of you have any counter example for this explaination

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

Would u say that 5 10 12 8 9 10 12 where mid element 8 is greater than 5

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

This seems to be the correct solution

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

nknicdhi

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.