Search a max value in an unsorted array. (Very abstract question) in better than O(n).

Question

dan · Accepted Answer

Is that even possible? If array is unsorted, there is no way to know the max unless you go over all the array. Sort the array would take more than o(n)

Unless there is some information missing on the question, the best would be o(n)

Anonymous · Answer

sorry - misread and can't edit - OP must have misheard or typed because better than O(n) is not possible to find a value in an unsorted array.

Anonymous · Answer

The key in generic questions like this, is to make sure to cover the fundamentals. There's usually a back-and-forth with the interviewer.
      

Might be worth doing a mock interview with one of the Google  Senior Software Engineer experts on Prepfully? Really helps to get some real-world practice and guidance.
      

prepfully.com/practice-interviews

Learning · Answer

would not priority Queue with custom compactor can do that on O(log(n)) ?

Lee · Answer

Quick select should help. It has a similar partition logic as quick sort but performs somewhere close to O(n) average case. Worst case, O(n^2), be sure to tell that. But most of the times, it is less than O(n) as we do partitions.

Anonymous · Answer

It's possible - you sort the array first. O(n log n) -- then you get the last value O(1)

Google

Google Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches