Algorithms question was probably the trickiest thing.

Given an array of integers of length N from 1 to N-1, how would you detect a single duplicate in the array?

Question

Algorithms question was probably the trickiest thing.

Given an array of integers of length N from 1 to N-1, how would you detect a single duplicate in the array?

Anonymous · Accepted Answer

The first solution basically was to add up all the numbers in the array and the 

for N = 3 and in an array of 1 1 2, which totals to 4, total - N = 1.

The duplicate is 1

He then turned up the difficulty to no additional memory space and to do it in big-O N time.

bitwise · Answer

a xor a = 0
0 xor a = a

so if we xor all elements 1 x 1 x 2 with all possible elements 1x2x3 = 0x3 = 3

still extra memory used but at least no overflow possibility.

was it allowed to change the original input ?

Anonymous · Answer

1) Subtract each number from summation formula = N * (N+1) / 2

2) Hash table , zero out all entries 
     when insert number -> 1
     after all insert look for 0 entry

3) XOR all elems -> X
     XOR all # 1 to N -> Y
    XOR of X and Y -> missing #



15 ^ 12 ^ 15 = 12

Carla · Answer

Stupid Math this is called stalking not algorithm

Nest

Nest interview question

Interview Answers

Followed companies

Job searches

Bowls

Want the inside scoop on your own company?