## Microsoft Interview Question

Interns**Country:**United States

**Interview Type:**In-Person

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

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.

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

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;
}
```

```
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++)
{
num[i] = Convert.ToInt32(Console.ReadLine());
}
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;
}
}
}
```

```
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")
}
}
}
```

```
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;
}
```

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

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]

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");

}

}

Please help me understand. Thanks

Lee

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

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

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.

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

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;

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++;
}
}
```

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] );
}
}
}
```

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;

}

}

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

```
class Program
{
public byte[] a = new byte[10];
public int[] num;
static void Main(string[] args)
{
Program obj = new Program();
obj.beep();
Console.ReadLine();
}
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++)
{
num[i] = Convert.ToInt32(Console.ReadLine());
}
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;
}
}
}
}
```

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

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;

}

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");

}

}

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

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.

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

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

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

I gave the following solution using bit vector:

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. :)

- learner February 10, 2013