## Linkedin Interview Question for Software Engineer / Developers

• 3

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

}``````

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.

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.

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

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

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

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.

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

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

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

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

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

}
}
}

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

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

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

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

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

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

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

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) {
}
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) {
}
else {
printf("found at index=%d\n", index);
}

}``````

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))``````

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))``````

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

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

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

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

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

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

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

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

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

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.

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

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.

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)``````

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

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.

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

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

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.

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)

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

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

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

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

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)

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)

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)
}
}
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)
}
}
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("}");
}

}``````

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

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.