## Flipkart Interview Question for Software Engineer / Developers

Country: India
Interview Type: Phone Interview

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

Just find the index at which the rotation occurred say: X, i.e. 6 7 8 1 2 3 4 5 so X = 3. Now do normal binary search but use following function to manipulate indexes of array in an non rotated sorted array:

``````getNormalIndexes(int ind)
{
return (ind + X) % N;
}``````

So when u set low = 0; high = N, it will return you low = 3 and high = 2 which is exactly the mapping in actual array. Use modified indexes to perform normal binary search.

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

how would you find the point of rotation ?
If its linear search. then it defeats the purpose of binary search.

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

I believe you can deterine the point of rotation using binary search

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

Below is the code to find the point of rotation using binary search

``````private int BinarySearch(int[] a, int start, int end)
{
if(start <= end)
{
int mid = (start + end) / 2;
if(start == end)
return a[mid];
else if(a[mid] > a[mid + 1] && a[mid] > a[mid - 1])
return a[mid];
else if(a[start]>a[mid])
return BinarySearch(a, start, mid - 1);
else
return BinarySearch(a, mid + 1, end);
}
else
return -1;
}``````

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

Above algorithm fails in this case {1,12,10,8,6,4}

Small change: for last else case in if replace "return BinarySearch(a, mid + 1, end) with BinarySearch(a, mid, end)

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

How is {1,12,10,8,6,4} a rotated array?

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

what happens when my array has only two elements?. Will it end up in a seg fault?.

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

{1,12,10,8,6,4} seems to be not a rotated array

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

Here is a binary search approach

``````boolean find(arr,start,finish,data)
{
if(start==finish)
{
if(arr[start]==data)
return true;
return false;
}
if(start==finish-1)
{
if(arr[start]==data || arr[finish]==data)
return true;
return false;
}
else
{
mid=(start+finish)/2;
if(arr[mid]==data)
return true;
if(arr[mid]>arr[start])
{
if(data>=arr[start] && data<arr[mid])
find(arr,start,mid-1,data);
else
find(arr,mid+1,finish,data);
}
else
{
if(data>arr[mid] && data<=arr[finish])
find(arr,mid+1,finish,data);
else
find(arr,start,mid-1,data);
}
}
}``````

Please comment if any corner cases are left.

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

``````int find_offset(int arr[], int start, int end) {
int first = arr;
int mid = (start + end)/2;
if (start == mid) {
return mid;
} else if (arr[mid] < first) {
return find_offset(arr, start, mid);
} else {
return find_offset(arr, mid, end);
}
}``````

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

public static int rotated_binary_search(int A[], int N, int key) {
int L = 0;
int R = N - 1;

while (L <= R) {
// Avoid overflow, same as M=(L+R)/2
int M = L + ((R - L) / 2);
if (A[M] == key) return M;

// the bottom half is sorted
if (A[L] <= A[M]) {
if (A[L] <= key && key < A[M])
R = M - 1;
else
L = M + 1;
}
// the upper half is sorted
else {
if (A[M] < key && key <= A[R])
L = M + 1;
else
R = M - 1;
}
}
return -1;
}

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.