3 ms·
Do you actually find people that expect candidates to implement quicksort? I've certainly implemented it, but there's no way I have it memorized, it's not an o
by bugsy 16y ago
Do you actually find people that expect candidates to implement quicksort?
I've certainly implemented it, but there's no way I have it memorized, it's not an obvious algorithm at all. I'd be flabbergasted to be asked to implement it from memory with no warning. It seems clear to me that one would be testing for if the person happened to have looked at the algorithm recently, not if they were competent.
- nandemo 16y agoIt's not such an arcane algorithm. Choose a pivot element, (say) p. Rearrange the array into left_sub_array + [p] + right_sub_array such that all elements of left_sub_array are no greater than p, and all elements of right_sub_array are greater than p. Then recursively sort the left and right sub-arrays. If you don't remember this, it's OK. If I was the interviewer I'd still give you the description above and see if you could implement it. Most candidates cannot.
- adrianN 16y agoAs long as you don't want to do it in-place, it's actually very easy to code.
- kaiwetzel 16y agoIn college ("computer science part A",using Haskell) we played out the various sorting algorithms we learned in class, with students holding up a number (to determine sorting order). Neat to actually experiencing the slowness of bubblesort vs. mergesort/quicksort ;) We repeated the performance in front of a local mall - I can't recommend trying something like that in a crowded place from that experience. I think expecting recent CS graduates to implement a basic sorting algorithm or binary search, etc. (say, in a garbage collected language they know well) is reasonable, for people with actual work experience I think it makes less sense and the focus should be on more recent experience if relevant to the job.
- bugsy 16y agoYeah doing a binary search in an array is pretty standard. What I was asking though is quicksort since that was mentioned. It's not obvious by any means how it works and I recall that early reference implementations had bugs that were unknown for years even though widely used. It really sounds to me like asking someone to implement the FFT in an interview. What are you really testing for when you do that?
- MichaelGG 16y agoI used quicksort as an example of something that one could conceivably memorize in Haskell (only 80 chars) with no clue to the functionality. I was referring to any sort of "memorization" - just talking and watching someone code should make it clear if they just recently read an article about an algorithm, or if they actually understand it.