Hacker News Reader

I don't think writing bubble sort from scratch without mistakes is necessarily a good demonstration of someone's ability to "handle the basics"

Realistically you will never need to write it yourself unless you're coding in some very specific domains

It's at most a signal for whether or not they remember algorithms 101 or some leetcode exercise, but knowing that they do remember isn't really useful to me

it's not even the most efficient search. I don't think any sort method in a language would use a bubble.

I agree it isn’t but the point I was trying to make is that when you have to do something from scratch, on your own, even if it’s simple, it can be a challenge. My example was poor because I am typing fast sitting in a car parking lot and I hate typing my thoughts on phones.. Forgive me..

I was agreeing with you haha

Companies ask that kind of stuff at interviews lol

> It's at most a signal for whether or not they remember algorithms 101 or some leetcode exercise, but knowing that they do remember isn't really useful to me

For bubble sort? Do you really think anyone should have to remember an algorithm to write a quadratic time sort? All you have to do is "compare and swap" and loop through until you are done, this is way easier than Fizzbuzz.

This is only hard if you have a hard time grasping loops, conditional comparisons or swaps. But if you understand all of those the sort writes itself. And understanding loops, comparisons and swaps is pretty fundamental to anything you do as a software engineer, so I'm not sure how any competent software engineer could struggle with it.

Every technical thing you know is informed by your practice in an area. There's a lot of roles where you don't even have to think about which algorithm is implemented behind your favorite sort method. If you work in a role like that for 10 years, bubble sort becomes "which one was that again"?

Engineering is about solving valuable problems. Solving some of those problems requires obsessive control over (and selection of) specific sorting algorithms, many do not.

Edit: it's also worth bearing in mind that many of the people who discovered these algorithms are famous in part for having thought them up. If data structures and algorithms were so obvious, nobody would know who many of these people were.

Assuming knowledge and understanding of an algorithm but no prior practice with implementing it, one’s way of implementing it does tell about their proficiency in programming.

GPs bubble sort was obviously just an example, effectiveness of the algorithm or wether there’s ever need for implementing it by hand is irrelevant.

> All you have to do is "compare and swap" and loop through until you are done, this is way easier than Fizzbuzz.

I think you have this wrong, Fizzbuzz is actually completely trivial to the point where the problem statement is almost literally (modulo modulo) a description of the algorithm.

Bubble sort is very easy but it's not literally trivial to the same degree as Fizzbuzz!

for i = 0 to n { for j = i to n { if n[j] > n[i] { swap(n[i], n[j] }}}

1 point for having a good reply. 100 points for doing it in code. Well done!

Except that sorts the list in reverse: https://tio.run/##Vc6xDsIwDATQPV9xYyJ5od2Qyo9UGYhIwFXkVlY68P...

(Also a subtle off-by-one error, it should be 0 to |n|-1 and i to |n|-1.)

Thanks for catching the reverse. I was aware of the off by one but thought the “to” operator I invented would be exclusive of the second operand (kinda like range in Python) :)

> Fizzbuzz is actually completely trivial to the point where the problem statement is almost literally (modulo modulo) a description of the algorithm.

Fizzbuzz requires you to read and understand a few lines of requirements. That is much harder than just "order these elements, runtime isn't important", you can easily miss some part of the problem statement or misunderstand it for Fizzbuzz and fail, you shouldn't but it can happen, no such thing for a quadratic sort.

>This is only hard if you have a hard time grasping loops, conditional comparisons or swaps

Or because you don't know the algorithm in question... The problem isn't bubble sort but any generic algorithms test. The examiner wants you to write code but not tell you the specification because it would be shockingly similar to telling you the solution.

When I read a post on HN about inverting a tree I was wondering how exactly you are supposed to invert the child and parent relationship so that children point to parents instead of parents pointing to children. I.e. leaf nodes are now at the root and the root node is where the leaf nodes are supposed to be. Then someone said "He meant reversing the tree" and I'm like "That is not what he said."

> Or because you don't know the algorithm in question

I don't think anyone would care if you did an insertion sort or some other brute force way to sort. Brute force sorting in general is trivial to come up with.

I agree with this.

You'll often see responses like "but many people don't need to write sorting algorithms from scratch in their day to day work, so they're out of practice". But to me this attitude itself is indicative of the issue.

Being able to do this doesn't require sorting algorithms to be well-practiced and fresh in one's mind. It requires a general ability to visualize and reason about simple data manipulations. Which to me is an absolute fundamental for a programmer working in any field.

If the algorithm can be described with a small sketch or a couple of sentences, generally an implementation should just flow for an experienced programmer who has general fluency? For something like bubble sort, the description can be more or less directly translated to code.

The fact that someone even conceives of this as something which needs to me memorized / practiced suggests to me that they might not have that kind of basic working fluency.

No need to be so literal. Substitute "bubble sort" for "any simple algorithm involving nested loops/branches/collections" and the result is likely to be the same. Mistakes are common. Partially, that is why unit tests may be useful.

The problem is that people need to know the algorithm you're asking them to implement, which biases it towards memorization.

When you tell them how the algorithm works, it feels like you are not testing anything except syntax.

If you let people look it up, it feels like you aren't testing anything except their research skills.

It is difficult to have a test in a vacuum. It would probably be better to have a test with multiple steps.

Exercise 1:

a) Research the topic bubble sort. Explain what bubble sort does and write some notes or pseudo code that will help you implement it. Once you are done, we will disable internet access and close your browser.

b) Write a working bubble sort in COMPANY LANGUAGE.

c) Modify the bubble sort so that it can sort by multiple columns.

The first tests your research skills, the second your syntax skills and the third your ability to deal with changing requirements and implement novel functionality without research.

Theory: "imposter syndrome" is simply seeing the truth. No one lives up to the social conception. Einstein needed help with mathematics. The realistic perspective is the curiosity of a scientist; the humility of a mortal. Knowing the premises does not automatically imply you know all the consequences... even though it "should".

Bugs have been found in production binary search.

Skipping bubblesort, I think quicksort is easy to implement, if you know Hoare's fp insight (I remembered it, but had to check it was him). Making a version that is both efficient and correct may be harder for me... Similar for Boyer-Moore substring matching (I remembered their names!)

> I think quicksort is easy to implement, if you know Hoare's fp insight

Could you please provide more information on this?

He learnt about recursion in a fp workshop(?), and as a first exercise, tried applying it to sort.

You pick a number in the list, then put lesser numbers into a left-list, and greater into a right-list. Recurse.

It's very slow as intuitive, simple and elegant fp, because it's creating new lists like crazy; but a mutable, in-place version (e.g. in C) is super fast. Maybe the origin of the folklore "learn fp to be a better coder, not to code fp"? I don't think he expected it to be so good; he was just doing him. A very smart man.

This seems like an uninteresting test. Nobody (almost) is implementing sorting algorithms in their day job. We use libraries. It's like asking people who claim to not struggle with driving basics to change their spark plugs and saying "aha, I new you were an idiot".

Yes but it is basic in the sense that it’s one of the first couple algorithms/data structs mostly everyone has been exposed to. Many knowing what they are and the general principle of how and why they work. That is exactly my point though.. Like what do we consider “basic” exactly? That line becomes blurry in any complex field…

If you don't use something, you forget it. Nobody is writing these algorithms in their job. If you did, it will get flagged in code review, the same way rolling your own crypto does. Which is why I think it's unreasonable to expect people to remember how to implement them off the top of their head.

It seems pretty indicative to me. Bubble sort is a simple idea that I understand conceptually but haven’t written the code for yet. That summarises most of my job. And yet, 30 years in, I still make stupid mistakes all the time.

I think the difference between professional engineers and person writing the blog isn’t necessarily skill. I think it’s how we react when we make mistakes. Maybe the real test of a programmer is watching how calmly they can write their buggy bubble sort, then test it and fix the bugs. Bugs happen. How we roll with the punches is what makes some people great.

> I work with arguably some of “smartest” people on the planet, and even they struggle with basic concepts from time to time, as does everyone. There is simply too much information for any single human to know it all, and learn new things instantly.

This. Many programmers, for some reason, act like skill is a complete order; you are either more skilled or less skilled than someone else. In practice you are just familiar with different things, so if somebody doesn't know something that feels trivial to you, it just means he didn't encounter it in the same way.