Amazon Interview Question Software Engineer / Developers
XOR won't work for [2,4,6,6] = 6
In good software engineering practices you should validate your arguments and in this case the cost of validation is the same as using the map solution
Sure it wouldn't work. 'cause only one integer must appear an even number of times. In your case, [2, 4, 6, 6], two integers (2 and 4) appear only 1 time. This example works fine - [2, 4, 2, 6, 6]. The answer is 4.
XOR is a solution if you can validate the input in O(n) time and O(1) space... I don't think that's possible
We can use a hashmap where key is the number and value is a bit.
1. Start traversing the array and pushing into the hashmap
2. If no key found with the number being traversed push into hashmap with value 0
3. If a key is found for the number being traversed just alter the state of the value (i.e., 0 if 1 and 1 if 0)
4. Parse the hashmap once to find:
a.) 0, if we are looking for one number which is repeated even number of times.
b.) 1, if we are looking for one number which is repeated odd number of times.
Use hashtable
during the 1st scan of the array, check wat is returned from
object o=hashtable.get(arr[i])
if o is null then hashtable.put(arr[i], odd)
if o==odd, then hashtable.put(arr[i], even)
if o==even, then hashtable.put(arr[i],odd)
finally scan the array and return arr[i] for whichever the hashtable.get(arr[i]) returns even.
IS there any way to find the reverse.i.e. All but one appears odd no of times.And we have to find the element which appears even no of times?
Why cant we write a simple code like this...
#include <stdio.h>
#include <conio.h>
#define N 10
int main()
{
int a[N]={1,2,3,1,2,4,9,3,6,6},temp,cnt;
for(int i=0;i<N;i++)
{
temp=a[i];cnt=0;
for(int j=0;j<N;j++)
{
if(a[j]==temp)
cnt++;
}
if(cnt%2!=0)
printf("%d\n",a[i]);
}
getch();
return 0;
}
Why cant we write a simple code like this...
#include <stdio.h>
#include <conio.h>
#define N 10
int main()
{
int a[N]={1,2,3,1,2,4,9,3,6,6},temp,cnt;
for(int i=0;i<N;i++)
{
temp=a[i];cnt=0;
for(int j=0;j<N;j++)
{
if(a[j]==temp)
cnt++;
}
if(cnt%2!=0)
printf("%d\n",a[i]);
}
getch();
return 0;
}
Basic bit manipulation problem:
- Anurag Singh February 04, 2011Just XOR all the elements in the given array, output will be the no which appeared in array an odd number of times.
answer=a[0];
for(i=1;i<array.length;i++)
answer ^= a[i];
printf("answer=%d\n",answer);