Linkedin Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




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

package learn;

public class RotatedBinarySearch {

	int[] a = {4,5,6,7,8,1,2,3};
	int rotation = 5;
	
	public static void main(String[] args) {
		RotatedBinarySearch rt = new RotatedBinarySearch();
		System.out.println(rt.search(6));
		

	}
	
	int search(int val){
		int start = 0+rotation, end = a.length-1+rotation;
		int mid;
		int position = -1;
		while(start<=end){
			mid = getMid(start, end);
			if(getValAt(mid)==val){
				position = mid;
				break;
			}else if(getValAt(mid)>val){
				end = mid - 1;
			}else{
				start = mid +1;
			}
			
		}
		
		return position%8;
	}
	int getValAt(int position){
		return a[position%(a.length)];
	}
	int getMid(int start, int end){
		int mid  = (start+end)%2==0?(start+end)/2:(start+end+1)/2;;
		//mid = (mid+rotation)%(a.length-1);
		return mid;
	}

}

- dev. February 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

From the way the problem is written, I don't believe you know the rotation. I'm thinking this because OP specifically said it was shifted left by an "unknown" number.

Outside of that your implementation looks good.

- Dave July 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 4 vote

We can append same array to original array and apply the binary search and return index % n(original array length)
eg: A = [4 5 6 1 2 3] n = 6
modified array B = [4 5 6 1 2 3 4 5 6 1 2 3]
suppose we want to search for 5. On first iteration we will get the mid = 6 (Assuming 1 based index) Then it will search in right half and recursively it will find 5 at location 8. Return position as 8%6 = 2.

- Chetan February 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't think your example works if we search for the index of 3.

- Bro February 12, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It works.
Bro why do you think it doesn't?
A little work around will make it work.
3 is at location 6, so 6%6 = 0. But 0 is not valid index(Chetan assumed 1 based indexing) so 0==>N and hence the location is 6.

- Piyush Agal February 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The solution looks good but it doesn't work while searching for 1 and 2. Try it...

- Zesta February 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

we don't need to append another copy of the list to apply binarySearch. Look at my code in the answers.

- randomCoder1988 April 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Try this:
public class RotatedSortedArray {

public static void main(String[] args) {
int arr[] = { 4, 5, 6, 7, 8, 9, 10, 0, 1, 2, 3 };
int L = 0, H = arr.length - 1;
int mid = (L + H) / 2;
int key = 10;
while (L <= H) {
mid = (L + (H - L) / 2);
if (arr[mid] == key) {
System.out.println("Found at " + mid);
break;
} else {// bottom half is sorted
if (arr[L] < arr[mid]) {
if (key < arr[mid])
H = mid - 1;
else
L = mid + 1;
} else if (arr[H] > arr[mid]) {
if (key > arr[mid])
L = mid + 1;
else
H = mid - 1;
}
}

}
}
}

- Zesta February 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

all arithmetic of indices should be (+ offset)%length

- Ahmed Aly February 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int arr[] = {4,5,6,1,2,3};
		System.out.println(modifiedBinarySearch(arr, 5, 0, arr.length -1 ));
			System.out.println(modifiedBinarySearch(arr, 2, 0, arr.length -1 ));
				System.out.println(modifiedBinarySearch(arr, -1, 0, arr.length -1 ));
	}
	
	public static boolean modifiedBinarySearch(int arr[], int val, int low, int high){
		if(low > high)
			return false;
		int mid = (low + high) / 2;
		if(arr[mid] == val)
		return true;
		else{
			if(arr[low]<arr[mid] && val < arr[mid] && val > arr[low]){
				return modifiedBinarySearch(arr, val, low, mid);
			}else{
				return modifiedBinarySearch(arr, val, mid+1, high);
			}
		}
	}
}

- randomCoder1988 April 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this won't work. for example, consider searching for 1 in 6 1 2 3 4 5

- Anonymous April 25, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This won't work. Consider searching for 1 in '6 1 2 3 4 5'.

- anony April 25, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorry I am posting revised version. Previous one is not correct. I removed it but it seems that the post is not removed instantly. Here we go:

#include<stdlib.h>
#include<stdio.h>

int binarySearch(int * arr, int low, int high, int item)
{

	if (low > high) {
		return -1;
	}
	int mid = (low + high) / 2;
	if (item < arr[mid]) {
		binarySearch(arr, low, mid, item);
	}
	else if (item > arr[mid]) {
		binarySearch(arr, mid + 1, high, item);
	}
	else {
		return mid;
	}
}

int binarySearch_modified(int * arr, int low, int high, int length, int item)
{

	if (low > high) {
		return -1;
	}
	int mid = (low + high) / 2;

	if (item < arr[mid % length]) {
		binarySearch_modified(arr, low, mid, length, item);
	}
	else if (item > arr[mid % length]) {
		binarySearch_modified(arr, (mid + 1), high, length, item);
	}
	else {
		return mid % length;
	}
}

int main() {
	int arr[6] = { 1, 2, 3, 4, 5, 6 };

	int index = -1;
	index = binarySearch(arr, 0, 5, 3);
	if (index == -1) {
		printf("not found\n");
	}
	else {
		printf("found at index=%d\n", index);
	}

	int arr_shifted[6] = { 3, 4, 5, 6, 1, 2};
	int shiftedBy = 4;
	index = binarySearch_modified(arr_shifted, 0+shiftedBy, 5+shiftedBy, 6, 1);
	if (index == -1) {
		printf("not found\n");
	}
	else {
		printf("found at index=%d\n", index);
	}

}

- snugkim June 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

elements = [16,17,18,19,20,10,11,12,13]




def binarySearch(val,low,high):
	print "Value = "+str(val)+"low = "+str(low)+"high = "+str(high)

	if low > high :
		return -1

	mid = ( low+high ) / 2

	print "mid = "+str(mid)+"------------------"
 
	if elements[mid] == val :
		return mid


	if elements[low]  <= elements[mid] :
		if  elements[low]  <= val <= elements[mid] :
			return binarySearch(val,low,mid-1)
		else : 
			return binarySearch(val,mid+1,high)	    		
	elif elements[mid] <= elements[high] :
		if elements[mid] <= val <= elements[high] :
			return binarySearch(val,mid+1,high)
		else : 
			return binarySearch(val,low,mid-1)
	return -1
		
print str(binarySearch(13,0,len(elements)-1))

- anonymous June 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

elements = [16,17,18,19,20,10,11,12,13]




def binarySearch(val,low,high):
	print "Value = "+str(val)+"low = "+str(low)+"high = "+str(high)

	if low > high :
		return -1

	mid = ( low+high ) / 2

	print "mid = "+str(mid)+"------------------"
 
	if elements[mid] == val :
		return mid


	if elements[low]  <= elements[mid] :
		if  elements[low]  <= val <= elements[mid] :
			return binarySearch(val,low,mid-1)
		else : 
			return binarySearch(val,mid+1,high)	    		
	elif elements[mid] <= elements[high] :
		if elements[mid] <= val <= elements[high] :
			return binarySearch(val,mid+1,high)
		else : 
			return binarySearch(val,low,mid-1)
	return -1
		
print str(binarySearch(13,0,len(elements)-1))

- anonymous June 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In regular binary search we always go to the left sub array if pivot is greater than search element otherwise to the right sub array.

For rotated binary search, the idea is to check in which sub-array we need to continue the binary search based on certain boundary value checks. The below binary search works for both regular
and rotated arrays.

public int rotatedBinarySearch(int [] arr, int lowIndex, int highIndex, int toSearch) { 
  int m = (highIndex + lowIndex) / 2;

  if (arr[m] == toSearch) {
    return m;
  }

  // Guard against values not in array
  if (highIndex - lowIndex == 0) {
    return Integer.MIN_VALUE;
  }

  if (arr[lowIndex] <= arr[m]) {
    if (arr[lowIndex] <= toSearch && toSearch <= arr[m]) {
      return search(arr, lowIndex, m - 1, toSearch);
    } else {
      return search(arr, m + 1, highIndex, toSearch);
    }
  } 

  if (arr[m] <= arr[highIndex]) {
    if (arr[m] <= toSearch && toSearch <= arr[highIndex]) {
      return search(arr, m + 1, highIndex, toSearch);
    } else {
      return search(arr, lowIndex, m - 1, toSearch);
    }
  }
  return Integer.MIN_VALUE;
}

java> rotatedBinarySearch(new int [] {7, 9, 10, 11, 1, 3, 5}, 0, 6, 4);
java.lang.Integer res48 = -2147483648
java> rotatedBinarySearch(new int [] {7, 9, 10, 11, 1, 3, 5}, 0, 6, 5);
java.lang.Integer res49 = 6
java> rotatedBinarySearch(new int [] {7, 9, 10, 11, 1, 3, 5}, 0, 6, 3);
java.lang.Integer res50 = 5
java> rotatedBinarySearch(new int [] {7, 9, 10, 11, 1, 3, 5}, 0, 6, 7);
java.lang.Integer res51 = 0
java> rotatedBinarySearch(new int [] {7, 9, 10, 11, 1, 3, 5}, 0, 6, 9);
java.lang.Integer res52 = 1
java> rotatedBinarySearch(new int [] {7, 9, 10, 11, 1, 3, 5}, 0, 6, 77);
java.lang.Integer res53 = -2147483648
java> rotatedBinarySearch(new int [] {7, 9, 10, 11, 1, 3, 5}, 0, 6, 4);
java.lang.Integer res54 = -2147483648
java> rotatedBinarySearch(new int [] {7, 9, 10, 11, 1, 3, 5}, 0, 6, 2);
java.lang.Integer res55 = -2147483648
java> rotatedBinarySearch(new int [] {7, 9, 10, 11, 1, 3, 5}, 0, 6, 2);
java.lang.Integer res56 = -2147483648

- sunnyday July 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is C++ version of solution

#include <iostream>
using namespace std;

bool find_array(int *input, int s, int e,  int target)
{
  if (s> e)
    return false;

  int half = s+ (e-s)/2;
  if (input[half] == target)
    return true;

  if (input[half] <target)
  {
    if (input[e] >= target)
      s = half+1;
    else
      e = half-1;
  } else {
    if (input[s] <= target)
      e = half -1;
    else
      s = half +1;
  }
  return find_array(input, s, e, target);
}

int main()
{
  int input[6] = { 4,5,6,1,2,3};

  cout << "find 1 = " <<find_array(input, 0, 5, 1)<<endl;
  cout << "find 5 = " << find_array(input, 0, 5, 5)<<endl;
  cout<< " find 2 = " << find_array(input, 0, 5, 2)<<endl;
  cout<< " find 0 = " << find_array(input, 0,5, 0)<<endl;
  return 1;
}

- hankm2004 August 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {
        int[] arr = {2,3,4,5,6,7,8,9,10,11};
        int[] arr1 = {3,4,5,6,7,8,9,10,11,2};
        int arrayRotatedIndex = rotatedIndex(arr1, 0, arr1.length-1);
        int originalArray = findElement(arr, 0, arr.length-1, 4);
        System.out.println(arr[originalArray]);
        System.out.println(arr1[originalArray+arrayRotatedIndex-arr.length]);
    }

    private static int findElement(int[] arr,int low,int high,int value) {
    	int mid = -1;
        while(low <= high) {
            mid = low + (high - low) / 2;
            if(arr[mid] == value) return mid;
            if(arr[mid] > value) {
                high = mid - 1;
            }
            if(arr[mid] < value) {
                low = mid + 1;
            }
        }
        return mid;
    }
    
    public static int rotatedIndex(int[] arr1, int low, int high) {
    	int rotatedIndex = -1;
        while(low <= high) {
            int mid = low + (high - low) / 2;
            if(arr1[mid] > arr1[low] && arr1[mid] > arr1[high]) {
                low = mid;
            }
            else if(arr1[mid] < arr1[low] && arr1[mid] < arr1[high]) {
                high = mid;
            }
            else {
                rotatedIndex = mid + 1;
                break;
            }
        }
        return rotatedIndex;
    }

- Anonymous October 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Code for the binary search

import java.util.Arrays;

/**
 * Created by Sameer on 1/3/2017.
 */
class BinarySearchRotation {

    public static int search(int[] arr, int elem){

        return binSearch(arr, elem, 0, arr.length - 1);
    }

    private static int binSearch(int[] arr, int elem, int start, int end){

        while(start <= end){
            int mid = (start + end) / 2;

            // Found element
            if(arr[mid] == elem){
                return mid;
            }
            else{
                // Check if mid is less than elem
                if(arr[mid] <  elem){
                    
                    if(arr[start] >= arr[end] && elem > arr[end]){
                        end = mid - 1;
                    }
                    else{
                        start = mid + 1;
                    }
                }
                // Go to the left of mid
                else{
                    // Go to right of mid
                    if(elem <= arr[end] && arr[mid] > arr[end]){
                        start = mid + 1;
                    }
                    else{
                        end = mid - 1;
                    }
                }
            }
        }

        // Return -1 if element is not found
        return -1;
    }
}

Tests:

import org.junit.Test;

import static org.junit.Assert.*;

/**
 * Created by Sameer on 1/3/2017.
 */
public class BinarySearchRotationTest {

    @Test
    public void search() throws Exception {
        // Test 1
        int[] arr = {1, 3, 4, 5, 6, 8};
        int elem = 6;
        assertEquals("Search failed", 4, BinarySearchRotation.search(arr, elem));

        elem = 5;
        assertEquals("Search failed", 3, BinarySearchRotation.search(arr, elem));

        elem = 4;
        int[] arr1 = {5, 6, 7, 8, 2, 3, 4};
        assertEquals("Search failed", 6, BinarySearchRotation.search(arr1, elem));

        elem = 6;
        int[] arr2 = {6, 7, 1, 2, 3, 4, 5};
        assertEquals("Search failed", 0, BinarySearchRotation.search(arr2, elem));

        elem = 10;
        assertEquals("Search failed", -1, BinarySearchRotation.search(arr2, elem));
    }
}

- Sam January 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Binary Search:

#include <iostream>

using namespace std;

int getIndex(int* array, int val, int start, int end) {
    if (start >= end) {
        if (array[start] == val) return start;
        else return -1;
    }
    
    int mid = (start+end)/2;
    
    if (array[mid] == val) 
        return mid;
    
    if (array[mid] > val) 
        return getIndex(array, val, start, mid);
    
    return getIndex(array, val, mid+1, end);
}


int findNum(int* array, int len, int val) {
    return  getIndex(array, val, 0, len-1);   
}

int main()
{
    int array[] =  {1, 2, 3, 4, 5, 6}; 
   
    int val = 3;
    printf("index of %d = %d\n", val, findNum(array, 6, val));
    val = 1;
    printf("index of %d = %d\n", val, findNum(array, 6, val));
    val = 7;
    printf("index of %d = %d\n", val, findNum(array, 6, val));
    return 0;
}

followup:

#include <iostream>

using namespace std;

int getIndex(int* array, int val, int start, int end) {
    if (start >= end) {
        if (array[start] == val) return start;
        else return -1;
    }
    
    int mid = (start+end)/2;
    
    if (array[mid] == val) 
        return mid;

    if (array[mid] > val) {
        if (array[start] > val)
            return getIndex(array, val, mid+1, end);
        
        return getIndex(array, val, start, mid);
    }
    else {
        if (array[start] > val)
            return getIndex(array, val, start, mid);
        
        return getIndex(array, val, mid+1, end);
    }
    
    return -1;
}


int findNum(int* array, int len, int val) {
    return  getIndex(array, val, 0, len-1);   
}

int main()
{
    int array[] =  {4, 5, 6, 1, 2, 3}; 
   
    int val = 2;
    printf("index of %d = %d\n", val, findNum(array, 6, val));
    val = 6;
    printf("index of %d = %d\n", val, findNum(array, 6, val));
    val = 5;
    printf("index of %d = %d\n", val, findNum(array, 6, val));
    return 0;
}

- pavelkushtia February 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

doesn't work for array = [5 1 3] and val = 3

- mrsurajpoudel.wordpress.com February 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yeah, this doesn't work. I think we need a logn algorithm to find the maximum of the array(the place where the array was broken) and then use that in the search.

- doit February 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this work in log(n) time.
1. Find the shift by doing a binary search on the shifted array (say k index).
2. Now doing a binary search in the two halves of the array depending upon the 'val' in the interval (1,k) and (k+1,n) as both will be sorted only.
Assuming it is rotated only once.

- shreshtha February 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Python solution

def find_rotation(array, start, end):
	if start == end:
		return start
	mid = (start + end) / 2
	if array[mid] < array[mid-1] return mid
	if array[mid] > array[0]:
		return find_rotation(array, mid+1, end)
	else:
		return find_rotation(array, start, mid-1)

- edge February 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

If I were you, I would remove this line:

if array[mid] < array[mid-1] return mid

and in the recursive call, include the mid in the calls.

- Anonymous February 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

First I discover which half is correctly ordered. If the desired value is within the range of this correct half, call the binary search into it. Otherwise, call into the other half. When the binary search comes into a subvector that has a correct ordering, it behaves as the regular binary search.

int f(const std::vector<int> &V, int s, int e, int x)
{
	if (e < s) return -1;
	
	int m = (s+e)/2;
	int mid = V[m];

	if (mid == x) return m;

	if (V[s] <= mid) {
		if (x >= V[s] and x <= mid) {
			return f(V, s, m-1, x);
		}
		return f(V, m+1, e, x);
	}

	if (x >= mid and x <= V[e]) {
		return f(V, m+1, e, x);
	}
	return f(V, s, m-1, x);
}

- Victor February 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This has a runtime of O(N). This problem can be solved in O(logN).
Why O(N), because one has to traverse through the whole array to find the point of rotation.

- as09 May 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

2 binary searches.
1) find the pivot point using binary search using the first element in the rotated array. Key property is that the numbers between the first element and the pivot element is ascending.
2) after finding the pivot point, use binary search on the left or right subarray from the pivot point to find the element you're looking for.

Total running time: O(logn)

- Anonymous February 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Actually this can be reduced to one binary search. Just have to modify the if statement for going left or right of mid to be based also on the first value of the array. This method also uses the fact that the values between the first index and the pivot index are incrementing.

if ((arr[mid] > searchValue && arr[0] > searchValue) || (arr[mid] < searchValue && arr[0] > searchValue )
search right side of mid index
else if ((arr[mid] > searchValue && arr[0] < searchValue) || (arr[mid] < searchValue && arr[0] < searchValue ))
search left side of mid

- Anonymous February 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

bool hasElement (int *Array, int value, int start, int end)
{
if (Array == NULL || start > end || start < 0 || end < 0) return false;
if (start == end && Array[start] != value) return false;
int mid = (start + end) / 2;
if (Array[mid] == value) return true;
bool isSortedLeftSide = false;
bool isSortedRightSide = false;
if (start >= (mid-1) || (start < (mid-1) && Array[start] < Array[mid-1]) )isSortedLeftSide = true;
if ((mid+1) == end || ((mid+1) < end && Array[mid+1] < Array[end])) isSortedRightSide = true;
ASSERT(isSortedLeftSide || isSortedRightSide); //At least one side should be sorted

if (!isSortedRightSide)
{
int lastValue = Array[end];
for (int i = end - 1; i >= mid+1; i--)
{
if ( Array[i] > lastValue )
{
mid = i;
break;
}
}
}
else if (!isSortedLeftSide)
{
int previousValue = Array[mid -1];
for (int i = mid-2; i >= start; i--)
{
if ( Array[i] > previousValue )
{
mid = i;
break;
}
}
}

if (Array[mid] == value) return true;
if (start <= mid-1 && value >= Array[start] && value <= Array[mid-1])
{
return hasElement (Array, value, start, mid-1);
}
else if (mid+1 <= end && value >= Array[mid+1] && value <= Array[end])
{
return hasElement (Array, value, mid+1, end);
}
else
{
return false;
}
}

- Amber S February 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

We can use rotated binary search as below:
public void rotatedBinSearch()
{
int arr[] = { 4, 5, 6, 7, 8, 9, 10, 0, 1, 2, 3 };
int L = 0, H = arr.length - 1;
int mid = (L + H) / 2;
int key = 10;
while (L <= H) {
mid = (L + (H - L) / 2);
if (arr[mid] == key) {
System.out.println("Found at " + mid);
break;
} else {// bottom half is sorted
if (arr[L] < arr[mid]) {
if (key < arr[mid])
H = mid - 1;
else
L = mid + 1;
} else if (arr[H] > arr[mid]) {
if (key > arr[mid])
L = mid + 1;
else
H = mid - 1;
}
}
}
}

- Zesta February 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public class BinarySearch {

    public static int binarySearch(final int[] array, final int value) {
        return binarySearchHelper(array, value, 0, array.length - 1);
    }

    private static int binarySearchHelper(final int[] array,
            final int value, final int left, final int right) {
        if (left > right)
            return -1; // not found

        int mid = (left + right) / 2;

        if (value == array[mid]) {
            return mid;
        } else if (value < array[mid]) {
            return binarySearchHelper(array, value, left, mid - 1);
        } else { // (value > array[mid])
            return binarySearchHelper(array, value, mid + 1, right);
        }
    }

    public static int binarySearchShifted(final int[] array, final int value) {
        return binarySearchShiftedHelper(array, value, 0, array.length - 1);
    }

    private static int binarySearchShiftedHelper(final int[] array,
            final int value, final int left, final int right) {
        if (left > right)
            return -1; // not found

        int mid = (left + right) / 2;

        if (value == array[mid]) {
            return mid;
        } else if ((array[left] <= array[mid] && (array[left] <= value && value < array[mid]))
                || (array[mid] <= array[right] && !(array[mid] < value && value <= array[right]))) {
            return binarySearchShiftedHelper(array, value, left, mid - 1);
        } else {
            return binarySearchShiftedHelper(array, value, mid + 1, right);
        }
    }

    public static void main(String[] args) {
        test(6);
        test(7);
    }

    private static void test(int count) {
        int array[] = new int[count]; // {10, 20, ... 10*COUNT}
        for (int i=0; i<count; i++) {
            array[i] = 10 * (i+1);
        }

        int VALUE_MIN = 8;
        int VALUE_MAX = 10 * count + 2;

        printArray(array);
        for (int value = VALUE_MIN; value <= VALUE_MAX; value++) {
            int index = binarySearch(array, value);
            boolean pass = ((index >= 0 && (value % 10 == 0)) || (index < 0 && (value % 10 != 0)));
            if (!pass) {
                System.out
                        .println("*** FAIL ***"
                                + " value = "
                                + value
                                + ((index >= 0) ? (" index = " + index)
                                        : " Not Found"));
            }
        }
        System.out.println();

        for (int shift = 0; shift < count; shift++) {
            for (int i = 0; i < count; i++) {
                array[i] = 10 * (((shift + i) % count) + 1);
            }

            printArray(array);
            for (int value = VALUE_MIN; value <= VALUE_MAX; value++) {
                int index = binarySearchShifted(array, value);
                boolean pass = ((index >= 0 && (value % 10 == 0)) || (index < 0 && (value % 10 != 0)));
                if (!pass) {
                    System.out.println("*** FAIL ***"
                            + " value = "
                            + value
                            + ((index >= 0) ? (" index = " + index)
                                    : " Not Found"));
                }
            }
            System.out.println();
        }
    }

    private static void printArray(int[] array) {
        System.out.print("array[] = { ");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]);
            System.out.print(" ");
        }
        System.out.println("}");
    }

}

- scgupta February 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public static boolean search(int[] array, int low, int high, int shiftedBy, int lookupElement) {
		if(low>high) return false;
		int mid = (low + high)/2;
		int shiftedIndex = mid - shiftedBy;
		if(shiftedIndex < 0) {
			shiftedIndex = array.length + shiftedIndex;
		}
			
		if(array[shiftedIndex]==lookupElement) return true;
		else if(array[shiftedIndex]<lookupElement) return search(array, mid+1, high, shiftedBy, 	  lookupElement);
		else return search(array, low, mid-1, shiftedBy, lookupElement);
		}

- Anonymous March 17, 2015 | 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