CareerCup

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

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

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.

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

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

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.

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

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

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

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.

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

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.

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

}

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.

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

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?

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

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

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

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