←back to thread

Google's “Director of Engineering” Hiring Test

(www.gwan.com)
1764 points fatihky | 1 comments | 13 Oct 16 15:15 UTC | HN request time: 0.349s | source
Show context
enjoylife ◴[13 Oct 16 15:48 UTC] No.12701550[source]▶
What the heck is a "Quicksort big-O score"? I've never heard anyone use the noun score when talking about complexity analysis.
replies(2): >>12701671 #>>12701675 #
protomyth ◴[13 Oct 16 16:04 UTC] No.12701675[source]▶
I assume they want the average O(n log n), but who the heck knows given the script from above.

I get the feeling this: http://bigocheatsheet.com would come in handy

replies(1): >>12701916 #
steven777400 ◴[13 Oct 16 16:28 UTC] No.12701916[source]▶
Big-O technically means "worst case", which for Quicksort is O(n^2), although usually (in normal cases) it runs better than that. Other sort algorithms can guarantee not worse than O(n log n).
replies(3): >>12702289 #>>12702370 #>>12703002 #
1. TimonKnigge ◴[13 Oct 16 18:39 UTC] No.12703002[source]▶
Depending on how the pivot is picked, Quicksort can actually be implemented in O(n lg n) worst-case time.

EDIT: I was going to link a proof for this but it's surprisingly hard to find. IIRC, the idea is to use the median of medians algorithm ([1]) to pick the median for the pivot, and deal with values equal to the pivot by alternatingly placing them in the left and right partition, or alternatively just keep them in a third partition in the middle.

[1] https://en.wikipedia.org/wiki/Median_of_medians