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
data structures, analytical

Interview Answer

7 Answers


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

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

Anonymous on Mar 25, 2011

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

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

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

Tellig about zero is an excellent catch.. +1

Anonymous on May 4, 2015

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 => x).Where(y => y.Count() == 1).Select(y => y.Key); //Ans = {4}

Gunjan on May 19, 2015

Add Answers or Comments

To comment on this, Sign In or Sign Up.