3 ms·

Thanks, I'm going to write all this out on a whiteboard the next time someone asks me to sort a linked list in a technical interview. Edit: just wanted to clar

Thanks, I'm going to write all this out on a whiteboard the next time someone asks me to sort a linked list in a technical interview. Edit: just wanted to clarify that the point I'm trying to make here is that if you want to ask someone if they've memorized the answer to that question, go ahead and ask it in a technical interview, because the real well-considered answer looks like the linked article, and my honest non-smartass answer is that one should use the library function and not try to implement it themselves until they've done sufficient research into the problem to prove to a reasonable degree that they indeed do need to re-implement sort() and that it's in the best interests of the business to fund such a project. Would love to read this over the phone to a recruiter and have them tell me that it's not what they have on their sheet.

scatters 5y ago
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 5y 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 5y 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 5y 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 5y 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 5y 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 5y 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 5y 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.
deleted 5y ago
[deleted]

scatters 5y ago

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 5y 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 5y 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 5y 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 5y 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 5y 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 5y 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 5y 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.

deleted 5y ago

[deleted]