## Facebook Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

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

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

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

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)

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

while(A[L]<A[R]) is wrong, it should be while(L<=R)

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

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)

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

{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

}

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

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

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

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

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

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

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

``````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
of 0 vote

``````/**
*
* @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;

}``````

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

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

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

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

}

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

Binary Search

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.