Interview Question
Mobile Software Engineer Interview
-
NestAlgorithms 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?
Interview Answers
4 Answers
▲
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
Add Answers or Comments
To comment on this, Sign In or Sign Up.