Amazon Interview Question: A list with a set of integers... | Glassdoor

Interview Question

Senior Software Engineer Interview Seattle, WA

A list with a set of integers. All elements appear even

  number of times while one appear odd number of times. Find this number that appear odd number of times

Interview Answer

6 Answers


use a counter for the number of times the digit appear

Interview Candidate on Sep 3, 2011

Suppose a list of integers: A[1..n]
We can calculate the result of A[1] xor A[2] xor ....A[n]
This is the answer!

Hong Sun on Sep 5, 2011

Use a HashSet. For each number in the list check to see if it exists in the HashSet. If it doesn't, put it in the HashSet. If it's already in the HashSet take it out. When you've gone through all the numbers the only number left in the HashSet will be the one that appeared an odd number of times.

Anonymous on Oct 5, 2011

1. sort the numbers
2. then do what hong sun does.

RK on Dec 8, 2011

// Requires that all the elements appear even # times except exactly 1:

int findOddEntry(List list)
  int xorBuffer = 0;
  for (int i : list)
    xorBuffer ^= i;
  return xorBuffer;

S on May 26, 2016

adding/deleting entry into an object for every value. In the end only the key with odd occurrences will be left since all even will removed. For even, first occurrence add into object, second one remove.

Anonymous on May 1, 2017

Add Answers or Comments

To comment on this, Sign In or Sign Up.