7 ms·

> Programmers can’t write algorithms without help And that might be a good thing. How often does a normal software engineer have to write bubble sort from scra

> Programmers can’t write algorithms without help And that might be a good thing. How often does a normal software engineer have to write bubble sort from scratch in his daily life? If someone from my team came to me telling me he had to sort an array and wrote bubble sort from scratch, then I'd probably not be very happy with that unless there is a really good reason to spend that time on it rather than using an existing solution.

Tehchops 7y ago
Purely anecdotally: I've seen online discourse that suggests that the complex nature of the modern web requires FE devs be able to keep at least a couple efficient data-structure traversal tools in their toolbox. Anyone with more experience could probably chime in.
- starbugs 7y ago
  Yes, being able to write a DFS is definitely a good thing. For more complex stuff I don't mind if you need to look it up.
- rhinoceraptor 7y ago
  In my experience, most front end performance problems are just unoptimized assets, or huge JS bundles. After that, there's issues where you're doing a lot of unnecessary rendering, for example in a React app, a Redux mapStateToProps function that isn't memoizing an array map, which is causing the whole subtree to re-render on every state update. The only time I even needed algorithmic complexity was implementing a drag and drop control, for a list that could have several hundred thousand elements, and my naive implementation was n^2.
  - jimbokun 7y ago
    > that isn't memoizing an array map "memoizing" is a pretty computer-sciencey word, so not implementing a data structure exactly, but still requires knowledge beyond "plug these APIs together." > The only time I even needed algorithmic complexity was implementing a drag and drop control, for a list that could have several hundred thousand elements, and my naive implementation was n^2. And if you didn't have an intuition for algorithmic complexity, how long would it have taken you to figure out the problem? And how many times have you instinctively avoided having an explosion in algorithmic complexity, by intuitively picking a suitable data structure or algorithm?
oneplane 7y ago
I suppose that depends on what a programmer is asked to do. There are many roles and not all of them need the same thing regarding knowledge, computer science or abstract thinking. If you are in a position where you mostly do the same thing over and over inside a relatively complete framework for a managed or scripting language, you are unlikely to find yourself building data structures, algorithms or understand what a query planner in an RDBMS might be up to. Those positions are far more prevalent than people might think. On the other side are the people that have to make sure that they get as much speed and/or as little memory usage as possible because they work on software that will scale (i.e. a small data structure that is used to keep track of filesystem allocations - you don't want a slow structure that also eats up a lot of disk space). But there are far fewer people that actually do that, and in theory far fewer people are needed to do that because a 'good enough' filesystem will fit all of those people from the other category. If one filesystem developer can support 100 million managed-language-framework-MVC-website engineers it's a pretty good scale.
- a_t48 7y ago
  Speaking as someone who has had to write performance critical data structures and also someone who does well with whiteboard interviews - there is a large difference between writing an algorithm with the advantage of having time to read, reason, and test your code and doing it on a whiteboard. There are many people who would do a fine job as a filesystem developer but might not be able to pass the interview for it. The current situation benefits me personally in many ways, but I recognize that it's unfair to many other people.
  - oneplane 7y ago
    Yes, that is true. At the same time, most of those interviews are of course more about finding out how a person performs under pressure and how a person thinks rather than how well the white boarded shell sort for red-black trees with double-rot13 'encryption' would be usable in the real world. At the same time I'd hope that we get better at asking questions rather than repeating the same nonsense in every interview. The more people we can work with, the better. Because maybe not everyone is a fit for the position we had in mind, but maybe a less complex position could be filled that way. Often the interviews are rather binary (due to it often targeting a vacancy instead of a workforce role) costs everyone involved much more than it ideally should.
Sarki 7y ago
I agree, what's more important IMHO is education/knowledge of existing data manipulation, after all 99% of the work is reuse not pure creation (incremental vs pure innovation). Algorithmicians (? - well... algorithm researchers, obviously) and programmers are not working in the same field of work, even though the boundary might seem thin for most, there's a world between both. Must all painters be artists?
- starbugs 7y ago
  I would go as far as saying that an "artist" might be detrimental to reaching your goal in a lot of cases, especially if a team is involved.
  - mark-r 7y ago
    To stretch the analogy to the breaking point, you probably don't want an "artist" to paint your living room walls.
dickeytk 7y ago
I get your point, but why would you pick bubble sort? That’s one any engineer should be able to implement without any help. It’s the more complex/useful ones worth discussing. Even Obama knows this: https://m.youtube.com/watch?v=k4RRi_ntQc8 https://m.youtube.com/watch?v=k4RRi_ntQc8
- starbugs 7y ago
  I picked bubble sort, because it's literally the example from the first sentence of the article: > David Hansson, the creator of Ruby on Rails, admitted in a tweet that he wouldn’t be able to write bubble sort on a whiteboard.
  - dragontamer 7y ago
    I wouldn't be able to write a bubble-sort specifically. But if I were asked to "sort" a set of numbers, I'm sure I'd come up with some unholy combination of bubble, selection, and insertion sort that got the job done. I always have to consult the books to remember the difference between bubble, insertion, and selection sorts. But even without documentation, surely people can write a list of numbers (ex: 9, 4, 5, 3, 2, 6, 0, 1, 8, 7), and then tinker with an algorithm until that list was in order? (0 1 2 3 4 5 6 7 8 9) ------------ Here's the thing about programming: you don't have to travel very far before you get into the "nobody knows the answer". The internet provides enough information for the first ~2 months on the job. Specialized books on your topic (ex: GPUs, HPC, OpenMP, etc. etc.) may cover another 1 or 2 months of training on the job. After that? Nobody in the world is doing what you do. Nobody has to work with your particular configuration of tools, your particular problems (performance? Bugs? Architecture?). Your particular office politics. Literally no one else in the world. And yet, you'll be responsible for coming up with a solution that works, even without any guides. That's why people like testing people "without the internet". Because in most cases, there's no guide to tell you how to progress a real project in the real world.
    - a_t48 7y ago
      Mergesort is also worth looking into.
nraynaud 7y ago
And also, even if the sort was important in my app and there was a superior compelling reason to rewrite it internally (one common case is computing 2 things at once), I would probably google what people in the domain do and think first, try to find a few blog post from people who implemented a sort to look at tradeoffs (getting a feel for the politics is in the domain: they probably critiqued each other's "real life" loads, optimization goal: memory vs. CPU vs cache), and then find something on github that I can follow, and do my tweak on.
AnimalMuppet 7y ago
I agree. In a world where good standard libraries exist, and where Google exists, why would a good software engineer write any of the standard algorithms from scratch?
- klyrs 7y ago
  One thing I find myself implementing repeatedly is the Union-Find datastructure. I never just need that though. Sometimes I need statistics about the disjoint sets, which inevitably means a custom Union implementation. Sometimes I know more about how often Find will be called, where I can get better performance without doing full path compression. Another one I've encountered recently is priority queues. Here, memory requirements and operation runtimes depend on which operations are supported -- insert/pop heaps are faster than insert/decrease/pop heaps are faster than insert/update/pop heaps. And if heap operations are your innermost loop on your critical path, you can get huge gains from rolling your own -- because a standard library's priority queue will support whichever operations it supports and you can't pick features a la carte. But no, I never do this without a search engine handy.
  - jcranmer 7y ago
    Union-find is one I find needing a fair amount too, although it does make algorithms tricky to debug if the problem is a bad union ("which union was the bad one that caused all these groups to collapse into one?"). But even for these simple data structures, I am much more comfortable implementing them with an algorithm textbook in front of me (or some other resource with similar level of detail), simply because it greatly reduces the scope for implementing the data structure itself incorrectly and, secure in that knowledge, I can focus my debugging on the algorithm itself.
Gunax 7y ago
I've been a developer for almost 2 years (I know not that long) but I have never even heard of bubble sort. Looking it up, it is O(n^2). Is there a reason this is a common interview question? It doesn't seem like a sort one would ever really use, or at least it has very obscure uses. I always thought merge/quick sorts accounted for 99.9% of use cases and only ever really learned about those.
- MatekCopatek 7y ago
  I think it's just the simplest sort to describe/implement on a whiteboard.
- cinnamonheart 7y ago
  The logic of bubble sort is so simple that just the description is enough for an implementation. It's a common interview question for the same reason Fizzbuzz is used -- any programmer worth their salt should be able to just write it down. Insertion and selection sort are also O(N^2), but sorts like merge and quick will use them to sort small sublists in their recursive cases because they are fast when input is small enough.
  - Gunax 7y ago
    I see. I would hope one would give a description of what bubble sort is during the question. It's definitely easy to implement, it just had me worried because I had never heard of it!
- mark-r 7y ago
  Bubble sort is good for two reasons. First, it's so easy that anybody should be able to remember how to do it. Second, it's slow and everybody should know that and be able to point it out. It's actually usable for small enough n. I once coded it when I expected n to be 4 or less, and I'm sure the person who replaced it cursed my name when that expectation turned out to be false.
  - kadoban 7y ago
    For a simple sort you can use for small N, I'd suggest insertion sort. Its constants are better, it performs well on almost-sorted input, and I think it's even easier to implement, personally.
mark-r 7y ago
I was once asked to sort a singly linked list in an interview, and the bubble sort was the only one I could think of at the time. This was a small part of a larger coding test that I think was based on a problem they actually ran into, which a previous employee had solved badly. I got a low-ball offer and turned it down. It wasn't until a couple of years later that I thought about that problem again and realized a merge sort would have been perfect.
tiborsaas 7y ago
> And that might be a good thing. - Graphics - Machine learning - Gaming Imagine yourself working in these fields and not being able to implement algorithms, you wouldn't be a super useful teammate.
- starbugs 7y ago
  Being able to write algorithms is a different thing than being able to do it without any reference or documentation on the state of the art, basically from scratch and from the top of your head, as commonly found in interview situations. The point is that as an interviewer/employer you risk not getting the information you've asked for. Someone who is able to memorize interview algorithms isn't necessarily a good fit for the role you are trying to fill. Forcing people to memorize the details of these concepts just to comply in an interview is often a waste of time for both parties. Even as a gamedev/ML guy you don't have to reinvent the wheel everyday. You have to understand what is available, judge about the pros and cons of different solutions, pick the right one and build a good system. Preferably on time.

Tehchops 7y ago

Purely anecdotally: I've seen online discourse that suggests that the complex nature of the modern web requires FE devs be able to keep at least a couple efficient data-structure traversal tools in their toolbox. Anyone with more experience could probably chime in.

starbugs 7y ago
Yes, being able to write a DFS is definitely a good thing. For more complex stuff I don't mind if you need to look it up.
rhinoceraptor 7y ago
In my experience, most front end performance problems are just unoptimized assets, or huge JS bundles. After that, there's issues where you're doing a lot of unnecessary rendering, for example in a React app, a Redux mapStateToProps function that isn't memoizing an array map, which is causing the whole subtree to re-render on every state update. The only time I even needed algorithmic complexity was implementing a drag and drop control, for a list that could have several hundred thousand elements, and my naive implementation was n^2.
- jimbokun 7y ago
  > that isn't memoizing an array map "memoizing" is a pretty computer-sciencey word, so not implementing a data structure exactly, but still requires knowledge beyond "plug these APIs together." > The only time I even needed algorithmic complexity was implementing a drag and drop control, for a list that could have several hundred thousand elements, and my naive implementation was n^2. And if you didn't have an intuition for algorithmic complexity, how long would it have taken you to figure out the problem? And how many times have you instinctively avoided having an explosion in algorithmic complexity, by intuitively picking a suitable data structure or algorithm?

oneplane 7y ago

I suppose that depends on what a programmer is asked to do. There are many roles and not all of them need the same thing regarding knowledge, computer science or abstract thinking. If you are in a position where you mostly do the same thing over and over inside a relatively complete framework for a managed or scripting language, you are unlikely to find yourself building data structures, algorithms or understand what a query planner in an RDBMS might be up to. Those positions are far more prevalent than people might think. On the other side are the people that have to make sure that they get as much speed and/or as little memory usage as possible because they work on software that will scale (i.e. a small data structure that is used to keep track of filesystem allocations - you don't want a slow structure that also eats up a lot of disk space). But there are far fewer people that actually do that, and in theory far fewer people are needed to do that because a 'good enough' filesystem will fit all of those people from the other category. If one filesystem developer can support 100 million managed-language-framework-MVC-website engineers it's a pretty good scale.

a_t48 7y ago
Speaking as someone who has had to write performance critical data structures and also someone who does well with whiteboard interviews - there is a large difference between writing an algorithm with the advantage of having time to read, reason, and test your code and doing it on a whiteboard. There are many people who would do a fine job as a filesystem developer but might not be able to pass the interview for it. The current situation benefits me personally in many ways, but I recognize that it's unfair to many other people.
- oneplane 7y ago
  Yes, that is true. At the same time, most of those interviews are of course more about finding out how a person performs under pressure and how a person thinks rather than how well the white boarded shell sort for red-black trees with double-rot13 'encryption' would be usable in the real world. At the same time I'd hope that we get better at asking questions rather than repeating the same nonsense in every interview. The more people we can work with, the better. Because maybe not everyone is a fit for the position we had in mind, but maybe a less complex position could be filled that way. Often the interviews are rather binary (due to it often targeting a vacancy instead of a workforce role) costs everyone involved much more than it ideally should.

Sarki 7y ago

I agree, what's more important IMHO is education/knowledge of existing data manipulation, after all 99% of the work is reuse not pure creation (incremental vs pure innovation). Algorithmicians (? - well... algorithm researchers, obviously) and programmers are not working in the same field of work, even though the boundary might seem thin for most, there's a world between both. Must all painters be artists?

starbugs 7y ago
I would go as far as saying that an "artist" might be detrimental to reaching your goal in a lot of cases, especially if a team is involved.
- mark-r 7y ago
  To stretch the analogy to the breaking point, you probably don't want an "artist" to paint your living room walls.

dickeytk 7y ago

I get your point, but why would you pick bubble sort? That’s one any engineer should be able to implement without any help. It’s the more complex/useful ones worth discussing. Even Obama knows this: https://m.youtube.com/watch?v=k4RRi_ntQc8 https://m.youtube.com/watch?v=k4RRi_ntQc8

starbugs 7y ago
I picked bubble sort, because it's literally the example from the first sentence of the article: > David Hansson, the creator of Ruby on Rails, admitted in a tweet that he wouldn’t be able to write bubble sort on a whiteboard.
- dragontamer 7y ago
  I wouldn't be able to write a bubble-sort specifically. But if I were asked to "sort" a set of numbers, I'm sure I'd come up with some unholy combination of bubble, selection, and insertion sort that got the job done. I always have to consult the books to remember the difference between bubble, insertion, and selection sorts. But even without documentation, surely people can write a list of numbers (ex: 9, 4, 5, 3, 2, 6, 0, 1, 8, 7), and then tinker with an algorithm until that list was in order? (0 1 2 3 4 5 6 7 8 9) ------------ Here's the thing about programming: you don't have to travel very far before you get into the "nobody knows the answer". The internet provides enough information for the first ~2 months on the job. Specialized books on your topic (ex: GPUs, HPC, OpenMP, etc. etc.) may cover another 1 or 2 months of training on the job. After that? Nobody in the world is doing what you do. Nobody has to work with your particular configuration of tools, your particular problems (performance? Bugs? Architecture?). Your particular office politics. Literally no one else in the world. And yet, you'll be responsible for coming up with a solution that works, even without any guides. That's why people like testing people "without the internet". Because in most cases, there's no guide to tell you how to progress a real project in the real world.
  - a_t48 7y ago
    Mergesort is also worth looking into.

nraynaud 7y ago

And also, even if the sort was important in my app and there was a superior compelling reason to rewrite it internally (one common case is computing 2 things at once), I would probably google what people in the domain do and think first, try to find a few blog post from people who implemented a sort to look at tradeoffs (getting a feel for the politics is in the domain: they probably critiqued each other's "real life" loads, optimization goal: memory vs. CPU vs cache), and then find something on github that I can follow, and do my tweak on.

AnimalMuppet 7y ago

I agree. In a world where good standard libraries exist, and where Google exists, why would a good software engineer write any of the standard algorithms from scratch?

klyrs 7y ago
One thing I find myself implementing repeatedly is the Union-Find datastructure. I never just need that though. Sometimes I need statistics about the disjoint sets, which inevitably means a custom Union implementation. Sometimes I know more about how often Find will be called, where I can get better performance without doing full path compression. Another one I've encountered recently is priority queues. Here, memory requirements and operation runtimes depend on which operations are supported -- insert/pop heaps are faster than insert/decrease/pop heaps are faster than insert/update/pop heaps. And if heap operations are your innermost loop on your critical path, you can get huge gains from rolling your own -- because a standard library's priority queue will support whichever operations it supports and you can't pick features a la carte. But no, I never do this without a search engine handy.
- jcranmer 7y ago
  Union-find is one I find needing a fair amount too, although it does make algorithms tricky to debug if the problem is a bad union ("which union was the bad one that caused all these groups to collapse into one?"). But even for these simple data structures, I am much more comfortable implementing them with an algorithm textbook in front of me (or some other resource with similar level of detail), simply because it greatly reduces the scope for implementing the data structure itself incorrectly and, secure in that knowledge, I can focus my debugging on the algorithm itself.

Gunax 7y ago

I've been a developer for almost 2 years (I know not that long) but I have never even heard of bubble sort. Looking it up, it is O(n^2). Is there a reason this is a common interview question? It doesn't seem like a sort one would ever really use, or at least it has very obscure uses. I always thought merge/quick sorts accounted for 99.9% of use cases and only ever really learned about those.

MatekCopatek 7y ago
I think it's just the simplest sort to describe/implement on a whiteboard.
cinnamonheart 7y ago
The logic of bubble sort is so simple that just the description is enough for an implementation. It's a common interview question for the same reason Fizzbuzz is used -- any programmer worth their salt should be able to just write it down. Insertion and selection sort are also O(N^2), but sorts like merge and quick will use them to sort small sublists in their recursive cases because they are fast when input is small enough.
- Gunax 7y ago
  I see. I would hope one would give a description of what bubble sort is during the question. It's definitely easy to implement, it just had me worried because I had never heard of it!
mark-r 7y ago
Bubble sort is good for two reasons. First, it's so easy that anybody should be able to remember how to do it. Second, it's slow and everybody should know that and be able to point it out. It's actually usable for small enough n. I once coded it when I expected n to be 4 or less, and I'm sure the person who replaced it cursed my name when that expectation turned out to be false.
- kadoban 7y ago
  For a simple sort you can use for small N, I'd suggest insertion sort. Its constants are better, it performs well on almost-sorted input, and I think it's even easier to implement, personally.

mark-r 7y ago

I was once asked to sort a singly linked list in an interview, and the bubble sort was the only one I could think of at the time. This was a small part of a larger coding test that I think was based on a problem they actually ran into, which a previous employee had solved badly. I got a low-ball offer and turned it down. It wasn't until a couple of years later that I thought about that problem again and realized a merge sort would have been perfect.

tiborsaas 7y ago

> And that might be a good thing. - Graphics - Machine learning - Gaming Imagine yourself working in these fields and not being able to implement algorithms, you wouldn't be a super useful teammate.

starbugs 7y ago
Being able to write algorithms is a different thing than being able to do it without any reference or documentation on the state of the art, basically from scratch and from the top of your head, as commonly found in interview situations. The point is that as an interviewer/employer you risk not getting the information you've asked for. Someone who is able to memorize interview algorithms isn't necessarily a good fit for the role you are trying to fill. Forcing people to memorize the details of these concepts just to comply in an interview is often a waste of time for both parties. Even as a gamedev/ML guy you don't have to reinvent the wheel everyday. You have to understand what is available, judge about the pros and cons of different solutions, pick the right one and build a good system. Preferably on time.