Linkedin Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
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};
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.
This code will not work if your middle element is the pivot. You may need to add a condition for that..
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);
}
}
}
}
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){
}
}
}
It appears that you are working with a reversed list, not a rotated list. It's not clear that you read the problem correctly.
Sorry, my test case put might be wrong but its works fine!!! Have you tested my code..?
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.
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".
If you aren't told rotateAmount in advance, how do you determine it in non-linear time?
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.
.. to get answer
Now all you need is to find modulo size for the binary search to get the rotation factor..
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)
if answer is None:
return None
return actual_pos(answer)
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()
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;
}
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);
}
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
}
}
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
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;
}
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);
}
}
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;
}
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).
This is the binary search in the rotated sorted array.
- Venki February 22, 2013int 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; }