Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
//the solution given works only when the range of numbers in the array is not more than n,i have taken assumption that range is between 0 to n-1. solution is O(n) time and O(1) space.
//
void no_odd_times(int arr[],int n)
{
//assuming array has no.s between 0 to n-1;
int max = n;
int i;
for(i = 0; i < n; i++)
arr[(arr[i]%n)] += n;
printf(" The no.s occuring odd times with their respective count are:\n");
for(i = 0; i < n; i++)
{
if(arr[i] < n)
continue; //means no one added n to this place so i doesn't occur at all
//now arr[i] >= n
if((arr[i]/n) & 1) //no. of times n is added is odd
printf(" %d ,count:%d\n",i,arr[i]/n); //arr[i]/n is the count of i
}
}
Can you explain me about your algorithm with the following array
{1,3,5,7,1,3,5,7,2,4,5,7}
what i have done is since the elements are from 0 to n-1 and so are indexes in the array,so at a particular index i, use the value to modify its actual place by adding maximum value(n) had we have a sorted and distinct array of n elements .mod is taken because the current element might be modified i.e added n one or many times by elements before visited i.e from index 0 to i-1. After doing this ,visit the elements ,if it is < n means no one added anything else divide by n to check the no. of times n is added . i hope now everything is crystal clear
we can use XOR to partition the array recursively, the base case is all elements in current partition is identical, then, if the size of this partition is odd, print the first elements of the partition.
void print_quick(const vector<int> &array, int mask, int partition_mask)
{
if (array.empty()) return;
int i = 0;
for (; i < array.size() ; i ++)
{
if (mask==0)
{
break;
}
if (((array[i]&mask)^partition_mask)==0)
{
break;
}
}
if (i>=array.size()) return;
int first = array[i];
int r = 0;
int cnt = 1;
i++;
for ( ; i < array.size() && r==0 ; i ++)
{
if (((array[i]&mask)^partition_mask)==0)
{
cnt ++;
r = first^array[i];
}
}
if (r==0)
{
if ((cnt&0x1)==0x1)
{
printf("%d ",first);
}
return;
}
int partition = 1;
while ((r&partition)==0)
partition <<= 1;
mask |= partition;
print_quick(array,mask,partition_mask|partition);
print_quick(array,mask,partition_mask);
I believe in case when there are several odd numbers you can solve it in two ways:
1) The one which you have already mentioned using HashSet-Time O(n), Space O(n)
2) Sort the array and then iterate keeping the running counter of the current number. When you reach a new number check if the counter is odd and print number if it is. Time O(nlogn), Space O(1)
Sorting the original array , distort the original array so it depends on question .
Like to add one more method using modified algo for Binary search tree and keep pointer of count on each node. Print any traversal with node having count odd
Time Complexity : o(nlogn)
space complexity o(n)
best algo will be sorting only o(nlogn) . we can use heap sort or Quick sort. as count sort requires o(n) space.
Only 1 bit is required to store whether the number has occurred odd number of times. So if all the numbers in the list are positive, then we have 1 bit in each array index. When iterating through the array, read the value 'x' after ignore the most significant bit (since it indicates odd or not), index into the array at position 'x' and toggle the most significant bit.
- Avinash February 05, 2014Then go through the array again and if the most significant bit is set, then the corresponding index has occurred odd number of times.