Amazon Interview Question
SDE1sCountry: India
Interview Type: Written Test
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.
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;
}
@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.
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;
}
// 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);
}
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;
}
// 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;
}
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;
#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);
}
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;
}
}
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)
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;
}
Use binarysearch.
Code:
- Dhass April 27, 2013