## techInterview Discussion |
||

A part of techInterview.org: answers to technical interview questions.
Your host: Michael Pryor |
Given 2 arrays, A and A'.
A has one more element than A'. How do you find the extra element? Assuming the two arrays are unsorted. Further restriction: cannot use any relational operators (>, <, ==...) If these are 2 arrays of integer, I think I can take the sum of the two and subtract one from another. What if they are not integer but objects? How would you go about that?
A very naive solution to start with:
Create a hashtable , scan through array a , insert each table into hashtable. scan throught array a' if element exists in hashtable, then remove it from hashtable. in the end 1 element in hashtable , which should be the solution. (anyways on second thought: i guess this does not satisfy ur requirement of not using == , as the hashtable internally would be using that or a variant of it. )
Create a hash function from your element type to an int. XOR together the hashes of all elements of A and A’. You are left with the hash of the extra element. Find it, check for duplicates -- if any deal with them. You are done.
AlphaBeta Tuesday, March 21, 2006 |

Powered by FogBugz