## Microsoft Interview Question for Interns

• 0

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
of 8 vote

I gave the following solution using bit vector:

``````public static void Beep(int[] a) {
int prev = 0;
int res;
for (int i = 0; i < a.length; i++) {
res = prev ^ (1 << a[i]);
if (res > prev) {
System.out.println("beep");
} else {
System.out.println("no beep");
}
prev = res;
}
}``````

I have XOR because when the number is repeated even times then 1 flips to 0 which causes decrease in the value. correct me if am wrong. :)

Comment hidden because of low score. Click to expand.
2

Your solution will work only for +ve integers, and less than 32.

Comment hidden because of low score. Click to expand.
0

You can use bit vector to switch between odd/even occurences, but this won't be O(1) space. The same if you just use 'res' as indicator for values in range [0; 30].

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

Why do people use bit-vectors whenever constant space is required ? A bit-vecotr of N bits takes O(N) space, just like any vector of N items.

Comment hidden because of low score. Click to expand.
0

but in this case its a const space as the input is a 32 bit integer and if u create a bitmap for that it takes 512MB which is independent of number of elements to be analysed and hence constant space

Comment hidden because of low score. Click to expand.
0

Your algorithm don't work for this sequece: 1,33. and the reason is obvious

Comment hidden because of low score. Click to expand.
0

Can't we use And operation???

``````for (int i = 0; i < a.length; i++) {
res = prev & (1 << a[i]);
if (!res ) {
System.out.println("beep");
res|=prev;
} else {
System.out.println("no beep");
res^=prev;
}
prev = res;
}``````

Comment hidden because of low score. Click to expand.
0

Above comment is erroneous
for (int i = 0; i < a.length; i++) {
res = prev & (1 << a[i]);
if (!res ) {
System.out.println("beep");
prev|=(1<<a[i]);
} else {
System.out.println("no beep");
prev^=(1<<a[i]);
}
prev = res;
} }}}

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

``````byte[] a = new byte[10];
int[] num;
Console.WriteLine("Number of integers to enter");
int n = Convert.ToInt32(Console.ReadLine());
num = new Int32[n];
Console.WriteLine("Entet array of integers");
for (int i = 0; i < n; i++)
{
}
for (int i = 0; i < n; i++)
{
if (a[num[i]] == 0)
{
Console.Write("beep ");
a[num[i]] = 1;
}
else if (a[num[i]] == 1)
{
Console.Write("NoBeep ");
a[num[i]] = 0;
}
}
}``````

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

most important question to ask the interviewer here is the range of numbers and whether the numbers are positive or negative.Only then can it be decided whether O(1) space is actually feasible.

Comment hidden because of low score. Click to expand.
1
of 5 vote

``````void main()
{
for (i=0;i<n;i++)
{
count = 0;
for(j=0;j<=i;j++)
{
if (a[j]==a[i])
{
count ++;
}
}
if (count %2 == 1)
{
puts ("beep");
}
else
{
printf("no beep")
}

}

}``````

Comment hidden because of low score. Click to expand.
0

This solution is correct but has O(n^2) complexity.
Is this acceptable?

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

probably not the optimal answer since it's infinite

Comment hidden because of low score. Click to expand.
0

No where in the question does it say its array. Its infinite stream of numbers. One solution could be to use lookup table of size 2^32,

Comment hidden because of low score. Click to expand.
0
of 2 vote

``````int main()
{
int arr[]={1,4,2,4,3,2,4,4,5,3,3,2};
int size=sizeof(arr)/sizeof(arr[0]);
int index=1;
for(int i=0;i<size;i++)
{
int temp=1;
temp=temp<<arr[i];
if(index & temp)
printf("No beep\n");
else
printf("beep\n");
index=index^temp;
}
getchar();
return 0;
}``````

Comment hidden because of low score. Click to expand.
0

nice algo

Comment hidden because of low score. Click to expand.
0

if the integer range between 1~32.

Comment hidden because of low score. Click to expand.
0

Yes.. you are right.. I have only given the method for large range you have take the array and divide in 32bit per array index and follow this logic..

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

But you solution will treat 1 and 33 as same (with 4 bytes of integer representation) and report incorrect answer, if the sequence is something like this [1, 2, 33]

Comment hidden because of low score. Click to expand.
0

I am confused and trying to understand. When we have array []{4,2,4,3,2,4,4,5,3,3,2} and we are at index 0 we need to print beep. But at this time we do not know how many 4s are in the array, because we haven't traverse to take the count of 4s
How will this give beep

{
res = prev ^ (1 << a[i]);
if (res > prev) {
System.out.println("beep");
}

}

Lee

Comment hidden because of low score. Click to expand.
0

@lee: basically you set the corresponding bit for that number and if it is encountered again then it will be reset.
such as:
if number is 3,4,3
first loop: check if 3rd bit is set?If not set then set 3rd bit
second loop: check if 4rd bit is set?If not set then set 4 bit
third loop: again you find out 3 then you check if 3rd bit is set.It means that you have encountered it 2nd time which means it occured even number of times(2 is even number).
So keep on doing this for all the numbers.

Comment hidden because of low score. Click to expand.
0

well, nice logic but this don't work for,
- zero's
- number range issue

I am just thinking to avoid this issues, if ou got any thought pls share..

Comment hidden because of low score. Click to expand.
0

set initial value of variable index to zero then issue with zero values will be resolved, and to avoid number range issue we must use seperate variables to store each bit status which is not acceptible in terms of memory.

Comment hidden because of low score. Click to expand.
0

I had a similar Q in MS interview and i suggested the bit vector for each integer of a 32 bit integer... in my case the memory constraint was 1GB and if you create a bit vector it consumes 512 MB only and he said that its correct

Comment hidden because of low score. Click to expand.
0

why it's 512MB only? any constraints on the range of integers?

Comment hidden because of low score. Click to expand.
0

Hey Vik,
32 bit doesn't consume 512MB memory if you just use 32 bit to represent integer caz integer just need 32 bit, right?

My idea is like this:
{1,4,2,4,3,2,4,4,5,3,3,2}
each time we receive a new int, we scan the whole array from start to end. We use bit vector to indicate which number is monitoring now and another bit to indicate odd or even. Totally, 33 bit.
eg:
1,4,2,4 last number is 4.
we set bit vector to 28's 0+0100, EvenOddBit = 0
we come across the first 4, EvenOddBit = 1;
we come across the second 4, EvenOddBit = 0;
at last EvenOddBit = 0, no beep;

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

i dont find any wrong in it... there is no time complexity asked for this question. hence only time complex matters

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

Space complexity O(1)?

I presume you are given constraints on the size of the numbers. Otherwise O(1) space is impossible...

And if you are given bounds, you can just use a bitvector and be done with.

Comment hidden because of low score. Click to expand.
0
of 2 vote

for infinite sequence of array with poitive integers...
code should be

``````func(int[] a){
int i=0;
while(true){
if(a[abs(a[i])] == abs(a[abs(a[i])]))
printf("beep");
else
printf("no beep");
a[abs(a[i])] = (-1) * a[abs(a[i])];
i++;
}
}``````

Comment hidden because of low score. Click to expand.
0

this code fail if the input a = [10, 4, 2, 4, 3, 2, 4]

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

probably some set of the math formulas can be used for the O(1) solution and wide range of integers, subscribing to the thread

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

Here is an algorithm with a BitSet, not O(1) space as well. Not sure if we can do better (in O(1) space complexity).

``````public static void beep(int[] a) {

final BitSet set = new BitSet();

for (int i = 0; i < a.length; i++) {

if( set.get( a[i] ) ){
System.out.println("no beep");
set.clear( a[i] );
}
else {
System.out.println("beep");
set.set( a[i] );
}
}
}``````

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

Does infinite sequence here, mean we are given a stream of integers to be taken one by one..if its given in the form of an array as assumed in the above answers, it doesn't really match the problem descriptions. Please clarify.

Comment hidden because of low score. Click to expand.
0
of 4 vote

void func()
{
int xor=0,x; //x is the input

While(true)
{

if((xor & x) == x)
{
printf("beep\n");
}
else
printf("not beep\n");
xor = xor^x;
}
}

Comment hidden because of low score. Click to expand.
0

This is a right idea. I'm not sure why we need an infinite loop here but all other is good.

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

How could this be right? It can not get the right result even with input sequence of "1, 2, 3".

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

``````void beep_unbeep (int num)
{
static int save = 0;
int temp = 0;

temp = num;
temp = temp ^ save;

if (temp) printf("\nno_beep");
else printf("\nbeep");

save = save ^ num;
}``````

this should do i believe.

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

``````void Beep2(int a[])
{
map<int,int> map;
for(int i = 0; i < 9; i++)
{
if(map[a[i]] = 1){
cout<<"no beep\n";
map[a[i]] = 0;
}
else{
cout<<"beep\n";
map[a[i]] = 1;
}
}``````

}

Comment hidden because of low score. Click to expand.
0
of 2 vote

``````class Program
{
public byte[] a = new byte[10];
public int[] num;

static void Main(string[] args)
{
Program obj = new Program();
obj.beep();
}

public void beep()
{
byte[] a = new byte[10];
int[] num;
Console.WriteLine("Number of integers to enter");
int n = Convert.ToInt32(Console.ReadLine());
num = new Int32[n];
Console.WriteLine("Entet array of integers");
for (int i = 0; i < n; i++)
{
}
for (int i = 0; i < n; i++)
{
if (a[num[i]] == 0)
{
Console.Write("beep ");
a[num[i]] = 1;
}
else if (a[num[i]] == 1)
{
Console.Write("NoBeep ");
a[num[i]] = 0;
}
}
}
}``````

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

``````#include<stdio.h>
#define CHECKBIT(var, pos) ((var)&(1<<(pos)))
main()
{
int a[]={1,2,4,2,3,4,5,4,1,6,7};
int checkvector = 0;
int n=sizeof(a)/sizeof(int);
int i;
for (i=1;i<=n;i++)
{
if(CHECKBIT(checkvector,a[i-1]))
{
printf("NoBeep ");
checkvector&=~(0x1<<a[i-1]);
}
else
{
printf("Beep ");
checkvector|=(0x1<<a[i-1]);
}
}
}

Output : Beep Beep Beep NoBeep Beep NoBeep Beep Beep NoBeep Beep Beep``````

Assuming the number range is only 0 to 32.

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

Why not just sort the array first? Then we can easily keep track of how many of a particular number there are. The bit vector solution doesn't seem to work too well if we can have values between -(2^32 -1) to 2^31-1

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

Questions that we need to ask interviewer.
1. What is the range of integer?
2. Could the number be positive or negative?
3. How many memory do we have?
4. What does O(1) mean? Does it include input space?

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

if the range of the number is between 0 and 9 then this too could be an optimal soln:
#include<stdio.h>
int main()
{
int a[10],i,m,n;
static int b[10];
printf("enter the number of elements of the array:\n");
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n;i++)
if(++b[a[i]]>1)printf("\nno beep");
else printf("\n beep");
return 0;
}

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

void main()
{
int n,a[20],b[20],count[20];
printf("enter the value of n");
scanf("%d",&n);
printf("enter the elements");
for(i=0;i<=n;i++)
{
count[i]=0;
scanf("%d",&a[i]);
}
b[0]=a[0];
count[0]=1;printf("beep");
for(i=0;i<=n,i++)
{
for(j=0;j<=n;j++)
{
if(a[j]==b[j])
{{count[j]++;}
if(count[j]%2==0)
printf("no beep");
else
printf("beep");
}
else
{
b[j]=a[i];
count[j]=1;
printf("beep");
}
}

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

I think this might work. Not sure though but it has O(n) time complexity and O(1) space complexity. The earlier posted solutions with bit-vectors still have O(n) complexity.

The strategy is simple. Define a function f(n) which produces a unique prime number for n. I believe there are a few functions available which can do this for very large n. Now all you have to do is keep a count variable of sorts. In the sequence, every time you see a number x, you check if count%f(x) is zero, and if so, print 'not beep' and set count to count/f(x). Else, print 'beep' and set count to count*f(x).

This should work as the prime factors of any number are unique. You may run into overflow problems with large number of variables but these are issues with programming and not the actual algorithm. It will still be O(1).

Comment hidden because of low score. Click to expand.
0

Actually nevermind, we can only generate unique prime for values 1 to 57 in O(1) time right now so this might not be the most efficient algorithm. I am not sure about the time complexity of generating numbers bigger than that but it should be bounded around O(logK) or O(sqrt(K)) or worst case O(KlogK) where K is the largest number you want a prime number for. Then, depending on the range, we might still be able to come up with a somewhat efficient algorithm.

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

I think this might work. Not sure though but it has O(n) time complexity and O(1) space complexity. The earlier posted solutions with bit-vectors still have O(n) complexity.

The strategy is simple. Define a function f(n) which produces a unique prime number for n. I believe there are a few functions available which can do this for very large n. Now all you have to do is keep a count variable of sorts. In the sequence, every time you see a number x, you check if count%f(x) is zero, and if so, print 'not beep' and set count to count/f(x). Else, print 'beep' and set count to count*f(x).

This should work as the prime factors of any number are unique. You may run into overflow problems with large number of variables but these are issues with programming and not the actual algorithm. It will still be O(1).

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

``````void function(int arr[], int size)
{
for(int i=0;i<=size;i++)
{
if(arr[arr[i]>0?arr[i]:-1*arr[i]] > 0)
cout<<"  beep "<<endl;
else
cout<<" no beep "<<endl;
arr[arr[i]>0?arr[i]:-1*arr[i]] *= -1;
cout<<endl;
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

better to use the HashMap and insert value if not exists and print "beap" otherwise print "no beap"

Comment hidden because of low score. Click to expand.
0

It is an infinite sequence of integers

Comment hidden because of low score. Click to expand.
0

You can't assume HashMap would be Space O(1) - in fact it will be O(n).

Comment hidden because of low score. Click to expand.
0

if use hashmap, u need to use someother count variable as well and simple lookup is NOT sufficient.

Comment hidden because of low score. Click to expand.
0

Hashset, might work for infinite numbers as well. It will have O(1), but a rather big constant, because if it is an infinite 'int' array we can have at most 4 billion values. :P

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.

### 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.