## Amazon Interview Question for Interns

• 0

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
6
of 8 vote

Here is a simple pythonic answer

``````def find_odd_occurences( elements ):
odd_occurences = set()
for e in elements:
if e in odd_occurences:
odd_occurences.remove(e)
else:

return odd_occurences``````

Comment hidden because of low score. Click to expand.
0

I think they are looking for a logic to find out how will you find odd occurences rather than finding out if you know how to call api's.

Comment hidden because of low score. Click to expand.
0

@aka[1] Where in God's name did he use API's? If you don't get the code don't comment.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Simplest way is to use hashing and XOR.
I'll just use an array, since there are no space restrictions in the question.

Pseudocode:

``````arr[0 .. MAX] = 0;        // initialize with 0

for n in set:
arr[n] = arr[n]  XOR 1;     // XOR will toggle the content between 0 and 1
// 0 occurences: 0;
// 1st occur: 1;
// 2nd occur: 0;
// 3rd occur: 1; etc ...

for n in {0 .. MAX}:
if arr[n]:			  // if NOT 0, then occurred odd number of times
print n;``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public void TestMethod3(int [] arrayofnumbers)
{
Dictionary<int, int> numberAndOccurance = new Dictionary<int, int>();
foreach (int number in arrayofnumbers)
{
try
{
}
catch (ArgumentException)
{
numberAndOccurance[number] = numberAndOccurance[number] + 1;
}
}
foreach (var outNo in numberAndOccurance)
{
if (outNo.Value % 2 == 1)
Console.WriteLine(outNo.Key);
}
}``````

}

Comment hidden because of low score. Click to expand.
0

if you want to have the result set sorted in ascending order.
the use Data Type SortedDictionary

``````public void TestMethod3(int[] arrayofnumbers)
{
SortedDictionary<int, int> numberAndOccurance = new SortedDictionary<int, int>();
foreach (int number in arrayofnumbers)
{
try
{
}
catch (ArgumentException)
{
numberAndOccurance[number] = numberAndOccurance[number] + 1;
}
}
foreach (var outNo in numberAndOccurance)
{
if (outNo.Value % 2 == 1)
Console.WriteLine(outNo.Key);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int main(int argc, char** argv)
{
int a[] = {1, 2, 1, 3, 2, 4, 4, 5, 4};
int N = sizeof(a) / sizeof(*a);

map<int, int> count;

for (int i = 0; i < N; i++) {
if (count.find(a[i])!= count.end())
count[a[i]]++;
else
count[a[i]] = 1;
}

for (map<int,int>::iterator iter = count.begin(); iter != count.end(); iter++) {
if (iter->second % 2)
cout << iter->first << " ";
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

void findOdd(int[] arr)
{
Hashtable ht = new Hashtable();
for (int i = 0; i < arr.Length; i++)
{
ht[arr[i]] = 0;
}

for (int i = 0; i < arr.Length; i++)
{
ht[arr[i]] = (int)ht[arr[i]] + 1;
}

IDictionaryEnumerator ide = ht.GetEnumerator();
while (ide.MoveNext())
{
if (((int)ht[ide.Key]) % 2 == 1)
{
Console.Write(ide.Key+" ");
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

If the number is not very big, I'd like to use bitmap.
Less memory than hashmap and in same speed.

Comment hidden because of low score. Click to expand.
0
of 0 vote

If numbers are not in any specific range, I think the solution would be through Hashtable. But, if the numbers are in range 1 to n where n is the size of array, it could be done in constant space and O(n) time.

Logic:

``````//keep flipping the sign of numbers
for (int i=0; i<n; i++) {
arr[ Math.abs(arr[i]) ] = - arr[ Math.abs(arr[i]) ];
}

//odd numbers will be the negative numbers in array
for(int i=0; i<n; i++) {
if(arr[ Math.abs(arr[i]) ] < 0)
System.out.println(Math.abs(arr[i]));
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a pretty straight forward question. Let me know if you find anything wrong with this code. C++. Should be pretty easy to following along too.

``````int x[] = {1,2,3,4,2,3,4,5,6,7,5,4,4,5,4,5,6,7,8,8,6,5,4,3,2,3,4,5,6,7,8,8,3,4,};
std::map<int,int> m;

for(auto i : x){
m[i]+=1;
}
for(int i = 0; i<m.size();i++){
if(m[i]%2==1){
std::cout<<i<<" appears an odd amount of the time in the set."<<std::endl;
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Use XOR operator. Sequentially XOR all the numbers. And at the end (assuming only one number has odd number of occurrences) the number with odd number of occurrences will remain.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

best and simplest!

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Idiots.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.