Do you remember all the time in college where your professor explained the intricacies of cache hits, access latencies, and branch prediction when going over algorithms?
As it turns out, designing a fast algorithm involves a lot more than what is covered in the textbooks. This is why something like Timsort can generally outperform quicksort even though a naive algorithms course overview may well come to the opposite conclusion.
If my job is not to design these algorithms, why does it matter if I can write a naive implementation of one?
Kind of a coincidence that you should bring that up since several jobs I've been at involved stints analyzing performance and identifying bottlenecks in existing code and it is, unfortunately, rather easy to glue together even well designed libraries in ways that result in a slow, inefficient result. Developers simply cannot get away with not knowing how their tools and libraries work under the hood.
It matters because "algorithm" is just another word for "program". The question is whether you can think up a way to make the computer do what you want it to do at all at the level after FizzBuzz, even when it's something like reversing a linked list that can be done in two lines of code (see https://news.ycombinator.com/item?id=30616573, or seven in C), even when it doesn't need to be fast.
I mean, it's true that there's a lot of code that really is at the FizzBuzz level:
switch (c) {
case 'h': case 'D': menu.left(); break;
case 'j': case 'B': menu.down(); break;
case 'k': case 'A': menu.up(); break;
case 'l': case 'C': menu.right(); break;
default: /* no op */ break;
}
def find(self, name):
for thing in self.contents:
if thing.is_a(name):
return thing
vaders.hits(bullets, (vader, bullet) => {
blam(vader, 2.5)
score += vader.bounty
vader.die()
bullet.die()
})
if (vaders.where(({y}) => y > 400).count()) startGame(120)
if (!vaders.count()) startLevel()
And I think you should write as much of your code as possible in such a painfully obvious way. Every once in a while, though, you do need to write something that can't be written quite that simply. Often, the reason why is something in your problem domain:
async def take_token(self):
self.update()
while not self.tokens:
await asyncio.sleep(self.recharge / 10)
self.update()
self.tokens -= 1
// Animate explosions.
poof.move()
poof.each(p => {if (--p.ttl < 0) p.die()})
// Chain-reaction explosions.
poof.about_every(64).each(p => {
if (poof.count() < 1024) blam(p, p.w/12)
})
// Limit number of explosion objects to guarantee responsivity
if (poof.count() > 1024) poof.about_every(2).die()
You need to be able to reason through what your code will do once you've written it, and you need to be able to come up with possible ways to write it that might work. Often the code you need for your problem domain isn't already in the standard library, so you have to write it. If it's on npm, you have to be able to read it to see whether it might work.
Reversing a linked list is just about the simplest task that requires that kind of reasoning, and it has the advantage (or disadvantage) that understanding the puzzle doesn't require, or benefit from, any problem-domain knowledge. You could substitute binary search or insertion sort or something. Another example I got, which takes a few more lines of code, was "implement an integer stack ADT which can always tell you the maximum number on the stack in constant time".
As it turns out, designing a fast algorithm involves a lot more than what is covered in the textbooks. This is why something like Timsort can generally outperform quicksort even though a naive algorithms course overview may well come to the opposite conclusion.
If my job is not to design these algorithms, why does it matter if I can write a naive implementation of one?