## Facebook Interview Question for Interns

• 0

Country: United States
Interview Type: Phone Interview

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

Actually, you can do a little simpler than that. You don't actually need the pivot index. We just need to compare the mid element with rightmost and leftmost elements. If mid element is larger than leftmost element, bottom half of the array is properly sorted. In this case, we have a plain binary search (if element we are searching for is between leftmost and middle element, look at the lower half of the array; otherwise look at the upper half of the array).
If mid element is smaller than leftmost element, upper half of the array is sorted. Accordingly, we look if the given element is at the upper of lower part.

``````int search(int A[], int N, int key) {
int left = 0;
int right = N - 1;

while (left <= right) {

int mid = left + ((right-left) / 2);
if (A[mid] == key) return mid;

// the bottom half is sorted
if (A[left] <= A[mid]) {
if (A[left] <= key && key < A[mid])
right = mid -1;
else
left = mid+1;
}
// the upper half is sorted
else {
if (A[mid] < key && key <= A[right])
left = mid+1;
else
right = mid-1;
}
}
return -1;
}``````

The method won't work if there are duplicates in the array

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

Doing the ternary then binary way is :
- Less likely to cause error in whiteboard coding as it is less "tricky"
- Has the same big-O

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

this will not work if the rotation is by n/2

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

I would use Ternary Search to find the pivot and then a normal Binary Search, knowing the pivot. The time complexity is O(log n) if the values are distinct

``````int FindPivot(int v[], int size) { // ternary search to find the pivot
int left = 0, right = size-1;
while (left+1 < right) {
int c1 = (left*2 + right) / 3;
int c2 = (left + right*2) / 3;
if (v[c1] < v[c2])
right = c2;
else
left = c1;
}
if (left < right)
return v[left] < v[right] ? left : right;
return left;
}
int SearchRot(int v[], int size, int number) {
int left = 0, right = size-1, mid;
int pivot = FindPivot(v, size);
while (left <= right) {
mid = (left + right) / 2;
int pos = (mid + pivot) % size;
if (v[pos] == number)
return pos;
else if (v[pos] < number)
left = mid+1;
else
right = mid-1;
}
return -1;
}``````

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

Simple binary search, with slight change will work.
See the code below.

``````// Aim is to find a element k in a rotated sorted array.

#include <iostream>

using namespace std;

int findKElement(int find, int array[], int length)
{
int start = array[0];
int end = array[length -1];
int mid = array[length/2];
int left = 0;
int right = length - 1;

while (left <= right) {
int middle = left + (right-left)/2;
if (array[middle] == find) return middle;

if (array[left] <= array[middle]) {
if (find >= array[left] && find < array[middle])
right = middle - 1;
else
left = middle + 1;
}
else {
if (find > array[middle] && find <= array[right])
left = middle + 1;
else
right = middle - 1;
}
}
return -1;
}

int main ()
{
int length;
cin >> length;
int array[length];
int toFind;
cin >> toFind;
for (int i = 0; i < length; i++)
cin >> array[i];
cout << "index is " << findKElement(toFind, array, length) << endl;
return 0;
}``````

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

Ignore the redundant 3 variables at the top.

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

Here is the scala solution:

``````def pivotIndex(input: Array[Int]):Int={
val pairs=input zip input.tail;
val pivotPosition=pairs.indexWhere((x: Pair[Int, Int])=>x._1>x._2);
val validInput=(pivotPosition>==0) && (pivotPosition==pairs.lastIndexWhere((x: Pair[Int, Int])=>x._1>x._2);
if(validInput) pivotPosition+1 else -1
}``````

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

Solution (considers duplicates as well):

One half of the array is normally ordered. It's either the left or the right. Find the normally ordered half and perform binary search on that if X is inside it. Otherwise, search the other half.

Complexity: O(logN) without duplicates, O(n) with all elements duplicates (because we need to search both halves)

CODE:

``````public int search(int[] array, int n){
return search(array, n, 0, array[array.length-1]);
}

private int search(int[] array, int n, int left, int right){

if (left>right)
return -1;
int mid = (left+right) / 2;

if (array[mid] == n)
return mid;

//find the normally ordered array and search in it
if (array[left] < array[mid])
{
//left is normally ordered
if (array[left]<=n && n<=array[mid])
return search(array, n, left, mid-1);    //search  left
else
return search(array, n, mid+1, right); //search right
}
else if (array[mid]<array[right]){
//right is normally ordered
if (array[mid] <= n && n <= array[right])
return search(array, n, mid+1, right);
else
return search (array, n, left, mid-1);
}
else if (array[left]==array[mid]){    //there are duplicates
if (array[mid]!=array[right])
return search(array, n, mid+1, right);
else
{
int l = search(array, n, left, mid-1);
if (l==-1)
return search(array, n, mid+1, right);
return l;
}
}
return -1;

}``````

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

Good solution

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

``````package com.test;

public class Test {

/**
* @param args
*/
public static void main(String[] args) {

int[] array = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int pivot = -1;
for (int i = 0; i < array.length - 1; i++) {
if (array[i] < array[i + 1]) {
continue;
} else {
pivot = i;
}
}

System.out.println("pivot: " + pivot);
}

}``````

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

``````static void binarySearchRotated(int [] A, int i, int l, int x){ // i=0; l=A.length-1;
if(i>l){
return;
}
int mid=(i+l)/2;
if(x==A[mid]){
System.out.print(mid);
return;
} else if(A[mid]>=A[l]){
if(x>=A[i] && x<A[mid]){
binarySearchRotated(A, i, mid-1, x);
} else binarySearchRotated(A, mid+1, l, x);
} else if(A[mid]<=A[l]){
if(x>A[mid] && x<=A[l]){
binarySearchRotated(A, mid+1, l, x);
}
else
binarySearchRotated(A, i, mid-1, x);
}
}``````

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

Can someone please comment on this code? It seems to work, but I would like to know how efficient it is...

``````public static int findIndexK(int k, int[] a) {
int index = -1;
int fromLeft = tryFromLeft(k, a);
if (fromLeft == -1)
index = tryFromRight(k, a);
else
index = fromLeft;
return index;
}

public static int tryFromLeft(int k, int[] a) {
int res = -1;
for (int i = 0; i < a.length; i++){
if (a[i] > k) break;
if (a[i]==k) return i;
}
return res;
}

public static int tryFromRight(int k, int[] a) {
int res = -1;
for (int i = a.length - 1; i >= 0; i--){
if (a[i] < k) break;
if (a[i] == k) return i;
}
return res;
}

public static void main(String[] args) {
int[] a = { 4, 5, 6, 7, 8, 9, 1, 2, 3 };
int k = 0;
System.out.println(findIndexK(k, a));``````

}

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

2 linear passes worst case. Which is O(n).

But if you coded it correctly, either
1) Try from left will give you an index found. OR
2) Both try from left and try from right will fail and return -1

In other words, try from right would be redundant.

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

Rename tryfromleft to findindex and delete the rest (the original findindex and the tryfromright).

That's 1 linear pass., still O(n).

Then try binary searching to get it down to lg n.

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

``````// 1. L < M < R (1,2,3) - regular QuickSort
// 2. L < M > R (2,5,1)
// 3. L > M < R (5,1,3)
// 4. L > M > R (3,2,1) - reverse QuickSort
static int FindInRotatedArray(int[] a, int k)
{
int l = 0;
int r = a.Length - 1;
while (l < r)
{
int m = l + (r - l) / 2;

if (k == a[m]) return m;

if (a[l] <= a[m] && a[m] <= a[r]) // 1
{
if (a[m] > k) r = m - 1;
else l = m + 1;
}
else if (a[l] <= a[m] && a[m] >= a[r]) // 2
{
if (a[l] <= k && k < a[m]) r = m - 1;
else l = m + 1;
}
else if (a[l] >= a[m] && a[m] <= a[r]) // 3
{
if (a[m] < k && k <= a[r]) l = m + 1;
else r = m - 1;
}
else // 4
{
if (a[m] > k) l = m + 1;
else r = m - 1;
}
}

return a[l] == k ? l : -1;
}``````

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

And then we can simplify the above implementation to:

``````static int FindInRotatedArray2(int[] a, int k)
{
int l = 0;
int r = a.Length - 1;
while (l <= r)
{
int m = l + (r - l) / 2;

if (k == a[m]) return m;

if (a[l] <= a[m]) // 1, 2
{
if (a[l] <= k && k < a[m]) r = m - 1;
else l = m + 1;
}
else // 3, 4
{
if (a[m] < k && k <= a[r]) l = m + 1;
else r = m - 1;
}
}

return -1;
}``````

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

Time Complexity: O(n)

``````static void Main(string[] args)
{

int[] arr = { 4, 5, 6, 7, 8, 9, 1, 2, 3 };
Console.WriteLine(PivotIndex(arr));

}
static int PivotIndex(int[] arr) {

int startIndex = 0;
int endIndex = arr.Length - 1;

for (int i = 0; i < arr.Length - 1; i++)
//while()
{
if (arr[startIndex] > arr[endIndex])
{
startIndex++;
endIndex--;
}
else {
return endIndex+1;
}

}

return -1;
}``````

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

``````public class Tab {

public static int res (int K, int g, int d, int[] tab){
if (tab.length==0){
return -1;
}
if (g==d){
if (K==tab[g]){
return g;
}
else{
return (-1);
}
}
else{
int N = (g+d)/2;
if (tab[N]==K){
return N;
}
else{
if (tab[N]<tab[g]){
if (K<=tab[d]){
return res(K,N,d,tab);
}
else{
return res (K,g,N,tab);
}
}
else{
if (K>=tab[g]){
return res(K,g,N,tab);
}
else{
return res (K,N,d,tab);
}
}
}
}
}

public static void main (String[] args){
int[] tab = {4,5,6,7,8,9,1,2,3};
System.out.println(res(1,0,tab.length,tab));
}
}``````

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

public class kParlindrome {
public boolean check(String s, int threshold)
{
return checkKparlindrome(s, 0, s.length()-1, 0, threshold);
}
public boolean checkKparlindrome(String s, int bpointer, int epointer, int misCnt, int threshold)
{
if(bpointer< 0 || epointer>=s.length())
return false;
if(epointer <= bpointer)
return true;
if(misCnt > threshold)
{
return false;
}
if(s.charAt(bpointer) == s.charAt(epointer))
{
boolean res = checkKparlindrome(s, bpointer+1, epointer-1, misCnt+2,threshold);
if (res)
return res;
else
return false;
}
else
{
//move bpointer
boolean res = checkKparlindrome(s, bpointer+1, epointer, misCnt+1,threshold);
if(res)
return true;
//move epointer
res = checkKparlindrome(s, bpointer, epointer-1, misCnt+1,threshold);
if(res)
return true;
//move
res = checkKparlindrome(s, bpointer+1, epointer-1, misCnt+2,threshold);
if(res)
return true;
return false;
}
}
public static void main(String[] args)
{
kParlindrome kp = new kParlindrome();
System.out.println(kp.check("bacdedafdeafdakljlke",3));
}
}

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

This code will be ok.

``````int Search(std::vector<int> & v, int k) {
int b = 0;
int e = v.size() - 1;
while (b <= e) {
int mid = b + (e - b) / 2;
if (v[mid] == k) return mid;
else if (v[mid] > v[e]) {
if (k > v[e] && k < v[mid]) e = mid - 1;
else b = mid + 1;
} else if (v[mid] < v[e]) {
if (t > v[mid] && t <= v[e]) b = mid + 1;
else e = mid - 1;
} else {
e--;
}
}
return -1;
}``````

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

``````public static int midIndex(int[] arr, int k)
{
return minIndex(arr, k, 0, arr.length);
}

private static int minIndex(int[] arr, int k, int l, int r)
{
while(l < r)
{
int mid = (r - l) / 2;
mid += l;

if(arr[mid] == k)
return mid;

if(arr[l] <= arr[mid])
{
if(k >= arr[l] && k < arr[mid])
{
r = mid;
}
else
{
l = mid + 1;
}
}
else
{
if(k < arr[mid] && k >= arr[l])
{
r = mid;
}
else
{
l = mid + 1;
}

}

return minIndex(arr, k, l, r);
}
return -1;``````

}

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.