## Amazon Interview Question for SDE1s

Country: India
Interview Type: Phone Interview

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

I sincerely think it's much helpful to explain the algo than posting some code here.

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

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.

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

This is no binary search. Ur algo is O(n) if there is only 1 at the last index

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

Isn't converting to decimal itself o(n)??

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

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.

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

I think you are right gen-y-s

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

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

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

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;
}
}
}``````

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

``````#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);

else cout<<"Found at the location"<<ret<<endl;
}``````

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

Hey you should call the function search in the second last line of your search function with arguments as middle+1 and end

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

Fixed the bug in the argument list.

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

What is the complexity of this code ?

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

``````findOne(int arr[], int start, int end)
{
if(start == end)
if(arr[start] == 1)
return start
return -1;

t =   findOne(arr, start, mid);
if(t != -1)
return t;

return findOne(arr, mid+1, end);
}``````

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

can somebody explain it for me ?

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

The above code looks to me is assuming the array is sorted, and it is the general case binary search, it will not work for this case.

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

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);

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

Buddy this code is of complexity O(N).. i said we need to use Binary search or any other algo to find out the Index of First occurrance of 1 in the array//

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

``````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;
}
}``````

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

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;
}``````

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

Innovative answer, but require to use binary search strictly.

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

void bsearch(int item,int *a,int f,int l)
{

if(f<=l)
{
int k=(f+l)/2;

bsearch(item,a,f,k-1);
if(*(a+k)==item)
{
if(g==-1)
g=k;
}
bsearch(item,a,k+1,l);

}
}

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

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.

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

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?

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

``````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);
}``````

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

correction

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)
if(*res < 0)
*res = mid;
binarySearch_arr(a,mid+1,end,res);
}

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

You guys are morons. How do you do binary search on an array which is not sorted?

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

it's not exactly binary search. it's like binary search only!

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

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;
}
}``````

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

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``````

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

Wrong question. Binary search is applicable only for the sorted array. Nothing better than linear search when array is not sorted.

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

We can tweak the merge sort to do binary search

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

#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)) ;
}

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

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);
}
}``````

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

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);
}
}``````

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

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.

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

1. You can't use binary search here, cause array isn't sorted.
2. If your data is represented as int[] arr = {0,0,0,0,1,1,0 ...}, you can't do better then O(n) time algorithm.

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

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\$``````

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

dude do have an idea what you did?

make a dry run for case: 000000

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

``````@rahul(imrhk) its  working fine on my machine ans for ur string is 4.
@niraj,nijju: i think we need to find first occurence of 1 using bsearch. According to that if input string does not contain 1 then it should print something like this for ex:1 is not in string.``````

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.