> 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.
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.
Hmmm... with Mergesort, you gotta be copying the data to new buffers, malloc-ing arrays and new arrays, managing the data etc. etc.
Quicksort can be trivially done in-place. And yes, I know Merge-sort has an in-place variation, but in-place Mergesort is non-intuitive IMO.
-------
I guess merge-sort is easy if you are willing to call malloc / free (or new / delete) over-and-over again. But those functions scare me. I prefer to get things done without dynamic memory, especially if its a whiteboard interview.
Quicksort does require more brainpower than selection / insertion / bubble sorts. But if I were to use a recursive methodology, trying to do quicksort would be my strategy.
You don't need to memorize multiplication table to be good at math, but this is an equivalent of saying "I wouldn't even be able to add two numbers together in my head!".
Whoever said it, I have a super hard time believing DHH couldn’t implement bubble sort on a whiteboard.
Am I the only one? I get that people hate whiteboard/algorithm interviews, but bubble sort?
for i = 0..n:
for j = i..n:
if arr[i] > arr[j]:
arr[j], arr[i] = arr[i], arr[j]
If you can't do that without help in 45 minutes, what can you actually do?
I think the actual problem is most developers / programmers are just bad at the job, and then go in a huff when this is pointed out.
More importantly, what you wrote is a selection sort, not a bubble sort!
A bubble sort swaps neighboring terms. Eg, if I interpret the code in 2.1 of https://users.cs.duke.edu/~ola/bubble/bubble.html correctly, the 'definitive' version is:
for i = n-1..0:
for j = 0..i:
if arr[j+1] < arr[j]:
arr[j], arr[i] = arr[i], arr[j]But bubblesort? There's no invariant. Sure, I can tell you that it's this structure:
for i = ? .. ?:
for j = ? .. ?:
i1, i2 = ?, ?
if A[i1] < A[i2]:
A[i1], A[i2] = A[i2], A[i1]
do
sorted = true
for i = 0 .. n-1:
if A[i] > A[i+1]:
A[i], A[i+1] = A[i+1], A[i]
sorted = false
while not sorted
If you're trying to recall this algorithm from memory by comparing it with other sorting algorithms you've memorized, you're probably doing it wrong, because there's hardly a place for real world usage of bubble sort, so your memory of it is naturally going to fade away. The trick is - you don't even need to memorize it or recall any structure to fit it into. Just imagine an inefficiently bubbling array of numbers in your head and that's it.
For people who know about knots out there... its like asking for somebody to tie a Granny Knot instead of a square-knot. Anyone who actually practiced knot-tying will "accidentally" tie a square-knot instead (because the square-knot is stronger for the same level of effort).
Similarly, bubble sort is the "bad" way to write insertion sort. Anybody who actually practiced writing sorts will write insertion sort by accident instead.
If I wrote it down every time someone claims that "this is so important any engineer should know it," I'd have a book as thick as the bible full of trivia. All of it so easy, and yet in every position you can find a person who hasn't mastered it all. Maybe it isn't all that important after all. Most of these people are capable of finding help should it come to that.
Merge sort? Quick sort? Bogosort? Maybe not. But bubble sort yes.
Just like an engineer even at the most junior level should be able to swap and write fizz buzz. If you can’t do that you certainly cannot call yourself an engineer.
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