FlexTrade Interview Question
Software Engineer / DevelopersWhy do you have to make things complicated? You going to write a bsearch for this?
You can just run through it once, know that it's N 1s (or 0s), then minus it by the total array elements since it's an array.. or vec.size(), if they need to know the remainder.
the reason binary search is SPEED.
BSearch will get answer in log(n) searches.
Looping through will require n/2 operations in avrg case. And worst case is n operations
Binary search wont guarantee the first instance of the value .best would be count one occurrence and subtract it from the length
Quote - " either 1 or 0 , and they are in sorted order Ex. a [] = { 1,1,1,1,0,0,0}"
Sorted order ..so shouldn't it be a[] = { 0,0,0,1,1,1,1} instead of 1s first. hello?
They need to phrase it correctly. sigh what's the happen with these interviewers..or is sachinsaner interpret or wrote it wrong.
I believe that this solution will be correct:
public class Test_CheckNumberOfDigitsInArray
{
public static void main(String[] arghs)
{
int a [] = { 1,1,1,1,0,0,0};
int noOfOnes = 0;
int noOfZeros = 0;
for (int i=0; i<a.length; i++)
{
switch (a[i])
{
case 1:
noOfOnes += 1;
break;
case 0:
noOfZeros += 1;
break;
}
}
System.out.println("Number of 1's is " + noOfOnes
+ " and number of 0's is " + noOfZeros);
}
}
#include<iostream>
using namespace std;
int binary_search(int* arr,int low,int high){
if(high<low) return -1;
int mid = (low + high)/2;
if(arr[mid]==0 && (mid-1<0 || arr[mid-1]==1)){ // First element
return mid;
}
else if(arr[mid]==0){ // Left search
return binary_search(arr,low,mid-1);
}
else{ // Right search
return binary_search(arr,mid+1,high);
}
}
int main(){
/* I am assuming that there are no integers apart from 0 and 1 */
int arr[]={1,1,1,1,0,0,0}; // Given case
/*
int arr[]={1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0}; // More of the same
int arr[]={0,0,0,0,0,0}; // Edge case
int arr[]={1,1,1,1,1,1}; // Edge case
int arr[]={}; // Edge case
*/
int len = sizeof(arr)/sizeof(int);
auto elem = binary_search(arr,0,len-1);
if(elem==-1 && len!=0){ // Edge case where arr has all ones
cout<<"Number of one's is "<<len<<" and number of zeros is 0"<<endl;
}
else if(elem==-1){
cout<<"There are no elements present"<<endl;
}
else{
cout<<"Number of one's = "<<elem<<" and number of zero's = "<<len-elem<<endl;
}
return 0;
}
read first element of array to determine whether its 1 or zero.
- Anonymous March 30, 2010start binary search depending on above result in order to find end of 1 or zero