Amazon Interview Question: Given a list of n numbers. Al... | Glassdoor

Interview Question

Software Development Engineer In Test Interview Seattle, WA

Given a list of n numbers. All numbers except one are

  unique. Find the number with duplicate entry.
Answer

Interview Answer

10 Answers

0

I gave an nlogn solution, where I said we will heap sort / quick sort the array, and then do a linear traversal to find out the duplicate entry. The interviewer was okay with the solution, and then she asked me code it, and then to write test cases for it.

Interview Candidate on May 20, 2010
0

How about using hashtable?

Anonymous on May 27, 2010
1

Use the function n(n+1)/2 = sum(0,n). Sum up all of the numbers in the array. Subtract the number from the function from the number in given by the sum. That will be your duplicate entry.

public static int dupeNum ( int [] array ){
  int arraySum = 0;
  int arraylength = array.length;
  int knownSum = (arrayLength * ( arrayLength + 1 ) ) / 2;
  for (int i : array ){
      arraySum += array[i];
  }
  return (arraySum - knownSum) ;
}

Should be O(n).

Anonymous on Jul 19, 2010
3

^^ person who replied above: Your solution fails if the numbers aren't sequential - for all you know, 'a list of n numbers' could be 'n' random numbers

Dopey on Jul 23, 2010
4

Merge sort it and then it iterate through the list. This takes nlogn time.

public in getDuplicate(List list) {
    List sortedList = Mergesort(list);
    for(int i = 0; i < sortedList.length-1; i++)
                  if(sortedList[i] == sortedList[i+1])
                              return SortedList[i];
    Throw exception;
 }

Rick on Mar 17, 2011
6

take XOR of all the numbers.You will get the sum with out the duplicated number.

(sum of all n - above sum) will give you the number

Anonymous on Mar 3, 2012
1

put the numbers into hashmap while traversing the list. Before placing the key into hashmap check whether it is null or not. if it isnot you've found it. worst case O(n). extra hashmap in the memory.

workStudy on May 7, 2012
0

i would sort them in n log and then traverse them. while traversing, chech two adjacent numbers are different. if not, that is the number.

Anonymous on Dec 12, 2014
0

Construct a binary search tree with the given number.when u find a duplicate number return from the method as in binary search tree one has to put element either left or right.

Anonymus on Oct 1, 2017
0

Construct a binary search tree with the given number.when u find a duplicate number return from the method as in binary search tree one has to put element either left or right.

Anonymus on Oct 1, 2017

Add Answers or Comments

To comment on this, Sign In or Sign Up.