Amazon Interview Question SDE1s
Team: Hyderabad
Country: India
Interview Type: Phone Interview
Nicely done Why are you sorting the array using prepareData? The array is already sorted?
I don't know how to replay for an comment, so I am answering here:
>> Nicely done Why are you sorting the array using prepareData? The array is already sorted?
prepareData is just a generator. It prepare random input data in format as you descibed in the task. The solution is in the method binarySearch().
>> This fails for [0, 0, 0]. Returns 2.
an odd, I ran my code with your example and I see the answer:
[0, 0, 0]
3
You can check it via copy-paste the code below:
import java.util.Arrays;
import java.util.Random;
/**
* Created by Igor_Sokolov on 6/16/2015.
*/
public class CareerCup_5766344614084608 {
public static void main(String[] args) {
int[] a = {0, 0, 0};
System.out.println(Arrays.toString(a));
int pos = binarySearch(a);
System.out.print(pos);
}
private static int binarySearch(int[] a) {
int l = 0;
int r = a.length - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (a[m] < 1) {
l = m + 1;
} else {
r = m - 1;
}
}
return l;
}
}
public class SortedArray {
static int countZeros(int[] arr) {
int index = 0;
while (arr[index] != 1) {
index++;
}
return index;
}
public static void main(String[] args) {
int[] arr = { 0, 0, 0, 0, 1, 1 };
System.out.println("No: of Zeros = " + countZeros(arr));
}
}
Simple binary search looking for index i where arr[i] == 1 and arr[i-1] == 0, return i-1->
Complexity = O(log n), memory = O(1)
public static int countZeros(int[] arr){
//handle base cases
if(arr == null){
throw new NullPointerException();
}
if(arr.length == 0){
return 0;
}
if(arr[0] == 1){
return 0;
}
if(arr[length-1] == 0){
return length;
}
//handle binary search
int lo = 0;
int hi = arr.length - 1;
int mid;
while(hi - lo > 1){
mid = (lo >> 1) + (hi >> 1);
if(arr[mid] == 1){
hi = mid;
}
else{
lo = mid;
}
}
return hi;
}
"mid = (lo + hi) / 2;" here is a classical issue with overflow. Actually such bug was in implementation of sort algorithm in java. If we have lo and hi close to integer max value it may lead to overflow.
public class ZeroCounter
{
public int countZeros(int[] arr)
{
if(arr==null||arr.length==0)
{
throw new InvalidInputException("The input array cannot be null or empty");
}
int start=0
int end=arr.length-1;
while(start<=end)
{
int mid=(start+end)/2;
if(arr[mid]==0)
{
return mid+1;
}
end=mid-1;
}
}
public class CountZeroTester
{
ZeroCounter zc=new ZeroCounter();
int numZeros=zc.countZeros(input);//where input is an int array of 0s and 1s
}
Fix for the counter,
static int countZeros(int[] arr)
{
int iCount = 0;
int index = 0;
while(index < arr.Length)
{
if (arr[index] != 1)
{
iCount++;
}
index++;
}
return iCount;
}
<strong>Using binary search:</strong>
Best case: O(1) when there are equal number of zeros as there are ones<br>
Worst case: O(log n) when there is no zero in the array<br>
<br>
<strong>Using linear search:</strong>
Best case: O(1) when there are no zeros in the array<br>
Worst case: O(n) when there are only zeros in the array.<br>
public class MinVal {
static int[] a={0,0,0,0,0,1};
public int returnCount(int arr[],int low,int high) {
if(high >=low) {
int mid = (low+high)/2;
//System.out.println(mid);
if(mid == 0 && a[mid]==0) {
return mid+1;
}
if((mid == 0 || a[mid-1]==0)&& a[mid]==1) {
return mid;
}
if (a[mid]==1) {
return returnCount(arr,low,mid-1);
} else {
return returnCount(arr,mid+1,high);
}
}
return -1;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
MinVal minVal = new MinVal();
int mid = minVal.returnCount(a, 0, a.length-1);
System.out.println(mid);
}
}
Use binary search to find when there is a zero after one to make this a O(log(n)) algorithm rather than a O(n).
This could also be done alliteratively with a while loop but decided to do recursively just a bit simplicity.
(or maybe I'm loosing my edge) :-P
public int CountZeros(int[] A)
{
return coreCountZeros(A, 0, A.Length);
}
private int coreCountZeros(int[] A, int start, int end)
{
if(start == (end - 1))
{
if(A[start] == 0)
return start + 1;
return start;
}
int mid = (start + end)/2;
if(A[mid] == 1)
{
return coreCountZeros(A, start, mid);
}
//else A[mid] == 0
return coreCountZeros(A, mid, end);
}
This solution uses binary search and runs in O(log n)
def get_count_0s(a):
if not a:
return -1
return _get_count_0s(a, 0.5, 0, len(a) - 1)
def _get_count_0s(a, t, beg_i, end_i):
if beg_i == end_i:
if a[beg_i] == 1:
return beg_i # it’s the index
return beg_i + 1
mid_i = (beg_i + end_i) // 2
if a[mid_i] < t: # must look higher
return _get_count_0s(a, t, mid_i + 1, end_i)
return _get_count_0s(a, t, beg_i, mid_i - 1) # must look lower
print(get_count_0s([0] * 9 + [1] * 8))
def get_count_0s(a):
if not a:
return -1
return _get_count_0s(a, 0.5, 0, len(a) - 1)
def _get_count_0s(a, t, beg_i, end_i):
if beg_i == end_i:
if a[beg_i] == 1:
return beg_i # it’s the index
return beg_i + 1
mid_i = (beg_i + end_i) // 2
if a[mid_i] < t: # must look higher
return _get_count_0s(a, t, mid_i + 1, end_i)
return _get_count_0s(a, t, beg_i, mid_i - 1) # must look lower
print(get_count_0s([0] * 9 + [1] * 8))
Here is my implementation using c++. The basic idea is binary search with O(lg n) time complexity.
int count0s(string input, int l, int r){
if(l>=r){
if(input.at(l)=='0')
return l+1;
return l;
}
int mid = (l+r)/2;
if(input.at(mid)=='0')
return count0s(input,mid+1,r);
else
return count0s(input,l,mid-1);
return l;
}
Here is my implementation in c++. The basic idea is reccursive binary search with O(lg n) time complexity.
int count0s(string input, int l, int r){
if(l>=r){
if(input.at(l)=='0')
return l+1;
return l;
}
int mid = (l+r)/2;
if(input.at(mid)=='0')
return count0s(input,mid+1,r);
else
return count0s(input,l,mid-1);
return l;
}
Here is my implementation in c++. The basic idea is reccursive binary search with O(lg n) time complexity.
int count0s(string input, int l, int r){
if(l>=r){
if(input.at(l)=='0')
return l+1;
return l;
}
int mid = (l+r)/2;
if(input.at(mid)=='0')
return count0s(input,mid+1,r);
else
return count0s(input,l,mid-1);
return l;
}
public class HowManyZeros {
public static int zero(int a[] , int l , int h)
{
while(l<h)
{
int m = (l + h)/2 ;
if(a[m-1]<1 && a[m]!=1)
{
return zero(a, m , h );
}
else if(a[m]>0 && a[m-1]!=0)
return zero(a , l , m-1);
else return m ;
}
return -1 ;
}
public static void main(String args[])
{
int []arr = {0 , 0 , 0, 0 , 0 , 1 , 1 , 1};
System.out.println(zero(arr , 0 , 6));
}
}
As the array is already sorted just look for the first number 1 get its position and it will be the number of 0’s.
import java.util.*;
public class ZeroCounter{
public static int getNumberCount(int number, List<Integer> sortedArray){
return sortedArray.indexOf(number);
}
public static void main (String[] args){
List<Integer> sortedArray = new ArrayList<Integer>();
sortedArray.add(0);
sortedArray.add(0);
sortedArray.add(0);
sortedArray.add(1);
sortedArray.add(1);
System.out.println(getNumberCount(1, sortedArray));
}
}
binary search, O(log n)
function solver(array, s) {
var start = s!=undefined?s:0;
if (array.length == 1) {
if (array[0] === 0) {
return start + 1;
} else {
return 0;
}
}
var current = Math.floor(array.length / 2);
if (array[current] === 0) {
if (array[current+1] != undefined && array[current+1] === 1) {
return start+current+1;
} else {
return solver(array.slice(current),start+current);
}
} else {
if (array[current-1] != undefined &&array[current-1] === 0) {
return start+current;
} else {
return solver(array.slice(0,current), start);
}
}
}
There is a very obvious linear time solution. Go through the entire array and count the number of zeros.
I don't understand the point of the question? Does the examiner want a more efficient solution?
I believe the idea is to respond with the lgN solution rather than the linear one. Basically use a binary search to find the (0,1) pair and return the location of the 0 as the number of 0s (or location of the 1 with zero indexed arrays).
You're correct. So here's an implementation of it:
void findPivot(int * Arr, int length)
{
int L = 0;
int H = Lenght - 1;
int M = 0;
while(L < H)
{
M = (L + H)/2
if (Arr[M] != 0)
{
if (Arr[M-1] == 0)
{
//this is the proper index, since we have {....0,1,...}
cout << "Required index is" << M << endl;
}
else
{
H = M-1;
}
}
else
{
L = M + 1;
}
}
return;
}
This is a task for binary search. Time complexity is O(LogN).
- igor.s.sokolov June 16, 2015import java.util.Arrays; import java.util.Random; /** * Created by Igor_Sokolov on 6/16/2015. */ public class CareerCup_5766344614084608 { public static void main(String[] args) { int[] a = prepareData(10); System.out.println(Arrays.toString(a)); int pos = binarySearch(a); System.out.print(pos); } private static int binarySearch(int[] a) { int l = 0; int r = a.length - 1; while (l <= r) { int m = l + (r - l) / 2; if (a[m] < 1) { l = m + 1; } else { r = m - 1; } } return l; } private static int[] prepareData(int N) { final Random rand = new Random(); int[] a = new int[N]; for (int i = 0; i < N; i++) { a[i] = rand.nextBoolean() ? 1 : 0; } Arrays.sort(a); return a; } }