Amazon Interview Question
SDE1sCountry: India
Interview Type: Phone Interview
Yes, I think you can use binary search to solve this problem.
let's say you have 100 0/1 in array. then convert binary to decimal, say k. if k > 1.
then convert first 50 to decimal, check if it is >1.
if it is 0, then convert 51~75
and go on....
you will find first 1 in lgn complexity.
This is a trick question, as it cannot be done in less than O(N).
Proof: Suppose we have an array of all zeros. Obviously we would have to check ALL the elements (and it doesn't matter in which order we do it) to know that there is no "1" element.
Now suppose we put "1" element in the last item we checked in the previous part, and run the algorithm again. It would still need N steps to find the "1" we inserted, since we already know that the item that contains "1" is the last one to be checked.
So we just prooved there is a case that takes O(N) to find the first "1". This means I proved that he problem is O(N) in the worst case.
Edit: Here's some explanation for Jack:
As indicated by the question, we are required to find the answer in O(N) or better time. Thus, sorting is not an option since it takes O(nlogn) time for any comparison based sorting algorithm. Finally, the question hinted to use a binary search meaning to cut things in halves and try to find the first occurring "1".
Typically, a binary search starts by looking at the middle of an array (or the root if it's a binary search tree), and if the middle (or root) is smaller than the item we are looking for, we go right else we go left. By going either direction, we effectively skipped half of the original array (or tree). This operation is O(logn) which is better than O(N).
However, the input is not sorted and so not all items on the left of the middle is smaller than the middle. This means, not all zeros are on the left side of the middle and not all ones are on the right side. This means, without sorting, the worse case is O(N).
Since the question insist on using "binary search", we can try to skip half of the list at a time until we hit a "1" that is on the left most side.
Here's my code in Python (now with comments):
def findOneHelper(bString, start, end):
#we are on the left most side of the sub-array
if(start == end):
#check if this left most index is "1"
if(bString[start] == "1"):
return start;
return -1;
#calculate the middle index of the array. Note that >> 1 is the same as divide by 2
mid = start+((end-start)>>1);
#Keep going left until we have reached the base case (left most index)
t = findOneHelper(bString, start, mid);
if(t != -1):
#if an index is found, return that to indicate this is where the first "1"
return t;
#Check the right half
return findOneHelper(bString, mid+1, end);
def findOne(bString):
return findOneHelper(bString, 0, len(bString)-1);
The output for: 00001101000001010100000
>>> findOne("00001101000001010100000")
4
Test cases:
>>> findOne("000000000000000000000")
-1
>>> findOne("111111111111111111111")
0
At a high level the code should look like this, ofcourse you need to check the boundary case and overflows.
int FindIndexOfFirstOne(number, length)
{
if (length < 1)
return -1;
int top = length-1;
int bottom = 0;
int curr = (top + bottom) /2;
while (top > bottom)
{
if (number < 2^ (curr)) // all the bits on left of curr digits is 0
{
top = curr;
curr = (top + bottom)/2;
}
else if (number == 2^(curr))
{
return curr;
}
else
{
if (number < 2^(curr+1)) //
return curr;
bottom = curr;
curr = top + bottom / 2;
}
}
}
#include <iostream>
using namespace std;
int search(int *list, int start, int end)
{
if(start > end) return -1;
int middle = (start+end)/2;
int nRet = -1;
nRet = search(list, start, middle-1);
if(nRet != -1) return nRet;
if(list[middle] == 1) return middle;
nRet = search(list, middle+1, end);
if(nRet != -1) return nRet;
}
void main()
{
int list[5]={1,0,1,0,0};
int ret = search(list, 0, sizeof(list)/sizeof(int)-1);
if(ret == -1) cout<<"Element Not Found"<<endl;
else cout<<"Found at the location"<<ret<<endl;
}
Hey you should call the function search in the second last line of your search function with arguments as middle+1 and end
int[] a = new int[10] { 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 };
int i;
int length = a.Length-1;
for (i = 0; i < a.Length/2; i++)
{
if (a[i]==1)
{
break;
}
else
{
if (a[i]!=a[length])
{
i = length;
break;
}
}
length--;
}
Console.WriteLine(i);
public class Main {
public static void main(Strings args[]) {
int[] input = {0,0,0,1,0,0,0,01,1,1};
OccurenceOf1.getOccurence(input, 0, input.length - 1);
}
}
public class OccurenceOf1 {
public static boolean getOccurence(int[] inputArray, int start, int end) {
int middle = (start + end) /2;
if(inputArray == null || inputArray.length == 0) {
System.err.println("Empty Array");
return false;
}
else if(middle == 0 && inputArray[middle] != 1) {
return false;
}
else if(middle == input.length - 1 && inputArray[middle] != 1) {
return false;
}
else if(inputArray[middle] == 1 && inputArray[middle - 1] != 1) {
System.out.println("First Occurence of 1 is " + middle);
return true;
}
else if(getOccurence(inputArray, start, middle)) {
return true;
}
else if(getOccurence(inputArray, middle, end)) {
return true;
}
else return false;
}
}
If bit vector represented as
int[] vector = { 0b0000000_00000000_00000000_00000000, 0b00001101_00000101_01000001_11001001, 0b00000000_00100101_01001001_10001111, };
you can achieve O(n/31)
private int firstOneIndex( int[] vector ){
final int BITS_PER_INT = 31;
int offset = 0;
for( int val : vector ){
if( val > 0 ){
int msbValue = Integer.highestOneBit(val);
return offset + (BITS_PER_INT - ((int)MathUtils.log2(msbValue) + 1)) + 1;
}
offset += BITS_PER_INT;
}
return -1;
}
We can apply binary search on this.
here is my example
if the given array is "000011010000"
First step, middle = (start + end)/2 = 6, then we compare "000001" with "000011" which is the first 6 digits from the given array.
"000011" is 3 in decimal and > "000001" = 1.
So, we need to search in the first part, which is start = 0, and end = middle = 6;
Second step, middle = 3, and we get "000" from array. "000" < "001". The target is shorten to digit 3 to 6
Third step, middle = 5, and we get "00001" is 1, we are done.
Here is my question
We can an array of bits. When we convert it to a integer, isn't we are scanning each and every array element? I mean
We divide the array into 2 halfes and take the first half. Now to know whether first half has a 1 we convert the array into integer.
My question is how we are converting the array into integer?Are we not scanning the complete array for this?
void binarySearch_arr(int a[],int start, int end,int* res)
{
if(start >= end)
return;
if(a[start] == 1)
*res = start;
int mid = (start+end)/2;
binarySearch_arr(a,start,mid,res);
if(a[mid] == 1)
*res = mid;
binarySearch_arr(a,mid+1,end,res);
}
C# solution
private static int FindFirst(int[] data, int startIdx, int endIdx)
{
if (data[startIdx] == 1)
return startIdx;
else if (startIdx == endIdx)
return -1;
else
{
int midIdx = Convert.ToInt32((startIdx + endIdx) / 2);
//Search left
int leftResult = FindFirst(data, startIdx, midIdx);
if (leftResult == -1)
{
//Look right
return FindFirst(data, midIdx + 1, endIdx);
}
return leftResult;
}
}
Assuming bitwise operators can be used, could this not be done easily using a slightly modified binary search? I'm short on time at the moment, so I'll just describe the algorithm.
Implement standard binary search, then modify the branch test as follows:
// bitwise "and" num with, e.g. 11110000. If > 0, must be a 1 on the left or current position
if ((~0 << (midpoint - 1)) & num > 0)
{
// bitwise "and" num with, e.g. 11100000. If 0, the current midpoint must be the first 1
if ((~0 << midpoint) & num == 0) //return midpoint
else //branch left
}
else //branch right
#include<stdio.h>
#include<strings.h>
int bsearch(char a[],int low,int high)
{
int mid,index;
mid=low+(high-low)/2 ;
printf("%d%d\n",low,high) ;
if(low>high||low==high && a[low]=='0')
return -1 ;
index=bsearch(a,low,mid-1) ;
if(index!=-1)
return index ;
if(a[mid]=='1')
return mid ;
return bsearch(a,mid+1,high) ;
}
void main()
{
char s[100] ;
int i=0;
printf("enter the string\n") ;
gets(s) ;
fflush(stdin) ;
while(s[i++]!='\0') ;
printf("%d\n",i) ;
printf("at %d index first occurance of 1",bsearch(s,0,i-1)) ;
}
Do a left favored binary search for "1" and keep shrinking the window of search till you get you get the same index or you can't find any more ones
public static int First1Search(int[] array)
{
int left = 0;
int right = array.Length - 1;
int minIndex = -1;
while (true)
{
int elementIndex = LeftFavoredSearch(array, left, right);
if (elementIndex == -1 || elementIndex == minIndex)
{
return minIndex;
}
else
{
minIndex = elementIndex;
right = minIndex;
}
}
}
public static int LeftFavoredSearch(int[] array, int l, int r)
{
if (l > r)
{
return -1;
}
int mid = (l + r) / 2;
if (array[mid] == 1)
{
return mid;
}
int leftSearch = LeftFavoredSearch(array, l,mid-1);
if (leftSearch != -1)
{
return leftSearch;
}
else
{
return LeftFavoredSearch(array, mid+1, r);
}
}
Do a left favored binary search for "1" and keep shrinking the window of search till you can't find and more 1s or search index of 1 remains same
public static int First1Search(int[] array)
{
int left = 0;
int right = array.Length - 1;
int minIndex = -1;
while (true)
{
int elementIndex = LeftFavoredSearch(array, left, right);
if (elementIndex == -1 || elementIndex == minIndex)
{
return minIndex;
}
else
{
minIndex = elementIndex;
right = minIndex;
}
}
}
public static int LeftFavoredSearch(int[] array, int l, int r)
{
if (l > r)
{
return -1;
}
int mid = (l + r) / 2;
if (array[mid] == 1)
{
return mid;
}
int leftSearch = LeftFavoredSearch(array, l,mid-1);
if (leftSearch != -1)
{
return leftSearch;
}
else
{
return LeftFavoredSearch(array, mid+1, r);
}
}
since the numbers are 0s and 1s you can treat them as binary and stuff them into an int (so the first 32 elements form an integer, the next 32 another integer) and at the end you`ll have an array of ints. Now you can do a binary search agains 0. If the first element of the aray is greater than 0 then there's a one there. Split that byte into 16 bit integers and check the first half .. and so on until you find the one. Of course you need to track the displacement in the String.
the code is not working as
rahul@hp:~/careercup$ g++ binaryStringBinarySearch.cpp
rahul@hp:~/careercup$ ./a.out
00001101000001010100000
1 is not in string
rahul@hp:~/careercup$
I sincerely think it's much helpful to explain the algo than posting some code here.
- Jackie May 21, 2013