Hacker News Reader

> I had a professor who told the class that if they ever wrote a sorting algorithm professionally, they should be fired.

For straight up sorting, yes.

But, some other algorithms have exactly the same structure as sorting.

As a toy example, take the famous skyline problem. See https://briangordon.github.io/2014/08/the-skyline-problem.ht... for the details:

"You are given a set of n rectangles in no particular order. They have varying widths and heights, but their bottom edges are collinear, so that they look like buildings on a skyline. For each rectangle, you’re given the x position of the left edge, the x position of the right edge, and the height. Your task is to draw an outline around the set of rectangles so that you can see what the skyline would look like when silhouetted at night."

One approach to solving the problem is equivalent to merge sort: you write a merge function that merges two lists of in-order non-overlapping rectangles, and go from there.

Which turns out not to be a toy problem at all - with the x axis representing time, and the y axis representing things like 'resource utilization' or 'seat reservations' or 'room bookings', all of a sudden you've got the basis for any number of resource optimization or allocation problems.

A related problem (not the same problem, but amenable to the same sort of approaches), for example, comes up when displaying overlapping appointments in a calendar timeline view.

Indeed. And the merge sort approach to solving these intervall-as-a-datastructure problems parallelize nicely.

>>I had a professor who told the class that if they ever wrote a sorting algorithm professionally, they should be fired.

Not many out of the box libraries would have find N min out of a stream/iterator...draw the moving median, moving min/max and so on. You won't find a red/black tree with linked next nodes to do the task efficiently. So sometimes there is that.

I realize that you chose one example off the top of your head, but it seems like an incredibly rare case. The majority of developers can understand "Queries involving this column are slow, it needs an index". Slightly more sophisticated developers can use an EXPLAIN statement (or it's equivalent) to see how many rows are being scanned and apply indexes where necessary. How many hours of coursework is it worth to obtain the knowledge "finding things in a ordered tree data structure are way faster than scanning through the whole table"?

I'm not sure if I've ever run into anyone who said "The things I learned in college have turned out to be pretty much worthless in my professional career. I wasted a lot of time learning irrelevant information." It's interesting that the majority of every CS education is always valuable, to every person, with no exceptions.

Eh, you'd be surprised by the number of devs that simply don't know what indexes are, other than magic-go-fast-juice. I've seen people put a separate index on every column, so that "it'd be fast for all queries"...without thinking that most of their queries used at least two predicates. I've seen people go on to spend tons of time and money on things that fundamentally cannot work because they simply are incapable of thinking through the complexity of what their asking. The fact that modern systems are so fast can let someone get pretty far before hitting a brick wall.

OTOH, I'm not sure full coursework is needed for that. Just make your way through Sedgwick's algorithms book in a month or two and you're in the top 1% probably.

Most places where I have worked, this is simply not the case. N in this case is somewhere between 100 and 300. Database indexing SPECIFICALLY is something that very few people grasp. Even Senior-Senior people.