Facebook Interview Question Development Support Engineers
Country: United States
Interview Type: Phone Interview
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",
"retrograde",
"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]);
}
}
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
}
}
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'.
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
<?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);
}
}
}
?>
<?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);
}
}
}
?>
public static void main(String[] args) {
String[] words = new String[]{
"ptolemaic",
"retrograde",
"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);
}
}
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));
}
}
}
public class DictRotatePt {
public static void main(String[] args) {
String[] words = {
"ptolemaic",
"retrograde",
"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;
}
}
public class DictRotatePt {
public static void main(String[] args) {
String[] words = {
"ptolemaic",
"retrograde",
"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;
}
}
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);
}
}
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)
- azambhrgn May 12, 2017