Labs247 Interview Question
Tech LeadsTeam: Unknown
Country: India
Interview Type: Phone Interview
modification
1. search index exponentially 0,1,2,4,8,16,....
2. when you encounter 1 at any index, it means the transition 0->1 lies within x/2 and x
Till this step the above algorithm is correct.
But what if x is 100 million?? you do not want to operate a binary search on 50 million numbers. We already have a function which performs exponential search.
therefore 3rd step :
3. Recursive call to exponential search function which will now start at x/2, x/2 +1, x/2 + 2, x/2 + 4, x/2 +8, x/2 + 16....
/**
* You are given a list of integers.
* You can call only one method on the list:getItemAt(x),
* which will return the integer at the index x from the list.
*
* The list starts with value 0 and it goes on to have value 0 continuously until some index.
* After the index the list continues to have value 1 till the end.
*
* You do not know the size of the list.
* Its huge.
* You need to find the index from where the value 1 begins in the list.
* @author patrick_diloreto
*
*/
public class FindPivot {
public static void main(String[] args) {
//pivot-index = 16
int[] elements = new int[] {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 , 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
int index = findPivotIndex(elements, 0, 0);
System.out.println("16 == " + index);
assert(16 == index);
}
public static int findPivotIndex(int[] elements, int index, int previous) {
int value = elements[valueFor(index)];
if(value == 0)
return findPivotIndex(elements, index+1, index);
else {
//value = 1
return binarySearch(elements, valueFor(previous), valueFor(index));
}
}
private static int binarySearch(int[] elements, int start, int end) {
if(end == start)
return start;
else {
int middle = (start + end)/2;
if(start == middle)
return end;
return (elements[middle]==0) ?
binarySearch(elements, middle, end) :
binarySearch(elements, start, middle);
}
}
private static int valueFor(int index) {
if(index == 0) {
return 0;
}
else {
return (int)Math.pow(2, index);
}
}
}
it gives an ArrayIndexOutOfBoundsException with input
int [] elements = {0,0,0,0,0,0,1,1};
it fails because the list is very small and the distribution to get the next index is expo, so because the list has only 7 elements on the 3rd iteration I'm looking already at the index 8. The pre-condition of the problem says that is a huge list where I don't know the size as that is very large.
This problem can be solved by using binary search to get the first position of 1 in the list. Here is the logic:
a. First check for the middle position of the array. If the mid is not 1 then you do not have to check in the left subarray as it will contain only 0s. For it you just have to check the right subarray.
#include <stdio.h>
#include <stdlib.h>
int firstPosOfOne(int arr[],int low,int high)
{
if(low==high)
{
if(arr[low]==1)
return low;
}
if(low+1==high)
{
if(arr[high]==1)
return high;
else if(arr[low]==1)
return low;
}
else
{
int mid=low+(high-low)/2;
if(arr[mid]==1)
return mid;
firstPosOfOne(arr,mid+1,high);
}
}
int main()
{
int arr[]={0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1};
int n=sizeof(arr)/sizeof(arr[0]);
printf(" First position of one occurs at %d location in the array ",firstPosOfOne(arr,0,n-1));
}
Used List.get in place of getItemAt in below answer
import java.util.LinkedList;
import java.util.List;
public class ZeroToOne {
public static void main(String[] args) {
int zero = 1000; //Zero count
int one = 9; //One Count
List<Integer> list = new LinkedList<>();
ZeroToOne zto = new ZeroToOne();
for (int i = 0; i < zero; i++)
list.add(0);
for (int i = 0; i < one; i++)
list.add(1);
System.out.println(zto.getZeroToOnePos(list));
}
public int getZeroToOnePos(List<Integer> list) {
int start = 0;
int end = 0;
int factor = 2;
/*
* Narrow down search area by exponential movements and
* adjust end point if gone beyond original list.
*/
while(true) {
/*
* try-catch to check if gone beyond list.
* In case of c, we can check for value != 0 and 1
*/
try {
if(list.get(end) == 1)
break;
start = end + 1;
end += factor;
factor *= 2;
} catch(Exception e) {
//Assuming IndexOutOfBounds or similar
/*
* Went beyond the list boundary. Re-align end position
*/
factor = (end - start) / 2;
end = start + factor;
if (start == end)
return end + 1;
}
}
/*
* Binary search for 0-1 in identified range.
*/
while (true) {
if (start >= end)
return end;
int middle = (start + end) / 2;
int val = list.get(middle);
if (1 == val) {
if (list.get(middle - 1) != 1) // can be a '== 0' check also
return middle;
else
end = middle - 1;
} else {
start = middle + 1;
}
}
}
}
1. we can search at index 0,1,2,4,8,16....
- cobra July 06, 20132. at the point we get getItemAt(x) == 1, our required index at x/2 < ans_index <= x
3. from (x/2)+1 to x we can do binary search and can find the required index