Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
Better approach would be to just sum up the array elements and subtract n(n+1)/2 from it. This approach ofcourse assumes the there is only one duplicate.
Your solution does not work.
Your solution work if all the elements are present from 1 to n except. and finding this missing one.
That can also work in that case also.
but it will fail in case of large numbers where n*(n+1)/2 will go out of bounds
@tanvi can you illustrate when this does not work ?
@nitin You are right. however, you have to choose a bigger datatype than what we are summing together. I was just outlining the algo.
The best answer is use XOR
time complexity : O(n) - 1 iteration
space complexity : O(1)
int xor=0;
for (int i=0;i<array.length-1;i++){
xor=xor ^ i ^ arr[i]
}
The final value is duplicate value.
@ analog76: your solution will not work for the case 1 2 3 2 5
according to your code it would be (2^4)=6 not 2.
and if last element is missing then ans would be 0.
To find out 2 and 4 separately we need to divide set (0,1,2,3,4,1,2,3,2) in two parts according to least active bit of ans(here 6)(110).
so we can separate them 2 groups having 2'nd bit from right 0 and 1. groups are {0,1,1,4}and {2,3,2,3,2}
then take XOR of both groups to find out 4 and 2 separately.
This could be solved with hash map where keys are elements in an array and values are number of occurrences.
- Sim February 06, 2012Scan the array linearly, if a key already exists in a hash map, (assuming there is only one duplicate element), return the key.
if its possible that there are duplicates of multiple elements, then create an array which contains duplicate elements. Whenever key.exists is true, add that element to the array.
In the end , when you have iterated all the elements, the array will contain all the duplicate elements.