## Amazon Interview Question for Development Support Engineers

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

O(loglogn) - Interpolation Search- not recommended as points are not equally iid (Independent and identically-distributed )
O(Logn) - Binary Search : Could not be so dumb question

Not able to scrutinize the exploitation of 0's 1's , Hashing wouldn't help.

Please comment.

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

LOL @interpolation search.

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

wtf is equally iid?

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

this is infinite array binary search can not be used.

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

As it is a sorted array Binary search will be the best soln

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

As it is a sorted array Binary search will be the best soln

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

As it is a sorted array Binary search will be the best soln

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

How??
You have to find the FIRST occurrence of 1, with Binary search, when you start in middle, and there is a 1, it will exit. You dont want that.

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

You need to modify the binary search little bit such that the if the middle element happens to be a 0 then if the number right next to it is 1 then u conclude that is the first one else if the middle number happens to be a 1 then if the number left to it is a 0 then u can conclude its the first one...if none of these is the case then u recurse the same process of the left half if the middle number happens to be a one or the right half if the number happens to be a zero. Its technically Binary search paradigm . Hope that helps.

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

this should give correct result in O(log n)

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

Add all the numbers , suppose u get x.This takes O(N).
Now suppose size of array is n , now index to n-x. This is O(1).This is the 1st one.This works as array is sorted and zeros come first.

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

LOL.

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

:D..

when you want to scan the array to add the elements, why not actually check them and return as soon as you find 1 :P

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

To mohammad.z.siddiqui
Your approach looks fine to me. I think that way we can tackle the problem.
To Rohan
Your approach sucks as you dint read the question properly.

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

here is my solution:
Jump 2 steps, see if it 1, then jump 4, 8 etc until u hit a one.
Then jump back 1,2,4,8 etc until u hit a zero, then forward and backward (until orgasm:)
This works good, O(log N) worst case

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

could someone clarify,

if the sequence is sorted then all 0's would obv appear first and then followed by 1's are they asking us to find the occurrence of the first "1" in the array,is that the question?

If the answer to my previous question is "yes" then are we required to find a method which takes < O(n).If its an O(n) solution then I am sure all of us know more than one method to do this qn.

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

none of the above solutions fully exploit the 0/1 property of the array

thinking...

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

Using a modified version of the binary search algorithm, you can return the lower bound index when the lower bound has the key being searched in case when the upper bound is greater than or equals to the key.

firstOccurrance(int[] sortedBins) {
int lower = 0;
int upper = sortedBins.length - 1;
while (lower <= upper) {
int middle = 1 + (upper - lower) / 2;
if (sortedBins[middle] == 0) {
lower = middle + 1;
} else {
upper = middle - 1;
}
if (sortedBins[lower] == 1) {
return lower;
}
}
return -1;
}

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

public static int findNum(int[] arr)
{
Set s =new HashSet<>();

int index=0;
for(int i=0;i<arr.length;i++)
{
if(s.add(arr[i]) && arr[i]==1)
{
index=i;
}
}
return index;
}

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

when using hashset you are again scanning through the array which means complexity is >O(n)

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

#include<stdio.h>
#include<math.h>
int BinarySearch(short int* array, int end) {
int mid;
int start=0;
while(start<=end) {
mid=(start+end)/2;
if(array[mid]==0 && array[mid+1]==1)
return mid+2;
else if(array[mid]==1 && array[mid-1]==0)
return mid+1;
else if(array[mid]==0)
start=mid+1;
else if(array[mid]==1)
end=mid-1; }
return -1; }

int find(short int* array) {
int i=0;
long long index=0;
while(array[index]!=1) {
i++;
index=pow(2,i); }
i=BinarySearch(array,index);
return i; }

Add a Comment
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.

Learn More

### 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.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More