## Facebook Interview Question for Development Support Engineers

Country: United States
Interview Type: Phone Interview

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

There could be two solution -

1- Using the linear search approach to find the index(say ind) of the point where words array of string stop the lexicographical increasing order.
Time complexity O(n)

2-We can reduce time complexity to the O(logn) time by using the Binary search approach, And I think it is the best solution for your question.

Approach -
Find the pivot point which is lesser in order(in dictionary) from prev string in your words array.
Below is running and tested code in java

``````public static int findTheRotation(String[] str,int l,int h){
// No rotation point will return -1
if(l > h){
return -1;
}
if(l == h) {
return h;
}

int mid = (l+h)/2;

//The rotation point is found at mid+1
if(mid < h && str[mid].compareTo(str[mid+1]) > 0){
return mid+1;
}

if(l < mid && str[mid-1].compareTo(str[mid]) > 0){
return mid;
}

//if Rotation point lies on left side
if(str[mid].compareTo(str[h]) < 0){
return findTheRotation(str, l, mid-1);
}
//Otherwise will check right array
return findTheRotation(str, mid+1, h);
}``````

Time complexity for above code is O(logn)

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

``````import java.io.*;
import java.util.*;

class Solution {

public static int findRotateIndex(String[] words) {

int start = 0;
int end = words.length - 1;
int result = 0;

while(start < end) {
int mid = (start + end)/2;

if(start + 1 == end) {
if(words[start].compareToIgnoreCase(words[end]) < 0) {
result = start;
} else {
result = end;
}
break;
}

if(words[mid].compareToIgnoreCase(words[start]) < 0) {
//top half is unsorted
end = mid;
} else {
//bottom half is unsorted
start = mid;
}
}

return result;
}

public static void main(String[] args) {

String[] words = new String[]{
"ptolemaic",
"supplant",
"undulate",
"xenoepist",
"asymptote", // <-- rotates here!
"babka",
"banoffee",
"engender",
"karpatka",
"othellolagkage",
};

int rotateIndex = findRotateIndex(words);

System.out.println("Rotated at : "+String.valueOf(rotateIndex) + " : Word : " + words[rotateIndex]);

}
}``````

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

in scala:

``````object WordsBinarySearch {

def main(args: Array[String]): Unit = {
val a = Array("pto", "ret", "supp", "und", "xen", "asyn", "bah", "bano", "ccc", "ddd")
println(getIndexRotationPoint(a))
}

def getIndexRotationPoint(a:Array[String]) : Int = {
var i = 0
var j = a.length-1

while (i < j) {
val m = a.length / 2

if (m >= 1 && a(m).compareTo(a(m-1)) < 0) {
return m
} else if (m < a.length+1 && a(m).compareTo(a(m+1)) > 0) {
return m+1
}

if (a(i).compareTo(a(m)) < 0) {
i = m + 1
} else {
j = m - 1
}
}

return i
}

}``````

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

What I understand from the problem statement: You need to find the index of the first word that starts with the letter 'a'. For that read the input array from the System.in and break at the point when you find first word with first character as 'a'. Please correct me if my understanding is wrong:

``````import java.util.*;

public class DictionaryRotationIndex
{
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
int iDictSize = sc.nextInt();
String[] arr = new String[iDictSize];
int iIndex = -1;
for(int i=0; i < iDictSize; i++)
{
arr[i] = sc.next();
if(arr[i].charAt(0) == 'a')
{
iIndex = i;
break;
}
}
System.out.println(iIndex);
}
}``````

Worst case time complexity: O(n) - assuming last array item starts with 'a'.
Best case time complexity: O(1) - assuming first array item starts with 'a'.
Average case time complexity: O(n) - assuming middle array item starts with 'a'.

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

Classical variation of the binary search as other solutions have already specified.
Solution in python

``````def get_index(words):
start = 0
end = len(words)-1
middle = (end - start) / 2

while words[middle - 1] < words[middle]:
if words[middle] < words[end]:
end = middle
elif words[middle] > words[start]:
start = middle

middle = ((end - start) / 2) + start

return middle``````

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

``````<?php

\$array = array("z","a","o","p","r","s","t","w");

echo findIndexOfRotation(\$array,0,sizeof(\$array)-1);

function findIndexOfRotation(\$array,\$left,\$right){

if(\$right<\$left) return -1;
if(\$right == \$left) return \$right;

\$n = \$right-\$left;
\$mid = floor(\$n/2)+\$left;
if(\$array[\$mid] == "a") return \$mid;
else{
if(\$array[\$right] > \$array[\$mid]){
//Study left
return findIndexOfRotation(\$array,\$left,\$mid-1);
}
else{
//Study right
return findIndexOfRotation(\$array,\$mid+1,\$right);
}
}

}

?>``````

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

``````<?php

\$array = array("z","a","o","p","r","s","t","w");

echo findIndexOfRotation(\$array,0,sizeof(\$array)-1);

function findIndexOfRotation(\$array,\$left,\$right){

if(\$right<\$left) return -1;
if(\$right == \$left) return \$right;

\$n = \$right-\$left;
\$mid = floor(\$n/2)+\$left;
if(\$array[\$mid] == "a") return \$mid;
else{
if(\$array[\$right] > \$array[\$mid]){
//Study left
return findIndexOfRotation(\$array,\$left,\$mid-1);
}
else{
//Study right
return findIndexOfRotation(\$array,\$mid+1,\$right);
}
}

}

?>``````

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

``````public static void main(String[] args) {

String[] words = new String[]{
"ptolemaic",
"supplant",
"undulate",
"xenoepist",
"asymptote", // <-- rotates here!
"babka",
"banoffee",
"engender",
"karpatka",
"othellolagkage",};

System.out.println(rotationPoint(words, 0, words.length - 1));
}

private static int rotationPoint(String[] words, int b, int e) {
if (e - b == 1) {
return words[b].compareTo(words[e]) > 0 ? e : -1;
}
int m = (b + e) / 2;
int c = words[b].compareTo(words[m]);
if (c < 0) {
return rotationPoint(words, m, e);
} else {
return rotationPoint(words, b, m);
}
}``````

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

``````package algorithms.sorting;

import java.util.Arrays;

public class P1 {

public static void main(String[] args) {
String[] words = new String[]{
"a", "b", "c", "d", "e", "f", "g", "h", "i", "j"
};

int rotateIndex = findRotateIndex(words);

if(rotateIndex == -1) {
System.out.println("Not Rotated");
}
else {
System.out.println("Rotated at : " + String.valueOf(rotateIndex) + " : Word : " + words[rotateIndex]);
}

}

private static int findRotateIndex(String[] words) {
if(words.length == 1) {
return -1;
}
int mid = words.length / 2;
int prevResult = words[mid].compareTo(words[mid - 1]);
int nextResult = words[mid].compareTo(words[mid + 1]);
int firstResult = words[mid].compareTo(words[0]);
int lastResult = words[mid].compareTo(words[words.length - 1]);

if(nextResult > 0) {
return mid + 1;
}
if(prevResult < 0) {
return mid;
}
else if(lastResult > 0) {
return findRotateIndex(Arrays.copyOfRange(words, mid + 1, words.length));
}
else {
return findRotateIndex(Arrays.copyOfRange(words, 0, mid));
}
}
}``````

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

``````public class DictRotatePt {

public static void main(String[] args) {
String[] words = {
"ptolemaic",
"supplant",
"undulate",
"xenoepist",
"asymptote", // <-- rotates here!
"babka",
"banoffee",
"engender",
"karpatka",
"othellolagkage"
};
System.out.println("Index " + findRotationPt(words));
}
public static int findRotationPt(String[] words) {
int start = 0;
int end = words.length - 1;
boolean found = false;
int index = 0;
while(found == false) {
index = (start + end) / 2;
String word = words[index];
if(word.charAt(0) == 'a') {
if(words[index - 1].charAt(0) == 'a') {
end = index - 1;
} else {
found = true;
}
} else {
if(word.charAt(0) > words[end].charAt(0)) {
start = index + 1 ;
} else {
end = index - 1;
}
}
}
return index;
}
}``````

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

public class DictRotatePt {

public static void main(String[] args) {
String[] words = {
"ptolemaic",
"supplant",
"undulate",
"xenoepist",
"asymptote", // <-- rotates here!
"babka",
"banoffee",
"engender",
"karpatka",
"othellolagkage"
};
System.out.println("Index " + findRotationPt(words));
}
public static int findRotationPt(String[] words) {
int start = 0;
int end = words.length - 1;
boolean found = false;
int index = 0;
while(found == false) {
index = (start + end) / 2;
String word = words[index];
if(word.charAt(0) == 'a') {
if(words[index - 1].charAt(0) == 'a') {
end = index - 1;
} else {
found = true;
}
} else {
if(word.charAt(0) > words[end].charAt(0)) {
start = index + 1 ;
} else {
end = index - 1;
}
}
}
return index;
}
}

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

``````public static int findRotatedIndexIterative(String[] arr) {
int start = 0, end = arr.length - 1, mid;

while(start < end) {
mid = (start + end) / 2;

if(mid < end && arr[mid].compareToIgnoreCase(arr[mid + 1]) > 0)
return (mid + 1);
if(mid > start && arr[mid].compareToIgnoreCase(arr[mid - 1]) < 0)
return mid;

if(arr[start].compareToIgnoreCase(arr[mid]) > 0) {
end = mid - 1;
}else{
start = mid + 1;
}
}

if(end == start && end == arr.length - 1)
return 0;
return start;
}

public static int findRotatedIndexRecursive(String[] arr, int start, int end) {
if(start == end) return end;

int mid = (start + end) / 2;

if(mid < end && arr[mid].compareToIgnoreCase(arr[mid + 1]) > 0)
return (mid + 1);
if(mid > start && arr[mid].compareToIgnoreCase(arr[mid - 1]) < 0)
return mid;

if(arr[start].compareToIgnoreCase(arr[mid]) > 0) {
return findRotatedIndexRecursive(arr, start, mid - 1);
}else{
return findRotatedIndexRecursive(arr, mid + 1, end);
}
}``````

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

I sort the list, then find the first element of the sorted list in previous one, that will be the index of a rotation.

``````words = ["pto", "ret", "supp", "und", "xen", "asyn", "bah", "bano", "ccc", "ddd"]
words_sorted = sorted(words)
index = words.index(words_sorted[0])
print(index)``````

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.