Facebook Interview Question Software Engineer / Developers
0of 0 votesSearch in a sorted rotated array.
Country: United States
Interview Type: Phone Interview
def rotated_array(arr, key):
N = len(arr)
L = 0
R = N-1
while (A[L] < A[R]):
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
print rotated_array([4,5,6,7,8,1,2,3], 5)
def rotated_array(arr, key):
N = len(arr)
L = 0
R = N-1
while (A[L] < A[R]):
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
print rotated_array([4,5,6,7,8,1,2,3], 5)
{def rotated_array(arr, key):
N = len(arr)
L = 0
R = N-1
while (A[L] < A[R]):
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
}
public static int searchRotArr(int[] arr, int val){
int lo = 0, hi = arr.length -1, mid = -1;
while(lo < hi){
mid = (lo + hi) >> 1;
if(val == arr[mid]){
return mid;
}
if(val > arr[mid]){
if(val <= arr[hi]){
lo = mid + 1
}
else{
hi = mid-1;
}
}
else{
if(val <= arr[lo]){
lo = mid + 1;
}
else{
hi = mid -1;
}
}
}
return mid;
}
public static int search(int[] x, int left, int right, int n) {
int middle = (left + right)/2;
if (n == x[middle]) {
return middle;
}
if (n < x[middle]) {
if (n == x[left]) {
return left;
}
if (n < x[left]) {
return search(x, middle+1, right, n);
}
else {
return search(x, left, middle-1, n);
}
}
else {
if (n == x[right]) {
return right;
}
if (n < x[right]) {
return search(x, middle+1, right, n);
}
else {
return search(x, left, middle-1, n);
}
}
}
Modified Binary Search
#include <cstdlib>
#include <stdio.h>
//if start pos is unknown
int binary_search(int * array, int length, int target)
{
//could not find the value until the found spos, do binary search for array from spos to end of the array
int left = 0;
int right = length -1;
int half = -1;
while (left <= right)
{
half = left + (right- left)/2;
if (array[half] == target)
return half;
if (array[left] < array[half])
{
if (array[half] > target && array[left] <= target)
right = half - 1;
else
left = half + 1;
} else {
if (array[half] < target && target <= array[right])
left = half + 1;
else
right = half -1;
}
}
return -1;
}
int main(int argc, char *argv[])
{
int array[7] = {5,6,7,9,1,2,3};
int target = atoi(argv[1]);
printf("target = %d\n", target);
int result = binary_search(array,7, target);
printf("found = %d\n", result);
return 1;
}
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;
}
/**
*
* @param array
* @param K -- num of positions shifted
* @return - index of the element in original array
*/
public static int binarySearchShiftedArray(int array[], int K, int beg, int end, int elem){
int mid = beg + (end-beg)/2 ;
int mid1 = ( mid + K) % (array.length ); //shifted mid
if(elem < array[mid1]){
return binarySearchShiftedArray(array, K, beg, mid-1, elem);
}
else if(elem > array[mid1]){
return binarySearchShiftedArray(array, K, mid+1, end, elem);
}
else return mid1;
}
def rotated_array(A, key, L, R):
if (L>R or R<L):
return -1
M = L + ((R - L) / 2)
if A[M] == key:
return M
#the bottom half is sorted
if (A[L] <= A[M]):
if key < A[M] and key >= A[L]:
return rotated_array(A, key, L, M-1)
else:
return rotated_array(A, key, M+1, R)
#the upper half is sorted
else:
if A[M] < key and key <= A[R]:
return rotated_array(A, key, M+1, R)
else:
return rotated_array(A, key, L, M-1)
list = [5,6,7,8,9,2,3,4]
print rotated_array(list,1,0,7)
int findPivot(int[] arr, int min, int max) {
if (arr.length == 0) return -1;
if (arr.length == 1) return 0;
int mid = (max - min) / 2 + min;
if (arr[mid] > arr[mid + 1]) {
return mid;
}
if (arr[min] < arr[mid]) {
return findPivot(arr, mid + 1, max);
}
return findPivot(arr, min, mid);
}
int binarySearch(int[] arr, int num, int min, int max) {
if (arr.length == 0) return -1;
if (arr.length == 1) return arr[0];
int mid = (max - min) / 2 + min;
if (arr[mid] == num) return mid;
if (arr[mid] < num) return binarySearch(arr, num, mid + 1, max);
return binarySearch(arr, num, min, mid);
}
int findInRotArr(int[] a, int num) {
int pivot = findPivot(a, 0, a.length);
if (a[pivot] == num) return pivot;
if (a[pivot] > num && a[a.length - 1] > num) return binarySearch(a, num,pivot + 1, a.length);
if (a[pivot] > num && a[a.length - 1] < num) return binarySearch(a, num, 0, pivot);
return binarySearch(a, num, pivot + 1, a.length);
}
- Fatma Zaman May 22, 2015def rotated_array(arr, key): N = len(arr) L = 0 R = N-1 while (A[L] < A[R]): 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