Microsoft Interview Question Software Engineer / Developers
Team: Bing
Country: India
Interview Type: In-Person
If you are getting infinite number of bits then how can you count the number of set bits. This answer does not fulfill the criteria.
~Harjit
@Harit..
We can keep the difference with mod %3
for eg: if no. of set bit at odd position is 6 and no of set bet at odd position is zero we can reset the no of set bit at odd position to zero again since at this point number is divisivle by 3
so we don;t need to keep the infnite value we can reset the value once the no is divisible by 3
@Cartman
for prove
we can prove in similar way as we proved for divisibility of 11
abc =100a+10b+c = 99a +11b + (a-b+c)
(a-b+c) should be divisible by 11 inorder to make abc divisible by 11.
in the similar way we can prove for 3 also
I dont think this is correct. The input is an infinite stream of bits how do you handle sum overflow? You can't simply convert the number to 10-base.
A number is divisible by 3 if the sum of its digits can be divided by 3.
so have a buffer to add all the digits so at any point of time you can tell whether the number is divisible by 3 or not
void divisible_by3(bitstream bits) //hypothetical infinite stream of bits
{
int d = 0, bit;
for (;;){
bits>>bit;
d <<= 1;
d += bit;
d %= 3;
if (d == 0) {
cout<<"divisible";
} else {
cout<<"not divisible";
}
}
}
#include<iostream>
#include<conio.h>
using namespace std;
int main()
{
char c;
int even=0,odd=0
boolean flag;
while(cin>>c)
{
if(flag)
{
if(c=='1')
even++;
}
else
{
if(c=='1')
{
odd++;
}
}
flag=!flag;
}
if((even-odd)%3==0)
cout<<"Divisible by 3"<<endl;
else
cout<<"Not Divisible by 3"<<endl;
getch();
return(0);
}
The logic is as follow:
1. Every number can be expressed as n=3a+b where b<3.
2. Thus if we assume the current number we have is n and when a new binary character i comes, the new number is n'=n*2+i=6a+2b+i.
3. We can approve that if 2b+i is divisible by 3 then so is n'.
To sum up, we only need to record the remainder of current number (which is b) and when a new binary character i comes we check if 2b+i is divisible by 3. It will never overflow or have any other problems.
This was the solution i was looking for .
{{
void isbitstreamdivisible ()
{
int n = 0 ;int k =0;
while(T)
{
n= getbit();
if(k = (2k+n) %3 == 0)
printf ("Divisible by 3");
else
printf("not divisible by 3");
}
}
}}
make use of automata .... moore / mealey machine ,,, the interviewer probably wants to know just that and not how you will store an infinite stream of data or find its length
@Aryan Shah, I also took the way of using Deterministic Finite State Automata
/*assuming infinite input fed from command line*/
#include<stdio.h>
int main()
{
int input,state=0;
//state indicates the remainder when the stream is divided by 3
while(scanf("%d",&input)!=EOF)
{//assuming all time valid input is given
switch(state)
{
case 0: if(input==1) //initially remainder is 0 if 1 is pushed then clearly remainder should be 1 else it should remain 0
state=1;
break;
case 2:if(input==0) //initially remainder is 2 if 0 is pushed then clearly remainder should be 1 else it should remain 2
state=1;
break;
case 1:if(input==1) initially remainder is 1.if 1 is pushed then remainder is 0 and if 0 is pushed then remainder is 2.
state=0;
else
if(input==0)
state=2;
}
}
//if remainder=state=0 finally then the number
if(!state)
printf("Divisible");
else
printf("Not Divisible by 3");
}
int main()
{
int bit_stream=0, remainder=0;
while (TRUE)
{
bit_stream = get_bit();
remainder = remainder * 2 + bit_stream;
if( remainder % 3 == 0 )
{
printf("Divisible by 3");
}
else
{
if ( remainder > 3 )
remainder = remainder % 3;
}
}/*while loop close*/
}/*main close*/
Test Cases:
Pass Test Cases: 1111, 1100, 10101
Fail Test Cases: 101, 111
Count the number of set bit at even and odd position .....if their difference is divisible by 3 then number is divisible by 3
- NaiveCoder March 17, 2012