Nest

## Interview Question

Mobile Software Engineer Interview

-

# 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?

0

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 ?

bitwise on

0

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

Anonymous on

0

Stupid Math this is called stalking not algorithm

Carla on

1

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.

Anonymous on