31–40 of 52 posts
Earlier quoted context omitted.
Also no mention of introsort (C++ std::sort), where it uses insertion sort for small arrays, detects if it's fallen too far towards O(n^2) of quicksort, and punts to heapsort when it needs to.
You can pry my stable sort algorithms out of my cold, dead hands.
Of course in the real world for problems where sorting is actually the bottleneck and not just something you want not to kill your app's performance, you end up with things like timsort that destroy all these in practice.
Earlier quoted context omitted.
Also no mention of introsort (C++ std::sort), where it uses insertion sort for small arrays, detects if it's fallen too far towards O(n^2) of quicksort, and punts to heapsort when it needs to.
You can pry my stable sort algorithms out of my cold, dead hands.
Who is still asking candidates to talk about sorting algorithms? It is just trivia and has little to no bearing on if the candidate can actually do the job (unless the job relates to the runtime of sorting algorithms, of course).
There may be better ways to assess that, though. For example, you could ask them to give one or two examples each of algorithms that are O(1), O(log N), O(N), O(N log N), and O(N^2), and O(something worse than N^2).
Who is still asking candidates to talk about sorting algorithms? It is just trivia and has little to no bearing on if the candidate can actually do the job (unless the job relates to the runtime of sorting algorithms, of course).
Some people like that sort of thing. Mostly the "academic" types. The memorizers. There are people who got through their higher education by using memory instead of wit. I know some of those people, I went to school with some of them, they were always studying and ramming as much "data" into their brains as possible... while I was getting through with minimum of effort by just coding a lot and trying to think about t…
Of course in the real world for problems where sorting is actually the bottleneck and not just something you want not to kill your app's performance, you end up with things like timsort that destroy all these in practice.
Is there any evidence of timsort being superior in practice? I've been looking for benchmarks but on synthetic ones with randomized data, both mergesort and quicksort handily beats timsort. The belief about timsort's superiority seem to me to be more about Tim Peters being a very well-respected developer than performance data.
Who is still asking candidates to talk about sorting algorithms? It is just trivia and has little to no bearing on if the candidate can actually do the job (unless the job relates to the runtime of sorting algorithms, of course).
Who is still asking candidates to talk about sorting algorithms? It is just trivia and has little to no bearing on if the candidate can actually do the job (unless the job relates to the runtime of sorting algorithms, of course).
Disagree. If you think that, what do you ask? "How would you Google or Stack overflow for the answer?" That's hardly going to provide any useful signal. At the end of the day you need to ask something that shows evidence there candidate knows something about efficiency tradeoffs.
Traditional technical interviews don't seem to help you find the best candidates (Google famously studied their interview process and decided it was no better than chance).
So maybe don't do a technical interview. Or if you do, just take a couple of real problems from work.
If you're making a lot of hires, do some research and run a RCT.
Would be nice to see mention of parallel sorting algorithms. These have basically linear speedup and you can do them on GPUs.
Obvious disclaimer that you should never care about your sorting algorithm choice until you need to. Performance is more often IO or memory related than compute. Tech interviews are daft, etc.
Who is still asking candidates to talk about sorting algorithms? It is just trivia and has little to no bearing on if the candidate can actually do the job (unless the job relates to the runtime of sorting algorithms, of course).
I think the intention is that the job will relate to the running time of other algorithms and that sorting things is a toy problem you can use to test whether they know anything about that subject in general. There may be better ways to assess that, though. For example, you could ask them to give one or two examples each of algorithms that are O(1), O(log N), O(N), O(N log N), and O(N^2), and O(something worse than N…
Generate all permutations of the data. Stop when one of them is in order.
O(n*n!).