4 ms·

If you need to write a sort from scratch it's because you're in some weird restricted environment without a standard library. Not because you need to get a few

If you need to write a sort from scratch it's because you're in some weird restricted environment without a standard library. Not because you need to get a few percent better performance sorting some gargantuan data set. Being able to put together a sort from compares and swaps (or inserts, or whatever you have available) is at least evidence that you won't either panic or storm off when the tools you have are something less than ideal.

naniwaduni 4y ago
"You have a weird bespoke data structure" is an example of an "environment" where you might not have a sort that works for your data in your standard library. Of course, if you're in that situation, you're not using a weird bespoke data structure for a mere few percent better performance.
gumby 4y ago
Also in in such an environment (real world not interview) you almost always have constraints on your data and/or requirements that allow you to write something faster or smaller (depending on your needs) that can beat the standard implementation because it doesn’t have to handle corner cases (or as this post shows, some major cases as well).
pas 4y ago
I'd wager that 99% of developers are not without a stdlib and yet it seems they get ~100% of the crazy algo interviews. > [...] is at least evidence that you won't either panic or storm off when the tools you have are something less than ideal. Maybe. Maybe not? Most of the time our tools are far from ideal anyway. Most of the time the important factors are a direct consequence of management/leadership/team. (Deadlines, feature creep, crazy engineering practices - eg. hand rolling sort, crazy interview practices - 8 hours of hardcore interview or whatnot, and so on.)
- quietbritishjim 4y ago
  In my job: * I always have access to a decent stdlib and would not need to implement sort itself * But I do need to design and implement bespoke algorithms The algorithms are nothing groundbreaking - they're things like how to grow and shrink a buffer when reading from a socket. But I'd struggle if I didn't know a few examples of different algorithms and how to think about their trade offs, and basic sorting algorithms (not like this article!) are ideal for that. Maybe I'm doing unusual work but it doesn't really feel like it. Edit: To put it another way: in a past job, we had some unfortunate examples of people being hired whose ability to work with algorithms was sadly not up to scratch, and it had a serious practical impact on their ability to do their job. If they had been asked a few questions about sorting algorithms in their interview then that could have been avoided.
  - jsmeaton 4y ago
    Then would a better interview technique be something like - here is a spec for an algorithm. Now implement it. I see very little value in having people studying algorithm implementations for interviews. Of course, knowing about specific algorithms is handy, and adjusting the question to find an appropriate spec to implement for a given problem could be a nice touch. I think that either approach above is strictly better than implementing algorithms from memory and would produce a far better signal.
  - pas 4y ago
    I think algorithmization is a must for programming. (Like you said, transforming/filtering data, results, structures, etc.) No questions about that. But grilling candidates for hours about it seems "a bit" excessive. (Which is again qualitatively different from asking someone to write a few lines of pseudocode/python/whatever-they-want to map/reduce something or ask them how they would implement a calculator, a few pointed questions about knowing the basics, etc.)
arnsholt 4y ago
I once had occasion to implement a sort algorithm in anger, on a platform _with_ a standard library no less! The project was written in SmallTalk, running on a very old implementation (last updated in 1999 I think) and we had a problem where clicking on column headers in the UI to sort would be very slow if most of the values were equal. The problem was that the standard library array sort was quicksort (which also meant that sorting on several columns broke since quicksort isn't stable), but since SmallTalk makes these things possible when you need to replacing the stdlib quicksort with mergesort was actually a fairly simple operation.

naniwaduni 4y ago

"You have a weird bespoke data structure" is an example of an "environment" where you might not have a sort that works for your data in your standard library. Of course, if you're in that situation, you're not using a weird bespoke data structure for a mere few percent better performance.

gumby 4y ago

Also in in such an environment (real world not interview) you almost always have constraints on your data and/or requirements that allow you to write something faster or smaller (depending on your needs) that can beat the standard implementation because it doesn’t have to handle corner cases (or as this post shows, some major cases as well).

pas 4y ago

I'd wager that 99% of developers are not without a stdlib and yet it seems they get ~100% of the crazy algo interviews. > [...] is at least evidence that you won't either panic or storm off when the tools you have are something less than ideal. Maybe. Maybe not? Most of the time our tools are far from ideal anyway. Most of the time the important factors are a direct consequence of management/leadership/team. (Deadlines, feature creep, crazy engineering practices - eg. hand rolling sort, crazy interview practices - 8 hours of hardcore interview or whatnot, and so on.)

quietbritishjim 4y ago
In my job: * I always have access to a decent stdlib and would not need to implement sort itself * But I do need to design and implement bespoke algorithms The algorithms are nothing groundbreaking - they're things like how to grow and shrink a buffer when reading from a socket. But I'd struggle if I didn't know a few examples of different algorithms and how to think about their trade offs, and basic sorting algorithms (not like this article!) are ideal for that. Maybe I'm doing unusual work but it doesn't really feel like it. Edit: To put it another way: in a past job, we had some unfortunate examples of people being hired whose ability to work with algorithms was sadly not up to scratch, and it had a serious practical impact on their ability to do their job. If they had been asked a few questions about sorting algorithms in their interview then that could have been avoided.
- jsmeaton 4y ago
  Then would a better interview technique be something like - here is a spec for an algorithm. Now implement it. I see very little value in having people studying algorithm implementations for interviews. Of course, knowing about specific algorithms is handy, and adjusting the question to find an appropriate spec to implement for a given problem could be a nice touch. I think that either approach above is strictly better than implementing algorithms from memory and would produce a far better signal.
- pas 4y ago
  I think algorithmization is a must for programming. (Like you said, transforming/filtering data, results, structures, etc.) No questions about that. But grilling candidates for hours about it seems "a bit" excessive. (Which is again qualitatively different from asking someone to write a few lines of pseudocode/python/whatever-they-want to map/reduce something or ask them how they would implement a calculator, a few pointed questions about knowing the basics, etc.)

arnsholt 4y ago

I once had occasion to implement a sort algorithm in anger, on a platform _with_ a standard library no less! The project was written in SmallTalk, running on a very old implementation (last updated in 1999 I think) and we had a problem where clicking on column headers in the UI to sort would be very slow if most of the values were equal. The problem was that the standard library array sort was quicksort (which also meant that sorting on several columns broke since quicksort isn't stable), but since SmallTalk makes these things possible when you need to replacing the stdlib quicksort with mergesort was actually a fairly simple operation.