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.

- Anonymous October 31, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- msramachandran November 01, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- timmy November 02, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Nani November 03, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- Nani November 03, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Piper November 07, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- sreekanth May 08, 2014 | Flag
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

- node* December 20, 2011 | Flag Reply
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.

- Guddu Sharma May 05, 2012 | Flag Reply
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[0];
    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);
    }
}

- h4x0r May 31, 2012 | Flag Reply
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;
}

- Parth January 18, 2014 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More