Amazon Interview Question Principal Software Engineers
Country: United States
How about this:
(1)use two HashSets instead of one HashMap, one for those numbers occurred odd times so far, let's call it oddSet, while the other for those occurred even times being evenSet.
(2)iterate to next number, if it has been in oddSet, we remove it from oddSet and add it to evenSet, otherwise we add it into oddSet and remove it from evenSet.
(3)finally, those numbers that occurred odd times are all in oddSet.
XOR works when there is exactly one number that occurs odd number of times and also there should not be any 0 in the array.
int getOddFreqNumber(int[] array) {
int oddFreqNumber = 0;
for (int i=0; i<array.length; i++)
oddFreqNumber = oddFreqNumber ^ array[i];
return oddFreqNumber;
}
why not doing it like sql? You can use group by the same number with count. Then return the number that has odd count? of course, if this is an interview, they probably won't let you use the easy and best way to do it unless you interview for microsoft.
Lambdas in C#
str.GroupBy(n => n).Select(s => new {num = s.Key, count = s.Count()}).Where(g => (g.count %2) != 0);
you can use Quaere in Java.
#include <stdio.h>
int getOddOccurrence(int ar[], int ar_size)
{
int i;
int res = 0;
for (i=0; i < ar_size; i++)
res = res ^ ar[i];
return res;
}
/* Diver function to test above function */
int main()
{
int ar[] = {2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2};
int n = sizeof(ar)/sizeof(ar[0]);
printf("%d", getOddOccurrence(ar, n));
return 0;
}
But it works only for +ve integers
//Find oddnumber in array
public Set<Integer> getListOfOddNumbers(int[] number)
{
Set<Integer> oddNumbersSet = new HashSet<Integer> (number.length);
if(number.length<0 || number==null)
{
return oddNumbersSet;
}
int i;
//Iterate each element in the array
for(i=0;i<number.length;i++){
if(oddNumbersSet.contains(number[i]))
{
oddNumbersSet.remove(number[i]);
}
else
{
oddNumbersSet.add(number[i]);
}
}
return oddNumbersSet;
}
//Find oddnumber in array
public Set<Integer> getListOfOddNumbers(int[] number)
{
Set<Integer> oddNumbersSet = new HashSet<Integer> (number.length);
if(number.length<0 || number==null)
{
return oddNumbersSet;
}
int i;
//Iterate each element in the array
for(i=0;i<number.length;i++){
if(oddNumbersSet.contains(number[i]))
{
oddNumbersSet.remove(number[i]);
}
else
{
oddNumbersSet.add(number[i]);
}
}
return oddNumbersSet;
}
//Find oddnumber in array
public Set<Integer> getListOfOddNumbers(int[] number)
Set<Integer> oddNumbersSet = new HashSet<Integer> (number.length);
if(number.length<0 || number==null)
return oddNumbersSet;
int i;
//Iterate each element in the array
for(i=0;i<number.length;i++)
if(oddNumbersSet.contains(number[i]))
oddNumbersSet.remove(number[i]);
else
oddNumbersSet.add(number[i]);
return oddNumbersSet;
//Find oddnumber in array
public Set<Integer> getListOfOddNumbers(int[] number)
Set<Integer> oddNumbersSet = new HashSet<Integer> (number.length);
if(number.length<0 || number==null)
return oddNumbersSet;
int i;
//Iterate each element in the array
for(i=0;i<number.length;i++)
if(oddNumbersSet.contains(number[i]))
oddNumbersSet.remove(number[i]);
else
oddNumbersSet.add(number[i]);
return oddNumbersSet;
//Find oddnumber in array
public Set<Integer> getListOfOddNumbers(int[] number)
Set<Integer> oddNumbersSet = new HashSet<Integer> (number.length);
if(number.length<0 || number==null)
return oddNumbersSet;
int i;
//Iterate each element in the array
for(i=0;i<number.length;i++)
if(oddNumbersSet.contains(number[i]))
oddNumbersSet.remove(number[i]);
else
oddNumbersSet.add(number[i]);
return oddNumbersSet;
//Find oddnumber in array
public Set<Integer> getListOfOddNumbers(int[] number)
Set<Integer> oddNumbersSet = new HashSet<Integer> (number.length);
if(number.length<0 || number==null)
return oddNumbersSet;
int i;
//Iterate each element in the array
for(i=0;i<number.length;i++)
if(oddNumbersSet.contains(number[i]))
oddNumbersSet.remove(number[i]);
else
oddNumbersSet.add(number[i]);
return oddNumbersSet;
//Find oddnumber in array
public Set<Integer> getListOfOddNumbers(int[] number)
Set<Integer> oddNumbersSet = new HashSet<Integer> (number.length);
if(number.length<0 || number==null)
return oddNumbersSet;
int i;
//Iterate each element in the array
for(i=0;i<number.length;i++)
if(oddNumbersSet.contains(number[i]))
oddNumbersSet.remove(number[i]);
else
oddNumbersSet.add(number[i]);
return oddNumbersSet;
//Find oddnumber in array
public Set<Integer> getListOfOddNumbers(int[] number)
Set<Integer> oddNumbersSet = new HashSet<Integer> (number.length);
if(number.length<0 || number==null)
return oddNumbersSet;
int i;
//Iterate each element in the array
for(i=0;i<number.length;i++)
if(oddNumbersSet.contains(number[i]))
oddNumbersSet.remove(number[i]);
else
oddNumbersSet.add(number[i]);
return oddNumbersSet;
A hash function associated with a linked list can be the best solution. Hash function uses number as a key and address of node in linked list as value. Hash function initialize its entries as NULL. If a number is not present in hash map ,add it to linked list and store its address in hash map.otherwise remove it from linked list.
Another approach:
Step 1. Heapify the numbers - O(log n)
Step 2. Read through each element: O(n)
- Since the items are already sorted, repeat items keep coming out one after the other.
- Count these. When number changes, determine if the previous number recurred odd/even number of times (counter's value) and print accordingly.
Overall time complexity: O(log n) + O (n) = ~O(n)
Additional Space : 0 if we can reuse the input array.
when you have a new number, just to search if it's already in the hashmap,
1) if it's in the hash map, delete it.
2) otherwise, add it to the hash map
At the end, all the numbers in the hash map should have odd occurrences.
I think O(n) lookup here means iterating through map to print odd frequency digits, which we have to somehow to get rid of. Your method doesnt get rid of that step.
You can do this using only one HashSet. Add new element to HashSet if its not already in the HashSet - else, remove it from the HashSet. This will make sure by the end of the iteration - the HashSet will only have the odd* occurring elements. Accessing elements in a HashSet is O(1) complexity. The overall time-complexity is O(n) for the linear traversal of the array elements.
- Jay February 27, 2014