Interview Question

Software Engineer Interview

-Sydney

Google

Find the longest subsequence of duplicate numbers in an array of sorted numbers.

Answer

Interview Answers

5 Answers

2

Hi there, can you elaborate on what you mean by using a binary search? I've been thinking about what you said for the last 10 minutes and I can't understand would a binary search help here. Just curious, thanks

Interview Answer Explanation? on

2

Jumping in powers of 2 would be O(log n) for best case scenario rather than linear search's O(n). Worst case scenario they would both be O(n). Logic: - Let n be the position you are currently checking for the longest subsequence (starts at 0) - K = 0 - While arr[n] == arr[n + 2^K] do - K++ - If 2^K is > the previously known longest subsequence - Binary search between 2^K-1 and 2^K to find the exact length of the current sequence - Store it as the longest known subsequence - Repeat with n as the position you are at now + 1

Anonymous on

0

A binary search with two partitions (i.e. partition list into thirds) will get you a logarithmic time solution. I got this solution, but I think I took too long to do it compared to the other candidates.

Anonymous on

1

If the array is sorted, you can simply go through elements one by one and count the duplicate numbers. The complexity is linear. Could it be so trivial?

Anonymous on

0

Linear is o(n), binary search takes just o(logn)

Anonymous on

Add Answers or Comments

To comment on this, Sign In or Sign Up.