Challenging algorithms and data structures every programmer should try
austinhenley.com
austinhenley.com
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.
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.
dynamo, spanner ect were written by devs at FAANG . Do they have special interview channels for 'regular devs' and another for people who can write dynamo ?
Not much different from databases of old. Writing a good sorting algorithms feels excessive in many applications. The number of such algorithms that the planner of a database picks between is rather large.
Not special interviews, but certainly different pieces of headcount. There are Googlers and there are Googlers. Being the second is a lot more work, but a lot more interesting.
Some people directly join sexy teams, but that probably means they have some accomplishments from before, the hard part is getting a foot in that door and the unsexy infrastructure teams are a great place to start since there are tons of problems to solve there and not much competition for that kind of work. Most people just want to work with data models or publicly visible products, not the invisible services that moves millions of requests per second, but anything that moves millions of requests per second will be easy to have impact with.
Ironically I failed the System one because I think the interviewer didn't actually understand the algorithms or solutions and was working off a checklist of expected buzzwords.
I spent about it 30 minutes working through a design with him putting down all my decisions. Halfway through he tells me I don't seem to be aware of this certain data structure which is necessary, so he'll tell it to me: A quadtree.
My original choice was an R-Tree, I tried to tell him it's faster for windowed queries, more accurate when it comes to large locations. The only real downside relative to a quadtree is slower inserts and deletes [0]. He just kept looking at his second monitor and telling me "Well this says a quadtree is the most efficient method". Couldn't tell me why, just that his notes say so.
[0] we had discussed at the start of the question, expectations of 1B queries/day, with an acceptable update latency of 24 hours.
Same goes for many of these algorithms. They are amazing, but also require a simplicity of problem that is hard to pull back to. Worse, they often solidify the program into something that is very rigidly defined and not conducive to change.
Computer Science tends to focus on programming in the small to medium, and software engineering tends to focus more on programming in the medium to large.
It's one thing to optimize a small piece of functionality fully, but it's another thing to put together a product that has thousands of live users, hundreds of features, multitude of configuration modes, distributed globally, etc.
If I ask you to clean a bathroom in 3 hours, and then I ask you to clean the whole house in 3 hours, your approach to the cleaning will be very different between the two, and the first thing that will be cut is your attention to details.
Now, implementing one of them on a whiteboard or without access to internet, knowing all of their intricacies and edge cases…that is stuff I doubt anyone needs to know except a very specific type of developer. If i want an optimized trie I use a library, and when it breaks and i need to fix the low-level implementation, i look it up online
I'm not sure I've ever seen a skip list outside of an algorithms book.
This field we're working in, it's pretty neat.
I still know how to do it, but I’d have to really stop and ask myself why I thought it was a good idea first. Because it probably wouldn’t be.
Conversely if you love algorithms and are sufficiently good at them then you can spend your entire career with that and never ever talk to non-technical people. Some people here thinks those jobs basically don't exist, but they do exist and are really important and well paid. And once you start working there you can just continue forever since there are so few who have experience working with those. Like, maybe Google asks algorithm questions since they want more people to improve their algorithms? I know they had low hanging fruit everywhere, they just lacked people who were competent enough at algorithms to solve them, their hiring bar is way too low to solve their hard problems. But they can't really raise it either, there aren't enough people that could pass them then.
I think there are two types of programmers. Ones that are like you that like algorithms for algorithms sake. And the other that like to solve real world problems. I got into software development because I want to solve problems for people. And not all of us likes algo. We prefer to learn stuff that we do use day to day because that has direct impact. For example, I just spent two months understanding functional programming. I use it in my code almost everyday, but it would be worthless in an interview where you are judge by your algo understanding. It’s frustrating when you realize how this standard is forced on every technical role, on companies that don’t even need algo experts because they are too small.
That is, to one without a hammer, nothing looks like a nail.
They irony of this is that for one with a hammer, everything looks like a nail.
The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times; premature optimization is the root of all evil (or at least most of it) in programming. Donald Knuth.
Knowing when to apply something is just as important as know where
A lack of hammer implies only having a screwdriver.
The point is you should have a tool box (and garage and workshop and spare bedroom) full of tools so you have the exact tool you actually need.
What the Phillips head and pozidrive represent in this metaphor are left as an exercise for the reader. As is the adjustable spanner.
In-memory skiplists, I'm still skeptical of.
for config I used ini files, super simple to parser (and now json so always can use an existing solution)
I've seldom implemented parsing, since we had Lisp, XML, and now YAML. However, I use language translation all the time.
Ever since I became a SWE rather than a researcher, I haven’t found a case to write another one, however. It’s much easier just to embed the DSL in kotlin.
(And I didn’t know about any of the data structures or algos mentioned in the post - I’d never have been hired at a FAANG)
I also thought there were skip-lists used in some part of the kernel or a driver but I don't remember: searching brings up https://lwn.net/Articles/551896/
I'm sure the dynamo team, the spanner team and etc are using all the techniques to make their database performant.
Time to market and solving business problems don't care about performance you'll never see. This is so obvious, I can't relate to your writing.
If I see a developer pack a data structure as tiny as possible I will not sign off on CR until it's done in a more clearly reading and maintainable way. Unless you're working on high performance applications or similar, you're pissing in the wind.
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.
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.
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.
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.)
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.
We have 2/(n!) probability that the shuffle sorts the list either way. The probability that it happens on the second level is 2/((n-1)!).
So the probability that it happens twice is 4/(1^2 * 2^2 … (n-1)^2 * n)
Which ends up being prod_{i=1} ^N i ^ i
It’s so astronomically unlikely, that it just never does.
Suppose you partition your test input set into N different partitions of equal size, and you want, for each partition, to have a test input from that partition. If you just generate random tests then on average after generating N log N tests you will have hit each partition at least once. And this is true not just of the partitions you choose, but ANY N partitions of equal size.
I think it's not that randomly (no pun intended) adding randomness to an existing algorithm or solution could improve it, but that sometimes a random sampling process mimics the underlying problem.
For caching, the assumption that LRU item should be ejected is that - an assumption. If you checked this assumption and found that it was wrong, but that instead the access patterns are random, then dropping random items _do_ mimic the problem domain, and that makes it a better solution!
The solution fails for specific non-random access scenarios. Eg you access an item exactly every n-1 accesses: in an LRU, it’ll always be in the cache but in a probabilistic eviction scenario, it’s most likely not going to be in there.
Huffman coding
Binary decision diagrams
Simplex method
General modeling of a problem to SAT
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/ -- 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.
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.
As for distributing heavy computations, Google has done that to compute your search results since almost the beginning. Fan out a request to a huge cluster of servers that all have different parts of their data in ram, then they filter and return the parts of the data that is relevant to you. It is totally possible to do it and return a response to the user in a fraction of a second. Typically it takes a few milliseconds to send data between servers in a data center, you can easily fan out a request to a few hundred servers, let them compute and return something 15 milliseconds later. It costa bit to run that though, Google can afford it since search is worth so much per request, so you got figure out if your usecase is worth that much compute. But it doesn't cost that much more than running the same work on a single server, it depends a bit on how well your servers are collocated.
Btw, frameworks for distributed computing like Apache Spark are way too slow for this, you have to hand roll those. But it really isn't that hard to do, there are programming competitions involving those, a correct solution to these kind of things takes like 30 minutes to write if you know what to do and you have done all the boring infrastructure work to ensure you can contact servers and access the data. That is why most programmers never work with complex algorithms, because the boring and tedious work on all the other parts takes up most of the time and manpower.
Another question is how much time it takes. Lets say we have small data, a few gigabytes or so. Sorting that would still take about 10 seconds to a minute, which is annoyingly slow to users. If that data is distributed over many computers that can each read a subset, then the distributed sorting will go much much quicker so you can do a full sort over the entire dataset within a normal 100ms request SLO. But this assumes that the user needs to sort using arbitrary comparisons, otherwise it is of course much better to just pre sort the dataset and serve it that way.
And even if you have all data locally, if that data doesn't fit in memory distributed would still help. Network within a server cluster is typically faster than communicating with local persistent storage, so distributed you can read it once and send it to the different workers instead of having to read and write it over and over as you'd have to do if you sorted it locally. So in other words, making a computer read X data from disk takes about the same time as getting that data to a distributed set of computers, since you can send data faster than you read it, and this is the worst case for distributed.
Note: This assumes that we can't precompute the sort, meaning the user asks for some ordering they want the items to be sorted in and we have to provide that on the fly. Pre-sorting data once is easy, so I'm not sure why we would discuss that case. Also networking tends to cost a ton more when you run it on others computers like AWS or Azure or Google cloud, then it might not be as viable. Don't they take like 10x more than the cost of networking? But when I worked at Google we got to run distributed jobs juggling a petabyte of data without anyone asking questions, so it can't be that expensive. As long as you didn't make an infinite loop in your distributed program or so nobody cares, and even when a guy did that his job ran for a couple of weeks before people noticed that our compute quota ran out, so I'm pretty sure it can't be expensive. But that amount of networking would probably cost a fortune in Gcloud.
You find it on Wikipedia! The insight that a closed-form solution might exist - "knowing what to Google" - is really all the mathematical insight you need.
But maybe Fibonacci is a stand in for something else in your explanation. I don't follow the definition of the integer updates problem.
Sorry for my poor explanation.
When you shard data, you could shard the record identifier and keep the data on a particular server -OR- you can shard the data itself and mapreduce it.
For example, a file system locally shards the file data into inodes. The sum of all the inodes = the data of the file.
I am trying to split an integer into shards, the sum of the parts is the value.
If account balance is defined as the SUM of all server's amounts, then each server stores a proportion of the data for that user.
If there are 8 servers and a user has £8000 in their bank balance, then you try store £1000 in each server, so any server can serve requests without coordination. If you user wants to spend £25, then that's fine, just deduct the local data. If you the user wants to spend £1001, then you need a globally consistent read since that would drop the balance below 0 for the local replica, and you need to check the other replicas to see if the user has enough.
I think it is related to the ID generation problem. If you have 1000 servers and you need to generate monotonically incrasing ID numbers without clashes between servers, how do you do it without synchronization? Do you split an integer / 1000 and give each server that batch to assign ID numbers out of?
Writing this out has lead me to think that you could run two clusters. One cluster serves sharded data. The other serves a stream of updates from the other servers and keeps a globally consistent value.
With probability, most transactions shall be below the server's proportion and shall be served locally without coordination. Coordination is only necessary rarely - for large purchases.
Independent threads are as independently fast as a single core and they slow down overall when synchronization is introduced. Amdahls law means that the cost of sequential tasks approaches the majority of time compared to the parallel speed up.
My design is to shard by thread. Each thread or machine maintains a sorted shard of the data. Erlang takes a similar approach. If you want a total order view, then you N way mergesort.
I have a lock free algorithm that can do about 1.2 million synchronizations a second across 11 threads. My lock benchmark does 3,444,152 3.4 million requests per second with 11 threads so my lock free algorithm isn't as good as locks. My lock free algorithm doesn't block though.
I'm thinking of calibrating message rate by increasing latency to increase throughput and limit interference for the lock. If I increase message rate to 2500-25000 messages then more messages get transferred per synchronization event.
I replied to your comment here.
In my experience, lock-free solutions tend to not do well when threads share a physical core (vs virtual cores), but ymmv.
I picked 11 threads due to my CPU having 12 logical cores.
With 100 threads and incrementing 10 at a time, the LockBenchmark achieves 3,482,053 requests per second.
With 100 threads the lock free benchmark achieves 17,754,858 requests per second, 10 messages sending per synchronization event at a time.
In other words, the lock free algorithm scales better.
LockBenchmark code https://github.com/samsquire/multiversion-concurrency-contro...
Lock free actor2 algorithm https://github.com/samsquire/multiversion-concurrency-contro...
Also not all work is parallelizable in the way graphics are parallelizable or follow the relatively simple fork-join structure. What about things like actor systems, where each actor may run on another core, each doing different kind of work?
Sometimes one might want to also have good single core performance in parallelized settings, so that the work for a single core gets finished quickly.
I am not convinced the picture is really as black and white as "do parallelized things on GPU, single core things on CPU".
You might really like the lectures from https://www.csail.mit.edu/person/erik-demaine
Or the AOSA book, https://aosabook.org/en/
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.
I hope someone can shed some light on this.
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.
https://www.goodreads.com/book/show/425208.The_Algorithm_Des...
Go on LC and try various approaches compare time-complexities and it will be obvious why you have to use a certain algorithm.
Implementing algorithms is easy. Implementing algorithms with constraints... not so much (but still fun though)
B-tree
Cooley-Tukey radix-2 FFT
CRC-32
DEFLATE decoder
Gauss-Jordan elimination
JSON parser
SHA-1 hashI second the recommendation for Jeff Erickson's book. He is an awesome in-person instructor, too.
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.
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.
Obviously, right?
Next time try, "challenging algorithms and data structures every algorithm programmer should try."