Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
If in the first pass, we find a value with multiple bit set to 1, then choose any one of such bit position.
This is really good answer without modifying the input array.
void twoNumAppearOnce(int arr[], int size)
{
int i, val = 0, res1 = 0, res2 = 0;
for (i = 0; i < size; i ++)
val ^= arr[i];
// Check if there are multiple bits are set to one choose any one of them. I am choosing the right most set bit.
if ( val & (val-1) )
val = (val & (val-1));
// Get the first number - that bit is off in number
for ( i = 0; i < size; i ++ )
if ((val & arr[i]) == 0)
res1 ^= arr[i];
// Get the second number - that bit is on in number
for ( i = 0; i < size; i ++ )
if ((val & arr[i])!=0)
res2 ^= arr[i];
printf ("Values are %d %d\n", res1, res2);
}
2 numbers with single instance:
- XOR all the numbers.
- The final hash will have 2 numbers that occur only once
- Go through the array XOR'ing each number with final hash and check whether the
remaining value is present in the array (we can use hashmap to improve lookup time).
- We have our two numbers when the value is found.
I think the same logic can be extended to solve 3, .. 100 numbers.
// only 1 number appears once and others twice
int unique_number(const vector<int>& a)
{
int ans(0);
for (int i=0; i < 32; i++)
{
int b(0);
for (int i=0; i < a.size(); i++)
b = ( b + ( a[i] & (1 << i) ? 1 : 0 ) ) %2 ;
if (b) ans |= (1 << i);
}
return ans;
}
we can do this with XOR....suppose 2 elements are present one time....lets take an example
given array is {1,3,1,2,2,5,4,5} our output will be 3 and 4
step 1: XOR all elements...we get 3(XOR)4=111(in binary)
step 2: check first one in binary of XOR from right side....in our example first LSB is one....which means...LSB of required numbers is are not same.....
step 3: divide array in two parts..first part numbers has 1 at LSB and second part number has 0 at LSB
step 4: take XOR of first part we get first number and XOR of second part give second
our example
first part: 1(001),1(001),3(011) ,5(101), 5(101) .....XOR of these give 3
secont part: 2(010),2(010),4(100) XOR of these give 4
output: 3,4....which is required
i think for number more then 2 unique numbers..suppose for 10 unique numbers we have to divide array further to get all 10 element(for further division we can use other bits of xor)
I think the idea is to use hash
if key exists then we remove it from hash else we add it to hash , as result the hash will remain just with those that are unique and is O(n)
Suppose, if the same element repeated 3 times, then how can you handle? First time you will add, second time you will delete and third time again you will add... so, is my understanding right??? please correct me if i am wrong.
If we have some element repeated more then 2 times; we can do like this to get O(n) time using Hashing.
(1) check a number to add in a hash table,
if it is not there
then add number as key and value as 1
else then increment the value of that number by 1(by replacing old entry with new entry with increment value)
(2)When all numbers are added,
Traverse the HashTable to get keys whose value is 1.
Seems like hashing or XORing are the two answers everyone here agrees on. I will go with the hashing since this kind of interview problem is usually given to test your knowledge of data structures (i.e. which one would work best and how)
So let's do this one in java real quick, using the obvious method, usually used for questions that ask for a fast way to find if a string contains duplicates (the principle can be applied to this without much adjustment).
public int[] find_unique(int[] a){
HashMap<Integer, Integer> map = new HashMap<Integer,Integer>();
for(int i = 0; i < a.length; i++){
if(map.containsKey(a[i]) == true) map.put(a[i], map.get(a[i]) + 1);
else map.put(a[i], 1);
}
ArrayList<Integer> uniques = new ArrayList<Integer>();
for(int i = 0; i < a.length; i++){
if(map.get(a[i]) == 1) uniques.add(a[i]);
}
return uniques.toArray();
}
Side note: not sure if the toArray I used would work in this case, whatever, you get the idea.
How it works: The method runs through and assesses the total count of all values in the original array. That takes O(n) time assuming the hashing function is decent. Then the method runs through again, after creating an initially empty arrayList, and any entry in a that has a stored value of 1 (meaning it was only seen once) is appended to the list. the list is then returned. The second half takes O(n) time, again assuming we have a decent hashing function.
This isn't as elegant as using logical operations, but you can get some brownie points in the interview if you mention that the runtime could potentially be O(n^2) if the hashing function is bad (i.e. tons of collisions).
Would it be wrong to use a hashset? Traversing through the array once, adding to the hashset when it doesn't contain the value and removing if it does contain it. Leaving you with a set at the end with only values that appeared once.
ok, i didn't pick the right words. there are other ways but it gets much more complex than using a hashmap.
The hashmap approach is easy to code and yields a O(n) time and O(n) extra space solution. To the best of my knowledge, the other approaches take at least O(n) time and O(n) extra space, unless we can change the array inplace but it gets tricky.
Hence, i don't see any reason to not follow the hashing approach.
@Miguel: check out my answer. I give an O(n) time, O(1) space method for finding two missing numbers without modifying the input array.
1. Sort all the elements. Duplicate elements will appear together.
2. Iterate the sorted elements to find out whether an elements is unique by performing equality test with previous one.
Why the downvote? I'm pretty sure the interviewer was looking for this answer instead of the hashing one.
Take the XOR of all the numbers -- this is the XOR of the two missing numbers. Since they differ in at least 1 bit, the XOR is nonzero in at least 1 bit. Identify one such bit position.
- eugene.yarovoi October 01, 2013Now, make a second pass through the array, XORing only numbers with that bit position set to 0 and ignoring the others. You will get one of the missing numbers as a result. Make a third pass that will consider only numbers with that bit position set to 1 to find the second missing number.
It's not apparent how to generalize this idea to 3 or more missing numbers, because 3 missing numbers that are all distinct could have an XOR of 0.