Anyone with more experience could probably chime in.
"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?
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.
The current situation benefits me personally in many ways, but I recognize that it's unfair to many other people.
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.
I always thought merge/quick sorts accounted for 99.9% of use cases and only ever really learned about those.
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.
It's definitely easy to implement, it just had me worried because I had never heard of it!
Personally I've never found this case myself, but regarding why it's used some times, the O(n²) is the worst case scenario. The best case scenario is O(2n) which is really good, so for lists that are sorted or almost sorted it works well.
Other algorithms like timsort have O(n) for the best case scenario, but O(n) only tells you how many times you go through the loop. Without actually measuring it, I would expect each iteration of timsort to be at more than twice as expensive as bubble sort, so in this case O(2n) would be cheaper than O(n).
When you know with a certain degree of certainty how is the data you expect in most cases, some times it's kinda easy to make a more efficient algorithm than the one that is the best for the average scenario.
If you have an application that only has to sort small lists, but has to sort a lot of them, it is quite possible that an O(n^2) sort like bubble, insertion, or selection sort will be better than merge/quick sort.
Among the O(n^2) sorts, insertion almost always will be faster than bubble, so you probably wouldn't actually choose bubble sort.
It's more just that I am concerned I would be cornered trying to remember what 'bubble sort' is. It's not difficult to write the algorithm per se--just hard to remember what 'bubble sort' means.
If someone just says "hey, implement bubblesort", that's pretty awful though. Then it's just testing your memory and/or gating by people that studied a particular algorithms curriculum. (Though _many_ intro algorithms courses go through sorting and most of those mention bubble sort probably)
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.
I only remember it because a machine language book for the Motorola 6809 used it as an introductory program.
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?
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.
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.
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
> 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.
- 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.
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.
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.