techInterview Discussion

A part of techInterview.org: answers to technical interview questions.

Your host: Michael Pryor

Extra element in array

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?
nicky Send private email
Saturday, March 18, 2006
 
 
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.
)
Vipul Send private email
Sunday, March 19, 2006
 
 
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
 
 
I don't believe this. Such complicated answers.

s1 = s2 = 0
for i <- 0 to (|A|-1)
  do s1 <- s1 + A[i]
      s2 <- s2 + A'[i]

s2 <- s2 + A'[i]

output (s2-s1);
bufferman
Thursday, March 23, 2006
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz