Round 1
Questions: Given a list of N+1 numbers, each in the integer range of 1 to N inclusive, please return any duplicate.
- Ex. N = 3
- L = [2,3,1,2] returns 2
- L = [1,1,1,1] returns 1
- L = [1,3,1,3] returns 1 OR 3 (note, not both)
The constraints were - The input array is immutable and need to use O(1) space, these made the problem a bit tricky.
Candidate's Approach
I used a binary-search based approach to trim the input result space (which can go from 1-N) in each call, that seemed to have done the job.
Interviewer's Feedback
No feedback provided.