## Linkedin Interview Question for Software Engineer / Developers

• 3

Country: United States
Interview Type: Phone Interview

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

This is the binary search in the rotated sorted array.

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

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

I believe this should work.

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

straight forward solution

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

Doesn't work with this input
int[] intAr = {1,2,3,4,5,6,7,8,9,10};
int[] tmpArray = {6,7,8,9,10,1,2,3,4,5};

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

Sorry my mistake:
gives wrong result when
int middle = left + ((right-left)/2);
is replace with int middle = right + left /2;

What is the reason for this weird behaviour.

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

This code will not work if your middle element is the pivot. You may need to add a condition for that..

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

this will not work for several scenarios if you can have duplicate numbers in the array. Like 1 5 1 1 1 -> try search for 5.

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

This is a modification of binary search, so time complexity is o(logn).

``````package com.problems;

public class FindElementInRotatedSorted
{
public static void main(String[] args)
{
test();
}

private static void test()
{
int[] a = { 5, 6, 7, 8, 9, 1, 2, 3 };
int key = 2;

System.out.println(key + ": " + findElementInRotatedSorted(a, 0, a.length - 1, key));

key = 9;
System.out.println(key + ": " + findElementInRotatedSorted(a, 0, a.length - 1, key));

key = 6;
System.out.println(key + ": " + findElementInRotatedSorted(a, 0, a.length - 1, key));

key = 10;
System.out.println(key + ": " + findElementInRotatedSorted(a, 0, a.length - 1, key));

key = 4;
System.out.println(key + ": " + findElementInRotatedSorted(a, 0, a.length - 1, key));

}

public static int findElementInRotatedSorted(int[] a, int start, int end, int key)
{
if (end < start)
{
return -1;
}

int middle = (start + end) / 2;
if (a[middle] == key)
{
return middle;
}

if (a[start] <= a[middle])
{
if (key < a[middle] && key >= a[start])
{
return findElementInRotatedSorted(a, start, middle - 1, key);
}
else
{
return findElementInRotatedSorted(a, middle + 1, end, key);
}
}
else
{
if (a[middle] < key && key <= a[end])
{
return findElementInRotatedSorted(a, middle + 1, end, key);
}
else
{
return findElementInRotatedSorted(a, start, middle - 1, key);
}
}
}
}``````

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

``````public class ModifiedBinarySearch {
/**
* @param args
*/

public static void main(String[] args) {
// TODO Auto-generated method stub
try{
int array[]={5,6,7,8,9,1,2,3};
//
int left=0;
int right=array.length-1;
int mid=(left+right)/2;
int element=1;
while(left<=right){
mid=(left+right)/2;
System.out.println("Mid is "+mid);
if(array[mid]==element){
System.out.println("Element found at "+mid);
break;
}
else if(element<array[mid]){
if(element<array[left]){
left=mid+1;
}
else{
right=mid-1;
}
}
else if(element>array[mid]){
if(element>array[right]){
right=mid-1;
}
else{
left=mid+1;
}
}

}

}catch(Exception E){

}
}

}``````

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

It appears that you are working with a reversed list, not a rotated list. It's not clear that you read the problem correctly.

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

Sorry, my test case put might be wrong but its works fine!!! Have you tested my code..?

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

Try finding 2 in 10, 2, 4, 6, 8. I think it breaks your algorithm, but there's an easy way to prove me wrong. :)

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

Solving this is O(N) time is trivial, so the challenge is to solve it in sub-linear time. If the interviewer tells you where the smallest element in the list is, then you can do a binary search with the known rotation offset. If you don't know where the smallest element is, then the challenge is to find the smallest element in the list.

To find the smallest element in a rotated sorted list, break the lists in half. If low <= mid and mid <= low, then the smallest element is the first element, and you're done. If low > mid, then the smallest element must be in the first half of the list, so recurse on the first half of the list. If mid > high, then the smallest element must be in the second half of the list, so recurse on that.

The key insight here is that when you break a rotated sorted list in half, only one half of the list will have the smallest element, and the other half of the list will be in sequence.

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

First list: Use a regular binary search algorithm
Second list: Similarly use the regular binary search algorithm except when accessing the array, translate the index. In this example, rotatedIndex = (index + rotateAmount) % sizeOfArray. Example finding rotatedIndex of old index 5 = (5 + 4) % 7 = 2. Note, both the old and new array at index 5 and 2 contains element "7".

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

If you aren't told rotateAmount in advance, how do you determine it in non-linear time?

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

lets say n is the element to be searched.

using int binarySearch(a[], n) --> you get the index for n in array a
now use the same binarysearch to find binarySearch(a[] , b[0]);

firstindex - second index
or first index+ secondindex
depending on location whether right or left of the middle elemen.
Now all you need is to find modulo size for the binary search to get the rotation factor..

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

This Python solution assumes two challenges. First, we have to do it in O(logN) time. Second, we aren't told in advance how many positions the array was rotated.

``````def test():
# Assume we have a list that is sorted, except that is
# rotated by an unknown offset.  First, we build a helper
# function to determine the position of the smallest
# element in the list (aka the rotation offset).
assert 0 == pos_smallest_element([0, 0, 0])
assert 0 == pos_smallest_element([0, 1, 2])
assert 1 == pos_smallest_element([2, 0, 1])
assert 2 == pos_smallest_element([1, 2, 0])
assert 3 == pos_smallest_element([4, 5, 6, 0, 1, 2, 3])
# Once we know the smallest element, it's pretty trivial
# to implement search in terms of a generic binary search.
test_lst = [10, 2, 4, 6, 8]
assert 0 == search(10, test_lst)
assert 1 == search(2, test_lst)
assert 2 == search(4, test_lst)
assert 3 == search(6, test_lst)
assert 4 == search(8, test_lst)
assert None == search(0, test_lst)
assert None == search(7, test_lst)
assert None == search(11, test_lst)

def bsearch(val, lowest, highest, get):
# A generic binary search uses a get() function, so
# that we're not coupled to the storage scheme.  We
# just need a guarantee that get(a) <= get(b) when a <= b.
def f(low, high):
if low > high:
return None
mid = (low+high) / 2
mid_val = get(mid)
if val == mid_val:
return mid
if val < mid_val:
return f(low, mid-1)
else:
return f(mid+1, high)
return f(lowest, highest)

def search(val, lst):
offset = pos_smallest_element(lst)
def actual_pos(i):
return (i+offset) % len(lst)
def get(i):
return lst[actual_pos(i)]
answer = bsearch(val, 0, len(lst)-1, get)
return None

def pos_smallest_element(lst):
def pos(low, high):
if low == high:
return low
if low + 1 == high:
if lst[low] <= lst[high]:
return low
else:
return high
mid = (low + high) / 2
if lst[low] <= lst[mid] <= lst[high]:
return low
if lst[low] <= lst[mid]:
return pos(mid, high)
else:
return pos(low, mid)

return pos(0, len(lst) - 1)

test()``````

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

1) Does rotation can happen at any place ?
I am providing my algorithm by assuming the rotation is happening at the middle of the array.

a) Get the size of the array or number of elements.. n
b) Assume i =0 and
if ( n%2 ==0)
j = n/2;
else
j = n/2 +1;
c) check the key value as follows.
if (key <= a[j-1]) {
if(key == a[i++] && i < j)
return i;
else
return -1;
}

if (key >=a[j]) {
if (key == a[ j++] && j <n)
return j;
else
return -1;
}

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

1. Use modified binary search to find the rotating point.
2. Apply regular binary search on each of the two segments separated by the rotating point.

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

How about the following O(log n) solution:

``````public static int find_element(int[] array, int low, int up, int key) {
if(up==low) {
if(array[low] == key)
return low;
else
return -1;
}
int m = low+ (up-low)/2;
if(array[low] < array[mid] && (array[low] <= key) && array[mid] >= key)) {
// array[low..mid] is sorted and the element is in there
return find_element(array, low, mid, key);
}
if(array[low] > array[mid] && ((array[low] >= key) || array[mid] <= key)) {
// array[low..mid] is not sorted; however it is a rotated
// sorted array; also the remaining a[mid..up] contains
// element smaller than key or large than key
return find_element(array, low, mid, key);
}
//otherwise the element is in the second half
return find_element(array, mid+1, up, key);
}``````

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

how does it matter, whether the array is rotated or not, if you have to search in rotated array, just do normal search in array...

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

Here is a slight modification to the binary search.
Checking for a rotated cased then recusing on the other half

``````public static int bSearch(int[] arr, int n, int lo, int hi){
if(arr == null)
throw new NullPointerException();

int mid = (hi + lo)/2;

if(arr[mid] == n) {
return mid;
} else if(n < arr[mid]) {
if(n < arr[hi])
return bSearch(arr, n, mid + 1, hi); //rotated
else
return bSearch(arr, n, lo, mid - 1); //normal
} else {
if(n > arr[hi])
return bSearch(arr, n, lo, mid - 1); //rotated
else
return bSearch(arr, n, mid + 1, hi); //normal
}
}``````

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

Darn, I cannot edit if I post as Anonymous. Sorry. The code is not right..

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

below should be used

``````else if(n < arr[mid]) {
if(n < arr[lo] && n < arr[hi]) {
...
...
}``````

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

I suppose the recursive solution will make it easier to address the scenario where the pivot, low and high are the same and we need both sides of the array.

``````#include <iostream>
#include <vector>

using namespace std;

template <typename T>
int rotated_binary_search(const T &arr, int low, int high, int key) {

while (low <= high) {
// arrvoid overflow, same as mid=(low+high)/2
int mid = low + ((high - low) / 2);
if (arr[mid] == key) return mid;

// the bottom half is sorted
if (arr[low] < arr[mid]) {
if( key < arr[mid] )
return rotated_binary_search(arr, low, mid - 1, key);
else
return rotated_binary_search(arr, mid + 1, high, key);
}
else  if( arr[mid] < arr[high] ) { // the upper half is sorted
if( key <= arr[high] )
return rotated_binary_search(arr, mid + 1, high, key);
else
return rotated_binary_search(arr, low, mid - 1, key);
}
else if ( arr[low] == arr[mid] )
{
if( arr[mid] == arr[high] ) // Can't tell which side to go - have to look at both.
{
int ret = rotated_binary_search(arr, low, mid - 1, key);
if ( ret == -1 )
return rotated_binary_search(arr, mid + 1, high, key);
else
return ret;
}
else
return rotated_binary_search(arr, mid + 1, high, key);
}
}
return -1;
}

int main() {
const int TESTS = 7;
int a[TESTS][9] = {{  1, 3, 4, 5, 1, 1,  1, 1, 1},
{  7, 8, 9, 1, 2, 3,  4, 5, 6},
{  5, 6, 7, 8, 9, 10, 1, 1, 1},
{  1, 3, 4, 5, 6, 7,  8, 9, 10},
{  1, 1, 1, 1, 1, 5,  8, 9, 10},
{  1, 1, 1, 5, 8, 8,  8, 8, 8},
{  1, 3, 4, 4, 5, 6,  7, 1, 1}};

int iFound = -1;
for(int i = 0; i < TESTS; i++ )
{
iFound = rotated_binary_search(&a[i][0], 0, sizeof(a[i])/sizeof(int)-1, 5);
cout << iFound << endl;
}

return 0;
}``````

Output:
3
7
0
3
5
3
4

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

``````public static void main(String... args) {
int[] arr = new int[]{0,0,2,3,3,3,3,4,7,7,9,9};
searchEndpoints(arr, 3);

}

public static void searchEndpoints(int[] arr, int element) {
int index = binSearch(arr, 0, arr.length-1, element);

int left = index;
int right = index;
int rightIndex = index;
int leftIndex = index;

while (left != -1) {
left = binSearch(arr, 0, left-1, element);
if (left != -1) leftIndex = left;
}

while (right != -1) {
right = binSearch(arr, right+1, arr.length-1, element);
if (right != -1) rightIndex = right;
}

System.out.println("Range:" + leftIndex + ", " + rightIndex);
}

public static int binSearch(int[] arr, int i, int j, int element) {
int low = i;
int high = j;

while (high >= low) {
int mid = low + (high - low)/2;
if (arr[mid] == element)
return mid;
if (arr[mid] > element)
high = mid - 1;
else
low = mid + 1;
}

return -1;
}``````

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

Recursive solution

``````int rotated_binary_search(int A[], int start, int end, int key)
{
int middle=(start+end)/2;

if(start==end)
{
if(A[start]==key)
return start;
else
return -1;
}

if(A[start] <= A[middle] )
{
if(A[start]<=key && key<=A[middle])
return	rotated_binary_search(A,start,middle,key);
else
return	rotated_binary_search(A,middle+1,end,key);
}
else
{
if(A[middle]<=key && key<=A[end])
return	rotated_binary_search(A,middle,end,key);
else
return rotated_binary_search(A,start,middle-1,key);
}
}``````

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

Just curious ? Is it a homework Problem ?

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

Find the rotation point first, then choose the binary search bounds based on a value to be found and then just do a binary search.

``````static int? FindElemInRotatedSorted(int[] input, int subject)
{
var rotationStart = 0;
int? nullableInt = null;
while (input[rotationStart] <= input[rotationStart + 1])
rotationStart++;
rotationStart++;
var left = 0;
var right = rotationStart - 1;
if(subject < input[input.Length - 1])
{
left = rotationStart;
right = input.Length - 1;
}
while(left<=right)
{
if(left == right)
{
return input[left] == subject ? input[left] : nullableInt;
}
var mid = left + (right - left)/2;
if (input[mid] == subject)
return input[mid];
if(input[mid]<subject)
{
left = mid + 1;
}
else if(input[mid]>subject)
{
right = mid - 1;
}
}
return null;
}``````

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

If you have to do an O(N) algorithm to find the rotation point, then you might as well just do a straightforward O(N) search as well, since O(N) + O(log N) is O(N).

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

yeah, that's right

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.