Marin Software Interview Question: I guess it would be the addit... | Glassdoor

Interview Question

Software Engineer Interview

I guess it would be the additional constraints on the array

  of integers being immutable. That and the fact that it should run in linear time.
Answer

Interview Answer

2 Answers

0

Hash the thing!!!!!

Interview Candidate on Mar 20, 2014
0

Hashing the whole 50 trillion entries does not seem right - the memory requirement would be very high (50 trillion*8 bytes) and unnecessary.

One possible solutions:
If we know that the values are within a limit (0 to n), then we can use the fast and slow cycle method to find the loop and then use it to reach the duplicate.
Code:
if(slow != fast) {slow = nums[slow]; fast = nums[nums[fast]];}
fast = 0;
if(slow != fast) {slow = nums[slow]; fast = nums[fast];}
return slow;

Anonymous on Apr 19, 2017

Add Answers or Comments

To comment on this, Sign In or Sign Up.