Amazon Interview Question: Given an array of integers, a... | Glassdoor

Interview Question

Software Development Engineer Interview Seattle, WA

Given an array of integers, all but one of which appears an

  even number of times, find the one integer which appears an odd number of times.
Tags:
data structures, algorithm
Answer

Interview Answer

3 Answers

2

I answered him that we can do a XOR, and then he asked me to it in another way and wanted me to write a code, read out so that he could note it. I wrote the code using HashMap.

Interview Candidate on Feb 1, 2011
0

XOR fails for an invalid input [2,4,6,6] as it will return 6.
You should validate your args and in this case the cost of validating your args is the same as obtaining the solution

e on Feb 4, 2011
1

Create a hash set.
Iterate through the array.
        If the set contains this value already, remove it
        Else add the value to the set

In the end, if a value was in the array an even number of times, it is no longer in the set. Otherwise, it's still in the set. After iterating through the array, the set will contain only one value, the one that was repeated an odd number of times.

K on Aug 8, 2011

Add Answers or Comments

To comment on this, Sign In or Sign Up.