←back to thread

Google's “Director of Engineering” Hiring Test

(www.gwan.com)
1764 points fatihky | 2 comments | 13 Oct 16 15:15 UTC | HN request time: 0.001s | source
Show context
sonoffett ◴[13 Oct 16 15:58 UTC] No.12701639[source]▶
quicksort is O(n^2) which is definitely not the "best big-O" for sorting.
replies(4): >>12701670 #>>12701718 #>>12701729 #>>12701867 #
1. dekhn ◴[13 Oct 16 16:09 UTC] No.12701729[source]▶
quicksort is O(nlogn) average case, and O(n2) on already sorted arrays.
replies(1): >>12703114 #
2. bvinc ◴[13 Oct 16 18:53 UTC] No.12703114[source]▶
Just a nitpick: There are versions of quicksort that perform well, O(n*log n), on already sorted data. But there is always some worst case scenario where it can be O(n^2).