It follows that our list has at least one integer which appears at least twice. But it may have several duplicates, and each duplicate may appear more than twice.
Write a function which finds an integer that appears more than once in our list.
(If there are multiple duplicates, you only need to find one of them.)
We're going to run this function on our new, super-hip Macbook Pro With Retina Display™. Thing is, the damn thing came with the RAM soldered right to the motherboard, so we can't upgrade our RAM. So we need to optimize for space!
We can do this in space.
We can do this in less than time, while keeping space.
We'll never post on your wall or message your friends.
Once you're logged in, you'll get free full access to this and 4 other questions.
space and time.
Tricky as this solution is, we can actually do even better, getting our runtime down to while keeping our space cost at . The solution is NUTS; it's probably outside the scope of what most interviewers would expect. But for the curious...here it is!
This function always returns one duplicate, but there may be several duplicates. Write a function that returns all duplicates.