Amazon Interview Question for SDE1s


Country: India
Interview Type: Written Test




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

Use binarysearch.
Code:

public int binSearch(int a[], int low, int high) {
		if (low > high)
			return -1;
		int mid = low + (high - low) / 2;
		if (a[mid] == 1 && (mid == 0 || a[mid - 1] == 0))
			return mid;
		else if (a[mid] == 1 && a[mid - 1] != 0)
			return binSearch(a, low, mid - 1);
		else
			return binSearch(a, mid + 1, high);
	}

- Dhass April 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 votes

Great! Minor modification:
In line "else if (a[mid] == 1 && a[mid - 1] !=0)", we can get rid of latter condition, as it is already checked above line. So,
"else if (a[mid] == 1)" would suffice.

- EJ April 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

public int binSearch(int a[], int low, int high) {
if (low > high)
return -1;

int mid = low + (high - low) / 2;
while(low<high){
if(a[mid] < 1){
low = mid+1;
}
else{
high = mid-1;
}
mid = low + (high-low)/2;
}

if(high == -1){
return 0;
}

return high;
}

- vishwanath April 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

is number of element n given?

- BVarghese April 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Will not work for 1 element

- CareerCup April 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@EJ : condition mid==0 is needed ..
take this case .. low=0,high=1 ==> mid=0 and a[mid]==1 then this condition is needed.

@srikath.mujjiga : This works with one element also.. when there is single element .. a[]={0} or a[]={1}..
low=0,high=0, mid=0.
In first case,
binSearch(a, mid + 1, high); will be executed and return -1.
In second case,
if (a[mid] == 1 && (mid == 0 || a[mid - 1] == 0)) will be true and return index 0.

- bharat April 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

And the correct version is:

public static int findTheIndexOfFirstOne(int[] numArray, int start, int end) {
		
		if (start > end || numArray == null || numArray.length == 0) return -1;	
		int mid = (start + end) / 2;
		if (numArray[start] == 1) return start;
		
		int index = -1;
		if (numArray[mid] == 1) {
			index = findTheIndexOfFirstOne(numArray, start, mid);
		} else {
			index = findTheIndexOfFirstOne(numArray, mid+1, end);
		}
		return index;

}

- Vijay Muvva May 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

returns 12 as the answer for the following array.

int []bb = new int[] { 0,1,1,1,0,0,0,0,1,0,0,0,1};

- anon June 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

// Returns -1 if the element is not found from a sorted array
    public static int firstIndex(int[] a, int num){
        return firstIndex(a,0,a.length-1,num);
    }

    public static int firstIndex(int[] a, int start, int end, int num){
        if(a==null || a.length==0 || start>end || a[start]>num || a[end]<num)
            return -1;
        // If the element is found right at the beginning that has got to be the first Index
        if(a[start]==num)
            return start;

        int mid = (start+end)/2;
        // If we found that does not necessarily mean that its the first index
        if(a[mid]==num){
            // Recursively look for num lower in the array
            int ind = firstIndex(a,start,mid-1,num);
            // Check if we found a lower number than mid. If not then return mid
            // else return the lower number
            return ind == -1 ? mid : ind;
        }
        // If a[mid] was higher than our required number then we need to find it lower in the array
        else if(a[mid]>num)
            return firstIndex(a,start,mid-1,num);
        // Else we need to find it higher in the array
        else
            return firstIndex(a,mid+1,end,num);
    }

- Anonymous April 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My 1st try to solve this problem is :
If array is given sorted then we use binary search on this and find the 1st occuracne of the '1' .
It take O(log n) time complexity and O(1) space complexity.
let me correct if my try is wrong ?

- Suhas April 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<conio.h>
#include<string.h>
int main(){
    int i=0,j,length,count=0;
    char a[50];
    
    scanf("%s",a);
    
length=strlen(a);
for(j=0;j<length;j++)
{
if(a[j]!='1')
count++;
else break;

}
printf("%d",count);
getch();
return 0;
}

- kaushal yadav April 27, 2013 | Flag Reply
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;
}

- jits April 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I would attack this question with binary search. Here is my Java version:

public static int findTheIndexOfFirstOne(int[] numArray, int start, int end) {
		
		if (start > end || numArray == null || numArray.length == 0) return -1;	
		int mid = (start + end) / 2;
		if (numArray[start] == 1) return start;
		
		int index = -1;
		if (numArray[mid] == 1) {
			index = findTheIndexOfFirstOne(numArray, start, mid);
		} else {
			index = findTheIndexOfFirstOne(numArray, mid+1, end);
		}
		return index;

}

- Vijay Muvva April 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Binary Search would be the right approach.

- Sekhar Pedamallu April 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int Find(int *a, int l, int u)
{
  if ((a[l] == 0) && (a[u] == 0))
    return -1;

  if ((a[l] == 1) && (a[u] == 1))
    return l;
  else
  {
    int mid = (l+u)/2;
    if (a[mid] == 0)
      return Find(a,mid+1,u);
    else
      return Find(a,l,mid);
  }
}

- CareerCup April 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// int[] a = {0, 0, 0, 0, 1, 1, 1, 1, 1};
    // find(a, 0, a.length-1, 1, -1)
    static int find(int[] a, int start, int end, int search, int presenceSofar)
    {
        int size = end-start+1;
        if(size == 0)
            return presenceSofar;

        int mid = (size/2) + start;
        if(search > a[mid])
            return find(a, mid+1, end, search, presenceSofar);
        
        if(search == a[mid])
            return find(a, start, mid-1, search, mid);
        
        return presenceSofar;

}

- krishnakumar.m April 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hmmm just some error in my comments in the beginning

//Check if last element is zero then return index value -1

- Naveen.Miriyalu April 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Logic: Array consists of only 0s and 1s. Lets assume that we apriori know the length of the array.
Then, mean(Array) gives us the fraction of 1s in the array, or s=sum(Array) gives us the # of 1s in the array.
index of 1st 1, in = length(Array)-sum+1;

- tejas May 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Just an addition,
To add the case where there are no 1s in the array, check if in > length(Array).

- tejas May 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>


int search(int arr[], int low, int high)
{

int mid,n;
if (low>high )
return -1;
if (low==high)
{

return low;
}

mid=(low+high)/2;
printf("\nlow=%d,mid=%d,high=%d",low,mid,high);

if (arr[mid]>0)
{
search(arr,low,mid);
}
else
{

search(arr,mid+1,high);
}


}


int main()
{
int pos;
int arr[]={0,0,0,0,0,0,0,1,1,1,1,1};

pos=search(arr,0,11);
printf("\n%d",pos);
}

- Anonymous May 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

package com.test.launch;

public class FirstOne
{

/**
* @param args
*/
public static void main(String[] args)
{
FirstOne first = new FirstOne();

String str = "0000000011111";

int index = first.firstOneIndex(str.toCharArray(), 0, str.length() - 1);

System.out.println(index);

}

public int firstOneIndex(char[] input, int start, int end)
{
if (start > end)
{
return -1;
}

int mid = (start + end) / 2;
if (input[mid] == '0')
{
if (mid == input.length - 1)
{
return -1;
} else if (input[mid + 1] == '1')
{
return mid + 1;
} else
{
return firstOneIndex(input, mid + 1, end);
}
} else if (input[mid] == '1')
{
if (mid == input.length - 1)
{
return mid;
} else if (input[mid - 1] == '0')
{
return mid;
} else
{
return firstOneIndex(input, start, mid - 1);
}
}

return -1;

}

}

- Anonymous May 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int findFirstOne(int array[]){
	  
	  int length=array.length;
	  
	  int head=0,tail=length-1;
	  
	  while(head<tail){
		  
		  int middle=head+(tail-head)/2;
		  
		  if(array[middle]==0)
		  head=middle+1;
		  else 
	      tail=middle;
		  	  
	  }
	  
	  if(head==tail && array[head]==1)
		return head;  
	  
	  
	  
	  
	  return -1;
  }
  
  
}

int a1[]={0,0,0,0,0,0,0,0,0,0,0};
		int a2[]={0,0,1,1,1,1,1,1};
		int a3[]={1,1,1,1,1,1,1,1,1};
		int a4[]={0,0,0,0,0,0,0,0,0,0,1};
		
		System.out.println(" a1 ="+findFirstOne(a1)+" a2 ="+findFirstOne(a2)+" a3="+findFirstOne(a3)+" a4= "+findFirstOne(a4));

OUTPUT------------------------------------
a1 = -1 a2 =2 a3 =0 a4= 10


time complexity = O(lgn)

- MrA May 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int return_first_1(int * a, int n)
{
    int low = 0;
    int high = n-1;
    int mid;
    
    while(1)
    {
        mid = (low+high)/2;
        
        if((mid >= 0) && (mid < n) && (low <= high))
        {
            if( a[mid] == 0 ) {
                
                if(((mid+1) < n) && a[mid+1] == 1) {
                    
                    return (mid+1);
                } else {
                    
                    if(mid == 0)
                        return 0;
                    
                    low = mid+1;
                }
                
            } else if( a[mid] == 1 ) {
                
                if((mid-1) >= 0 && a[mid-1] == 0) {
                    
                    return mid;
                } else {
                    
                    if(mid == 0)
                        return 0;
                    
                    high = mid-1;
                }
                
            }
            
        } else {
            break;
        }
    }
    
    return -1;
}

- chaitanya.jun12 May 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If we know the array length in advance (if we don't know we can't apply binary search as well) i.e. N the following approach can be chosen.

for i = 0 to N/2
If arr[i] == 1
break;
else if arr[N-i-1] == 0
break;

- Sandy May 16, 2013 | Flag Reply


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