Amazon Interview Question: Given a (potentially large) a... | Glassdoor

## Interview Question

Software Engineer Interview Seattle, WA

# Given a (potentially large) array of integers, all but one

repeating an even number of times, how would you find the one repeating an odd number of times in an efficient way? eg [1 2 3 3 2 2 1 4 2] should return 4
Tags:
data structures, analytical

0

Use any collection data structure to insert and remove the numbers, such that at the end the only one remaining will be the one repeated an odd number of times.
For example we can use a tree. We consider on number at the time. We first search for the number in the tree. If found, we will remove it. Otherwise, we will insert it. At the end, the number (or the numbers, in general) repeated an odd number of times will be in the tree. For the complexity it is necessary to perform an amortized analysis.
Another data structure that we can use is the hashmap. However, the space consumption and management could be high, if the map automatically resizes.

Interview Candidate on Mar 23, 2011
7

Ex-or the numbers. For the odd occurrence, the ex-oring will not result in zero.

Anonymous on Mar 25, 2011
0

Ex-oring is a great idea, one other solution is to sort the array and then in one pass you can find out the number that occurs odd number of time
with quicksort avg case nlogn and worst case n^2

Anon on May 3, 2011
1

Few steps of counting sort can help us do it in O(n) time.

Step I: find min and max, thus the range
Step 2: initialize array of the range with 0
Step3: as numbers come in, increment the a[number] by 1.
Step4: scan the array to find the odd number.

Sanchay Subhedar on Jan 1, 2012
1

Ex-or is a good solution only if 0 is not in the input list. If 0 occurs odd number of times, not sure it will report it.

x on Jun 19, 2013
0

Tellig about zero is an excellent catch.. +1

Anonymous on May 4, 2015
0

by using LINQ it can be acheived.

var numList = new List() {1 ,2, 3, 3, 2, 2, 1, 4, 2 };
var oneOccurance = numList.GroupBy(x =&gt; x).Where(y =&gt; y.Count() == 1).Select(y =&gt; y.Key); //Ans = {4}

Gunjan on May 19, 2015