Say you have an un sorted array of numbers from [1-K]. Write a function that returns any duplicates using binary search. You can solve this in o(n) using a set but the interviewer needs to see the binary search solution even though it has worse time complexity??? #engineering #software #swe
They want O(1) space solution. You need to sort it. It’s not always about time complexity. Interviewer probably wanted you to discuss the trade offs between time and space complexity of such solution.
We discussed 4 different approaches. They requested a binary search without sorting it. I didn’t choose that approach.
Sorting is O(n^2), you can have O(nlog(n)) with binary search.
OP are you sure you understood the question correctly? Part of the interview is based on the candidate asking the right questions and disambiguating the ask. It seems like you don't have a clear understanding of the question itself and tried to jump to the solution - red flag tbh
We discussed 4 different approaches. They requested a binary search without sorting it. I didn’t choose that approach.
That doesn't even make any sense
I'm not sure how binary search is related to this problem, that requires sorting the array, and couldn't you do a linear scan afterwards to find duplicates if you're sorting? Is there anything special about the values of the array like they are contiguous from 1 to K with possible duplicates? Then you could do a quickselect type strategy, but this also only works for 1 duplicate value
You need to think a bit outside the box. For N = 5, our range of possible values are 1 - 5. So in that sense we can think of our range as being a list containing the values 1 - 5 (NOTE: you are not actually creating a list here, instead you are simply imagining your range to be in this format) range = [1, 2, 3, 4, 5] Using this idea, we can perform binary search on our range "list" in order to find the duplicate in our actual list. Binary search starts by first selecting your midpoint which in this example will be 3. Using this midpoint (3) you go through your actual list and count the number of values that were less than or equal to 3 and the number of values that were greater than 3. Now, normally, if the size of our actual list was N (and not N + 1 like the problem dictates), the count of values on either side of the midpoint of our range would be equal to the number of possible values. In our example, the count on the left hand side of our midpoint (including the midpoint itself) would be 3 (for 1, 2, 3) and the count on the right hand side of our midpoint would be 2 (for 4, 5). However, since we have N + 1 values in the actual list, this means that either the count on the left hand side will be greater than 3 OR the count on the right hand side will be greater than 2 OR potentially both depending on our actual list. In other words, if the count of values that fall in the range 1 to N/2 is greater than the total number of values it can have then you know there is a duplicate somewhere in 1 to N/2. Otherwise the duplicate will be somewhere in the range of (N/2 + 1) to N.
OP mentioned the array is unsorted
It still works in nlogn time
There is an O(n) and O(1) algo which uses the indices to find the duplicate. Was this the entire question? Or was there some other detail that warranted a monotonic binary search approach? It would still be n*log n I think
This type of question makes me think I’m not actually cut out for FAANG, despite working at amazon for 4 years now.
This kind of situation is a communication test with the interviewer
You misunderstood something
This is the binary search solution that they wanted you to code: https://leetcode.com/problems/find-the-duplicate-number/discuss/72844/Two-Solutions-(with-explanation)%3A-O(nlog(n))-and-O(n)-time-O(1)-space-without-changing-the-input-array
And this is the optimal one both in time and space: https://leetcode.com/problems/find-the-duplicate-number/discuss/72846/My-easy-understood-solution-with-O(n)-time-and-O(1)-space-without-modifying-the-array.-With-clear-explanation.
Why can't we use cyclic sort concept here? I think it can be done in O(n) time. Using BS I don't think it'll improve the complexity. Probably the interviewer is interested in how one uses BS in this ask.
World Conflicts
Yesterday
460
Remember folks, all Israel wants is the hostages back
Tech Industry
Yesterday
349
If you had the choice between two
Tech Industry
Yesterday
1161
Brother beaten severely as a kid. Doesn’t speak to dad at all now.
Tech Industry
Yesterday
8335
China CYBERATTACK on UK ? WTF
Tech Industry
4h
1421
Are tech workers as rich as they think we are?
Why would you want to use binary on i sorted array? You can instead use cyclic sort, place each element in its correct position as elements are ranged from 1 to K
That’s what I said. It’s unsorted I can’t sort it how does binary search help?
I think the interviewer messed up if they did indeed ask for binary search