11 ms·

Challenging algorithms and data structures every programmer should try

439 points by whack 4y ago

melony 4y ago
I recommend https://web.stanford.edu/class/cs168/index.html https://web.stanford.edu/class/cs168/index.html
koinedad 4y ago
Thanks for the list. First time I coded a Trie I thought it was super cool. Topological sort is such a useful one as well.
- Turing_Machine 4y ago
  Tries are probably the one I've used the most in the real world, so I guess if I were making such a list it'd be on the main one, not in the honorable mention section. I'm not sure which one I'd remove to make space for it, though. I second the recommendation for Jeff Erickson's book. He is an awesome in-person instructor, too.
anigbrowl 4y ago
Nicely written. Hits a spot that a lot of instructional and documentary material misses - telling the reader up front what common problem each technique solves.
samsquire 4y ago
Wikipedia is sometimes enough to implement an algorithm. I implemented multiversion concurrency control and btrees due to Wikipedia which do not have pseudocode. If you can implement an algorithm from an English description that is really useful. It relies on the algorithm being well explained. I also suggest trying to implement a btree, they're really useful data structures for data retrieval and many database products use them extensively for indexes. With any algorithm, I think there is a critical insight (that might be different for each person) where the algorithm clicks. I didn't understand mergesort properly until I worked on implementing it but I understood quicksort. When the underlying mental model of the problem being solved becomes clear, we can reason about the algorithm and write code to implement what we want to do.
- withinboredom 4y ago
  I also recommend this. It can really help when trying to understand why a query may be slow even though you’re using indices. For example, one index was on a Boolean field and the query took several seconds. Most rows were “true” and very rarely did we query for false, and when we did query for false, latency was acceptable. If you know a btree is being used under the hood, you can imagine what the tree looks like and that it is very lopsided. From there, as soon as you see the EXPLAIN, you know how to fix it: drop the index.
waynecochran 4y ago
I would add KD-Tree and BSP-Tree as generalizations of a binary search tree in higher dimensions.
taeric 4y ago
Fun list! Other things I'd recommend trying: Huffman coding Binary decision diagrams Simplex method General modeling of a problem to SAT The last one there is particularly fun. Finding a way to solve a problem fast by mapping it to a silly large set of variables is surprisingly fun.
- pfdietz 4y ago
  Suffix trees
  - evouga 4y ago
    Yes! Most of the examples of “challenging” algorithms in the blog post are actually fairly elementary stuff covered in undergrad algorithms. Suffix arrays though (especially linear-time construction) are the real deal.
ComputerGuru 4y ago
At this point, everyone knows about bloom filters simply because it’s the thing to write about any time someone asks “lesser known data structures/algorithms?” - it’s hard to find a list that doesn’t feature them! Still some good entries in that list. I would add skip lists, not because they’re structurally anything special but because they open your mind to the possibly entirely-new-to-the-reader world of probabilistic data structures. As someone that’s been around the block, something I’ve learned to be less surprised by is how often simply adding an element of randomness to a difficult problem can sometimes give you results comparable to a 10- or 100-times more complicated solution, with the advantage of being more maintainable, making better use of the i$, and avoiding a lot of work. (Eg compare a cache dropping randomly selected items to LFU or LRU caches.)
- Jensson 4y ago
  Randomness is very useful to handle edge cases, quicksort is the poster child here, it has some edge cases were it runs extremely slowly but randomising how you apply the algorithm means that you can ignore them since they are so unlikely. If you try to use deterministic code then those rare edge cases often comes up in the real world.
- PartiallyTyped 4y ago
  > I’ve learned to be less surprised by is how often simply adding an element of randomness to a difficult problem can sometimes give you results comparable to a 10- or 100-times more complicated solution We tend to use "Las Vegas" and "Monte Carlo" to classify randomised algorithms, where the former means using randomness to get a speedup, and the latter means using randomness to get an approximately correct solution. An example of the former is QuickSort, where we shuffle the elements, giving the Expected nlogn time complexity* . An example of the latter is bloom filters. Other examples are found all over approximation algorithms like taking random cuts off graphs. * Assuming something like Yates shuffling with O(N) complexity is used.
  - chii 4y ago
    and once in a while, the shuffle puts the elements in a pattern that makes quicksort perform worst case (n^2). But i guess that is rare, the larger the list! So in practice, it works.
TrackerFF 4y ago
Call me cynical, but every time I see interesting threads like these - I can't help but to think that somewhere, a hiring manager is thinking to himself "Nice, I'll add these to the technical (interview) questions"
Xeoncross 4y ago
> Google asked me two interview problems involving these back when I was in college. Have I ever needed this in practice? Nope! This is the shame of the Big Tech. I've used bloomfilters, tries, and many other of these multiple times on side projects with constraints, but would something like this ever make it into a deployed system at FAANG by all the regular devs? No, just use dynamo, spanner or a bigger cluster + more workers, more queues, add more k8s nodes, plus whatever cloud tech you should be using to "horizontally scale" and be "distributed". Not that there aren't awesome devs at these companies which do code responsibly, but I don't often see it. I can't believe how unperformant the systems I've often seen in Big Tech are. I want more people to read the article about fitting the whole level into a single byte[1] and stop using big budgets as a way to be irresponsible. 1: https://news.ycombinator.com/item?id=34095954 https://news.ycombinator.com/item?id=34095954
- juancn 4y ago
  Somebody implements that infra, and in many cases you need to use them to build it, and it's important to understand them. I'm not asking you implement one from memory, but at least have some knowledge of its properties and the reasoning behind their design. For example Bloom filters are a probabilistic data structure, even if you don't use one as is, it's a representative algorithm of whole class of techniques that can be used when exact answers are not required. For example, at scale, if you have something that can cheaply shed 90% of the load without falling back to a more expensive precise algorithm is a big win. Or Splay trees, binary trees, etc. the notion of self balancing structures and the concept of "divide and conquer" as a problem solving strategy. All these add something to your toolbox and in many cases can make a huge difference on the type of solutions that you can come up with other than "throw more money at it". Many people miss the point on these, it's like learning math, it's the way you learn to think that matters, not the particular piece of math you learn.
- Jensson 4y ago
  I think the problem with slow user interfaces is that the programmers who knows how to make things fast usually want to work on more interesting algorithms instead of optimising UI interactions. I built model evaluators at Google so I used a lot of these algorithms, specifically topological sort is useful in so many places and you can't really make a generic solution for it to put in a library, and different parsing methods. When doing this I had to look at how many nanoseconds different ways to do things costs, because things are run billions of times on large models in production so it is very expensive. The people on that team were really good at making things run fast, but I haven't seen that kind of people doing user interfaces, instead even at Google some internal pages took minutes to load with barely any data, I could run a batch job spinning up thousands of servers over terabytes of data in the time it took just to view my account in that service. The silver lining is that Google has many alternatives for everything so I could use something else instead. I guess a part of it is that Google pays for server compute, but not client compute, so your computer running slowly isn't a big deal compared to their server costs, so the optimizing programmers gets placed on backends. I did work on message routers as well, they have to be blazing fast, so I know how to make network requests fasts, the only reason the UI's are slow is that the companies aren't prioritizing it.
charlieyu1 4y ago
Thank you. Never really figure out how parser works but maybe I should try and write one
- tgv 4y ago
  I've always found writing parsers very rewarding. There are different parsing methods. The article mentions top-down recursive descent parsing. That's the easiest to do by hand, but you can't parse everything that way (or not easily). Bottom-up parsing is another strategy, which works (in principle) for all unambiguous grammars. The lazy solution is backtracking (try a rule, back up if it fails), and add memoization to keep the runtime acceptable. This is the basis for the so-called PEG parsers. There's a lot of formal literature. E.g., top-down recursive descent is a class known as LL(k), bottom-up is LR(k), and there are algorithms to derive parsers from grammars. It is however not the easiest starting point.
todd8 4y ago
This is an interesting list. I'd add hashing and hash tables to the list. There are lots of interesting variations of these as well. I would put hash tables ahead of piece tables because of their generality. For text editors I've always thought that gap buffers were so straightforward that ropes and piece tables seemed like extra unnecessary work. I see that VS Code uses piece tables so perhaps someone can explain the performance differences to me. I've never sat down and benchmarked various implementations of text buffers. However, it seems to me that memmove(3) on modern processors would be so fast that moving a buffer gap on even a 1GB file wouldn't be perceptible, and in return operations over the whole buffer like string searching or parsing would be much more efficient in a gap buffer because the program could count on the buffer being in contiguous memory locations (after closing the gap). In buffers implemented using a part table or ropes, every character access involves extra layers of indirection. Furthermore, gap buffers are going to be more cache friendly for the way that most editing operations take place in a text editor. Perhaps someone that has actually done some comparisons could enlighten me.
- TYMorningCoffee 4y ago
  I think the author excluded hashing because it is too well known.
  - todd8 4y ago
    That makes sense, thanks.
- peterfirefly 4y ago
  Piece tables give you fast and easy undo.
zelphirkalt 4y ago
I often find myself thinking: "But how would I do any of these without reaching for mutation? So that I can later parallelize them?" And then I come up empty. I still need to work through "Purely Functional Data Structures" by Okasaki. Hopefully then I will have an idea, of how to come up with a functional version to mostly single-core algorithms or at least locking-requiring algorithms. I skipped ahead once and looked at functional red-black trees and the solution was to involve one more color! How ingenious is that?! I have no idea, how people got to these solutions. In many places algorithms are described implicitly with mutation assumed. However, this can be very hard to parallelize later and might hit you in the future. In the times of many cores, this seems no longer appropriate to me. I wish we spent more time on learning how to get it done without mutation. Another great post that was linked at some point on HN was this: https://nullprogram.com/blog/2020/04/30/ https://nullprogram.com/blog/2020/04/30/ -- A comparatively simple change in approach and yet it allows for massive parallelization without locks! This is the kind of stuff we should learn more about and then make more use of our many available cores, moving on from the single core world of algorithms.
- samsquire 4y ago
  I am deeply interested in parallelism. Would enjoy talking to you about it. I think the parallelism provided by Haskell is really interesting. And its software transactional memory. I think parallelisation can be generalised but we need to study it further to understand it better. There must be a set of primitives that parallelise very well but they've not been found out yet. Rather than trying to parallelise something that was invented to be sequential, we parallelise something that is parallelisable. I'm today working on parallelising a total ordered list view over X sorted lists that are maintained by separate threads or independent computer servers. My idea is to use N way mergesort to retrieve up to N items sorted items. Servicing requests is extremely fast since there is no synchronization needed within a thread or server but if you need total order, you need to use the N way mergesort. I'm thinking you have a cluster for ordered views and a cluster for within-a-thread view. My other problem I'm working on is how to paralellise integer updates. If you have 8000000000 accounts (which DOES fit on a single machine) but you have more operations overall than a single machine can process? You could shard by account but I think there's an approach that shards by integer and per server. You store a portion of the integer on each machine, hopefully enough to handle operations. Then when you need to check if account integer > deduction amount I just need to learn how to a strongly consistent read cheaply. Essentially we load balance the integer in the account. For example, fibonacci is often used as an example to parallelise something but it's never implemented in a parallelisable manner. It just does the same calculation in different threads. If we knew the formula of fibonacci that didn't depend on previous iterations, we could parallelise fibonacci. But I'm not a mathematician so I I'm not sure how to find out that formula.
rrgok 4y ago
I like algorithms and data structures. One of the thing I, personally, find hard about Algos and DS, is that I don't know when to use which. For example, I could never ever come up with my own, that the traveling salesman problem can have a good solution with ant colony optimization or simulated annealing. How do I learn that skill? I still don't know when to use a graph for what kind of problem. I hope someone can shed some light on this.
- Jensson 4y ago
  You get good at this from a long life of curiosity in the subject. Basically, if you spent your life testing many different ways to do things, think thousands of different ways to compute or parse or view data etc, then you have that huge knowledge bank to aid you when you see a new problem, so you compose a few of those things to solve it. It is the same process as learning the elementary algebra in math. You learn a few basic techniques, like moving numbers and variables from one side to the other, and then you compose those to solve expressions you haven't seen before. The only difference is that algorithms is a much larger space, there are way more techniques and problems there so it takes longer to get to a point where it is useful to you.
- jpitz 4y ago
  The Algorithm Design Manual, which maybe should have been named The Algorithm Selection Manual. https://www.goodreads.com/book/show/425208.The_Algorithm_Design_Manual https://www.goodreads.com/book/show/425208.The_Algorithm_Des...
- TheEndIsNigh 4y ago
  You need to solve hard problems. Code Jam is an amazing source for this. Just don't expect to knock them out in 5 minutes. Pick a hard problem and stay a week with it trying different ideas and compare the time complexity.
  - djur 4y ago
    So far most of the resources I've found for this kind of thing don't really provide enough guidance in what algorithms to choose and why, mostly because they're usually designed as competitions. I'm not interested in competing with other programmers, I want to learn from them.
TheEndIsNigh 4y ago
Not exactly challenging, they're covered in a decent undergrad Algorithms course.
- cinntaile 4y ago
  They were challenging when you learned them. It doesn't really matter when or where that was.
PaulDavisThe1st 4y ago
Although it is somewhat embarrassing to admit this, when I wrote JACK [0] I was unaware of topological sort, mostly due to a lack of any formal CS education. This was a major error/failing on my part, because that codebase was more or less made for TS. There have been few other instances where a lack of formal CS training has been an impediment, but not knowing that there was a well-known algorithm for ordering node execution in a directed graph was ... bad. [0] https://jackaudio.org/ https://jackaudio.org/
djur 4y ago
What I would be interested in is some kind of resource (book, video series, etc.) where someone presents a reasonably "real-world" problem, discusses the thought process in choosing an implementation, and steps through the process of implementing, testing, and iterating on the solution. It's easy to find sources for hard problems to solve, and it's easy to find sources for explanations of algorithms and data structures, but I haven't found much to bridge the gap.
- justinlloyd 4y ago
  That is a very good idea. I think I have the germ of an idea for a new set of videos.
- sitkack 4y ago
  I thought of something similar, but going over how early computers were used, from precalculating ballistics tables, to solving cut-and-cover for building roads. I always loved the story problems because they showed how math was useful for figuring things out, they gave examples of predictive power. You might really like the lectures from https://www.csail.mit.edu/person/erik-demaine https://www.csail.mit.edu/person/erik-demaine Or the AOSA book, https://aosabook.org/en/ https://aosabook.org/en/
galkk 4y ago
This is related to one of my fun stories. During an interview to one company, I got asked topological sort question. I passed, but in couple of months I needed to troubleshoot why host app has a problem loading addons. I started digging and found that their implementation of topological sort was wrong…
- layer8 4y ago
  Sounds like they made the right choice in hiring the expertise they were missing. ;)
m0rissette 4y ago
> Alright, so we are all spending our leisure time reading about algorithms, right? Obviously, right?
- keepquestioning 4y ago
  If you aren't preparing for your next interview this holiday period, you are seriously screwing up.
nikisweeting 4y ago
Surprised HyperLogLog didn't get mentioned considering Bloom filters were such a popular suggestion. https://en.wikipedia.org/wiki/HyperLogLog https://en.wikipedia.org/wiki/HyperLogLog
yeputons 4y ago
> Segment tree Note that there are at least two data structures with the same name (three if you also count interval tree): the one used in competitive programming for fast queries on subsegments of a changing array, and two used for storing segments/intervals on a line in slightly different ways. Wikipedia describes the latter.
kens 4y ago
I'd put Fourier transforms on the list of algorithms that are extremely useful to know. (Well, not exactly the algorithm itself as much as the concept.) Many things make a lot of sense if you understand Fourier transforms, such as computer graphics, audio processing, signal processing, image processing, data analysis, filtering, and electronics. But Fourier transforms get hardly any attention on HN.
- e9 4y ago
  Agreed, here is a good introduction with many examples: http://www.dspguide.com/pdfbook.htm http://www.dspguide.com/pdfbook.htm
EnderShadow8 4y ago
Segment trees are the foundation upon which all of competitive programming is built.
nayuki 4y ago
The OP's list is decent. Here are my suggestions for moderately challenging algorithms to understand and implement: B-tree Cooley-Tukey radix-2 FFT CRC-32 DEFLATE decoder Gauss-Jordan elimination JSON parser SHA-1 hash
mybrid 4y ago
I don't have a problem with the article. I do have a problem with the "every programmer". Not every programmer writes sophisticated algorithms. In fact, in my experience working on web sites most programmers are front end developers coding web sites or back end developers shuffling data around. The most sophisticated algorithm they need is a for loop. Occasionally one needs and algorithm developer to work on scale out. Next time try, "challenging algorithms and data structures every algorithm programmer should try."
askvictor 4y ago
In my most recent job, my first real task was to implement a persistent (i.e. flash-disk-based) queue. In (micro)python. Seems simple enough, until real world performance constrains kick in, and suddenly things get much, much more interesting. Need to keep flash happy, so wear-levelling is a concern; not a problem using LittleFS (as it's designed for flash disks), but that ends up taking massive amounts of time for seeking. And we have an upper bound on allowable time for an operation, which throws out any naive solution. Implementing algorithms is easy. Implementing algorithms with constraints... not so much (but still fun though)

439 points by whack 4y ago

I recommend https://web.stanford.edu/class/cs168/index.html https://web.stanford.edu/class/cs168/index.html

Thanks for the list. First time I coded a Trie I thought it was super cool. Topological sort is such a useful one as well.

Turing_Machine 4y ago
Tries are probably the one I've used the most in the real world, so I guess if I were making such a list it'd be on the main one, not in the honorable mention section. I'm not sure which one I'd remove to make space for it, though. I second the recommendation for Jeff Erickson's book. He is an awesome in-person instructor, too.

anigbrowl 4y ago

Nicely written. Hits a spot that a lot of instructional and documentary material misses - telling the reader up front what common problem each technique solves.

samsquire 4y ago

Wikipedia is sometimes enough to implement an algorithm. I implemented multiversion concurrency control and btrees due to Wikipedia which do not have pseudocode. If you can implement an algorithm from an English description that is really useful. It relies on the algorithm being well explained. I also suggest trying to implement a btree, they're really useful data structures for data retrieval and many database products use them extensively for indexes. With any algorithm, I think there is a critical insight (that might be different for each person) where the algorithm clicks. I didn't understand mergesort properly until I worked on implementing it but I understood quicksort. When the underlying mental model of the problem being solved becomes clear, we can reason about the algorithm and write code to implement what we want to do.

withinboredom 4y ago
I also recommend this. It can really help when trying to understand why a query may be slow even though you’re using indices. For example, one index was on a Boolean field and the query took several seconds. Most rows were “true” and very rarely did we query for false, and when we did query for false, latency was acceptable. If you know a btree is being used under the hood, you can imagine what the tree looks like and that it is very lopsided. From there, as soon as you see the EXPLAIN, you know how to fix it: drop the index.

waynecochran 4y ago

I would add KD-Tree and BSP-Tree as generalizations of a binary search tree in higher dimensions.

taeric 4y ago

Fun list! Other things I'd recommend trying: Huffman coding Binary decision diagrams Simplex method General modeling of a problem to SAT The last one there is particularly fun. Finding a way to solve a problem fast by mapping it to a silly large set of variables is surprisingly fun.

pfdietz 4y ago
Suffix trees
- evouga 4y ago
  Yes! Most of the examples of “challenging” algorithms in the blog post are actually fairly elementary stuff covered in undergrad algorithms. Suffix arrays though (especially linear-time construction) are the real deal.

ComputerGuru 4y ago

At this point, everyone knows about bloom filters simply because it’s the thing to write about any time someone asks “lesser known data structures/algorithms?” - it’s hard to find a list that doesn’t feature them! Still some good entries in that list. I would add skip lists, not because they’re structurally anything special but because they open your mind to the possibly entirely-new-to-the-reader world of probabilistic data structures. As someone that’s been around the block, something I’ve learned to be less surprised by is how often simply adding an element of randomness to a difficult problem can sometimes give you results comparable to a 10- or 100-times more complicated solution, with the advantage of being more maintainable, making better use of the i$, and avoiding a lot of work. (Eg compare a cache dropping randomly selected items to LFU or LRU caches.)

Jensson 4y ago
Randomness is very useful to handle edge cases, quicksort is the poster child here, it has some edge cases were it runs extremely slowly but randomising how you apply the algorithm means that you can ignore them since they are so unlikely. If you try to use deterministic code then those rare edge cases often comes up in the real world.
PartiallyTyped 4y ago
> I’ve learned to be less surprised by is how often simply adding an element of randomness to a difficult problem can sometimes give you results comparable to a 10- or 100-times more complicated solution We tend to use "Las Vegas" and "Monte Carlo" to classify randomised algorithms, where the former means using randomness to get a speedup, and the latter means using randomness to get an approximately correct solution. An example of the former is QuickSort, where we shuffle the elements, giving the Expected nlogn time complexity* . An example of the latter is bloom filters. Other examples are found all over approximation algorithms like taking random cuts off graphs. * Assuming something like Yates shuffling with O(N) complexity is used.
- chii 4y ago
  and once in a while, the shuffle puts the elements in a pattern that makes quicksort perform worst case (n^2). But i guess that is rare, the larger the list! So in practice, it works.

TrackerFF 4y ago

Call me cynical, but every time I see interesting threads like these - I can't help but to think that somewhere, a hiring manager is thinking to himself "Nice, I'll add these to the technical (interview) questions"

Xeoncross 4y ago

> Google asked me two interview problems involving these back when I was in college. Have I ever needed this in practice? Nope! This is the shame of the Big Tech. I've used bloomfilters, tries, and many other of these multiple times on side projects with constraints, but would something like this ever make it into a deployed system at FAANG by all the regular devs? No, just use dynamo, spanner or a bigger cluster + more workers, more queues, add more k8s nodes, plus whatever cloud tech you should be using to "horizontally scale" and be "distributed". Not that there aren't awesome devs at these companies which do code responsibly, but I don't often see it. I can't believe how unperformant the systems I've often seen in Big Tech are. I want more people to read the article about fitting the whole level into a single byte[1] and stop using big budgets as a way to be irresponsible. 1: https://news.ycombinator.com/item?id=34095954 https://news.ycombinator.com/item?id=34095954

juancn 4y ago
Somebody implements that infra, and in many cases you need to use them to build it, and it's important to understand them. I'm not asking you implement one from memory, but at least have some knowledge of its properties and the reasoning behind their design. For example Bloom filters are a probabilistic data structure, even if you don't use one as is, it's a representative algorithm of whole class of techniques that can be used when exact answers are not required. For example, at scale, if you have something that can cheaply shed 90% of the load without falling back to a more expensive precise algorithm is a big win. Or Splay trees, binary trees, etc. the notion of self balancing structures and the concept of "divide and conquer" as a problem solving strategy. All these add something to your toolbox and in many cases can make a huge difference on the type of solutions that you can come up with other than "throw more money at it". Many people miss the point on these, it's like learning math, it's the way you learn to think that matters, not the particular piece of math you learn.
Jensson 4y ago
I think the problem with slow user interfaces is that the programmers who knows how to make things fast usually want to work on more interesting algorithms instead of optimising UI interactions. I built model evaluators at Google so I used a lot of these algorithms, specifically topological sort is useful in so many places and you can't really make a generic solution for it to put in a library, and different parsing methods. When doing this I had to look at how many nanoseconds different ways to do things costs, because things are run billions of times on large models in production so it is very expensive. The people on that team were really good at making things run fast, but I haven't seen that kind of people doing user interfaces, instead even at Google some internal pages took minutes to load with barely any data, I could run a batch job spinning up thousands of servers over terabytes of data in the time it took just to view my account in that service. The silver lining is that Google has many alternatives for everything so I could use something else instead. I guess a part of it is that Google pays for server compute, but not client compute, so your computer running slowly isn't a big deal compared to their server costs, so the optimizing programmers gets placed on backends. I did work on message routers as well, they have to be blazing fast, so I know how to make network requests fasts, the only reason the UI's are slow is that the companies aren't prioritizing it.

charlieyu1 4y ago

Thank you. Never really figure out how parser works but maybe I should try and write one

tgv 4y ago
I've always found writing parsers very rewarding. There are different parsing methods. The article mentions top-down recursive descent parsing. That's the easiest to do by hand, but you can't parse everything that way (or not easily). Bottom-up parsing is another strategy, which works (in principle) for all unambiguous grammars. The lazy solution is backtracking (try a rule, back up if it fails), and add memoization to keep the runtime acceptable. This is the basis for the so-called PEG parsers. There's a lot of formal literature. E.g., top-down recursive descent is a class known as LL(k), bottom-up is LR(k), and there are algorithms to derive parsers from grammars. It is however not the easiest starting point.

todd8 4y ago

This is an interesting list. I'd add hashing and hash tables to the list. There are lots of interesting variations of these as well. I would put hash tables ahead of piece tables because of their generality. For text editors I've always thought that gap buffers were so straightforward that ropes and piece tables seemed like extra unnecessary work. I see that VS Code uses piece tables so perhaps someone can explain the performance differences to me. I've never sat down and benchmarked various implementations of text buffers. However, it seems to me that memmove(3) on modern processors would be so fast that moving a buffer gap on even a 1GB file wouldn't be perceptible, and in return operations over the whole buffer like string searching or parsing would be much more efficient in a gap buffer because the program could count on the buffer being in contiguous memory locations (after closing the gap). In buffers implemented using a part table or ropes, every character access involves extra layers of indirection. Furthermore, gap buffers are going to be more cache friendly for the way that most editing operations take place in a text editor. Perhaps someone that has actually done some comparisons could enlighten me.

TYMorningCoffee 4y ago
I think the author excluded hashing because it is too well known.
- todd8 4y ago
  That makes sense, thanks.
peterfirefly 4y ago
Piece tables give you fast and easy undo.

zelphirkalt 4y ago

I often find myself thinking: "But how would I do any of these without reaching for mutation? So that I can later parallelize them?" And then I come up empty. I still need to work through "Purely Functional Data Structures" by Okasaki. Hopefully then I will have an idea, of how to come up with a functional version to mostly single-core algorithms or at least locking-requiring algorithms. I skipped ahead once and looked at functional red-black trees and the solution was to involve one more color! How ingenious is that?! I have no idea, how people got to these solutions. In many places algorithms are described implicitly with mutation assumed. However, this can be very hard to parallelize later and might hit you in the future. In the times of many cores, this seems no longer appropriate to me. I wish we spent more time on learning how to get it done without mutation. Another great post that was linked at some point on HN was this: https://nullprogram.com/blog/2020/04/30/ https://nullprogram.com/blog/2020/04/30/ -- A comparatively simple change in approach and yet it allows for massive parallelization without locks! This is the kind of stuff we should learn more about and then make more use of our many available cores, moving on from the single core world of algorithms.

samsquire 4y ago
I am deeply interested in parallelism. Would enjoy talking to you about it. I think the parallelism provided by Haskell is really interesting. And its software transactional memory. I think parallelisation can be generalised but we need to study it further to understand it better. There must be a set of primitives that parallelise very well but they've not been found out yet. Rather than trying to parallelise something that was invented to be sequential, we parallelise something that is parallelisable. I'm today working on parallelising a total ordered list view over X sorted lists that are maintained by separate threads or independent computer servers. My idea is to use N way mergesort to retrieve up to N items sorted items. Servicing requests is extremely fast since there is no synchronization needed within a thread or server but if you need total order, you need to use the N way mergesort. I'm thinking you have a cluster for ordered views and a cluster for within-a-thread view. My other problem I'm working on is how to paralellise integer updates. If you have 8000000000 accounts (which DOES fit on a single machine) but you have more operations overall than a single machine can process? You could shard by account but I think there's an approach that shards by integer and per server. You store a portion of the integer on each machine, hopefully enough to handle operations. Then when you need to check if account integer > deduction amount I just need to learn how to a strongly consistent read cheaply. Essentially we load balance the integer in the account. For example, fibonacci is often used as an example to parallelise something but it's never implemented in a parallelisable manner. It just does the same calculation in different threads. If we knew the formula of fibonacci that didn't depend on previous iterations, we could parallelise fibonacci. But I'm not a mathematician so I I'm not sure how to find out that formula.

rrgok 4y ago

I like algorithms and data structures. One of the thing I, personally, find hard about Algos and DS, is that I don't know when to use which. For example, I could never ever come up with my own, that the traveling salesman problem can have a good solution with ant colony optimization or simulated annealing. How do I learn that skill? I still don't know when to use a graph for what kind of problem. I hope someone can shed some light on this.

Jensson 4y ago
You get good at this from a long life of curiosity in the subject. Basically, if you spent your life testing many different ways to do things, think thousands of different ways to compute or parse or view data etc, then you have that huge knowledge bank to aid you when you see a new problem, so you compose a few of those things to solve it. It is the same process as learning the elementary algebra in math. You learn a few basic techniques, like moving numbers and variables from one side to the other, and then you compose those to solve expressions you haven't seen before. The only difference is that algorithms is a much larger space, there are way more techniques and problems there so it takes longer to get to a point where it is useful to you.
jpitz 4y ago
The Algorithm Design Manual, which maybe should have been named The Algorithm Selection Manual. https://www.goodreads.com/book/show/425208.The_Algorithm_Design_Manual https://www.goodreads.com/book/show/425208.The_Algorithm_Des...
TheEndIsNigh 4y ago
You need to solve hard problems. Code Jam is an amazing source for this. Just don't expect to knock them out in 5 minutes. Pick a hard problem and stay a week with it trying different ideas and compare the time complexity.
- djur 4y ago
  So far most of the resources I've found for this kind of thing don't really provide enough guidance in what algorithms to choose and why, mostly because they're usually designed as competitions. I'm not interested in competing with other programmers, I want to learn from them.

TheEndIsNigh 4y ago

Not exactly challenging, they're covered in a decent undergrad Algorithms course.

cinntaile 4y ago
They were challenging when you learned them. It doesn't really matter when or where that was.

PaulDavisThe1st 4y ago

Although it is somewhat embarrassing to admit this, when I wrote JACK [0] I was unaware of topological sort, mostly due to a lack of any formal CS education. This was a major error/failing on my part, because that codebase was more or less made for TS. There have been few other instances where a lack of formal CS training has been an impediment, but not knowing that there was a well-known algorithm for ordering node execution in a directed graph was ... bad. [0] https://jackaudio.org/ https://jackaudio.org/

djur 4y ago

What I would be interested in is some kind of resource (book, video series, etc.) where someone presents a reasonably "real-world" problem, discusses the thought process in choosing an implementation, and steps through the process of implementing, testing, and iterating on the solution. It's easy to find sources for hard problems to solve, and it's easy to find sources for explanations of algorithms and data structures, but I haven't found much to bridge the gap.

justinlloyd 4y ago
That is a very good idea. I think I have the germ of an idea for a new set of videos.
sitkack 4y ago
I thought of something similar, but going over how early computers were used, from precalculating ballistics tables, to solving cut-and-cover for building roads. I always loved the story problems because they showed how math was useful for figuring things out, they gave examples of predictive power. You might really like the lectures from https://www.csail.mit.edu/person/erik-demaine https://www.csail.mit.edu/person/erik-demaine Or the AOSA book, https://aosabook.org/en/ https://aosabook.org/en/

galkk 4y ago

This is related to one of my fun stories. During an interview to one company, I got asked topological sort question. I passed, but in couple of months I needed to troubleshoot why host app has a problem loading addons. I started digging and found that their implementation of topological sort was wrong…

layer8 4y ago
Sounds like they made the right choice in hiring the expertise they were missing. ;)

m0rissette 4y ago

> Alright, so we are all spending our leisure time reading about algorithms, right? Obviously, right?

keepquestioning 4y ago
If you aren't preparing for your next interview this holiday period, you are seriously screwing up.

nikisweeting 4y ago

Surprised HyperLogLog didn't get mentioned considering Bloom filters were such a popular suggestion. https://en.wikipedia.org/wiki/HyperLogLog https://en.wikipedia.org/wiki/HyperLogLog

yeputons 4y ago

> Segment tree Note that there are at least two data structures with the same name (three if you also count interval tree): the one used in competitive programming for fast queries on subsegments of a changing array, and two used for storing segments/intervals on a line in slightly different ways. Wikipedia describes the latter.

kens 4y ago

I'd put Fourier transforms on the list of algorithms that are extremely useful to know. (Well, not exactly the algorithm itself as much as the concept.) Many things make a lot of sense if you understand Fourier transforms, such as computer graphics, audio processing, signal processing, image processing, data analysis, filtering, and electronics. But Fourier transforms get hardly any attention on HN.

e9 4y ago
Agreed, here is a good introduction with many examples: http://www.dspguide.com/pdfbook.htm http://www.dspguide.com/pdfbook.htm

EnderShadow8 4y ago

Segment trees are the foundation upon which all of competitive programming is built.

nayuki 4y ago

The OP's list is decent. Here are my suggestions for moderately challenging algorithms to understand and implement: B-tree Cooley-Tukey radix-2 FFT CRC-32 DEFLATE decoder Gauss-Jordan elimination JSON parser SHA-1 hash

mybrid 4y ago

I don't have a problem with the article. I do have a problem with the "every programmer". Not every programmer writes sophisticated algorithms. In fact, in my experience working on web sites most programmers are front end developers coding web sites or back end developers shuffling data around. The most sophisticated algorithm they need is a for loop. Occasionally one needs and algorithm developer to work on scale out. Next time try, "challenging algorithms and data structures every algorithm programmer should try."

askvictor 4y ago

In my most recent job, my first real task was to implement a persistent (i.e. flash-disk-based) queue. In (micro)python. Seems simple enough, until real world performance constrains kick in, and suddenly things get much, much more interesting. Need to keep flash happy, so wear-levelling is a concern; not a problem using LittleFS (as it's designed for flash disks), but that ends up taking massive amounts of time for seeking. And we have an upper bound on allowable time for an operation, which throws out any naive solution. Implementing algorithms is easy. Implementing algorithms with constraints... not so much (but still fun though)