Hacker News Reader

Comment by Xeoncross | Hacker News Reader

> 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

View on HN

Bloom filters, skiplists, tries, recursive descent, etc. are actually used in many systems and I think it’s important to understand how they work at a high-level

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

Recursive descent isn't an oddity; it's a universally useful parsing approach. It isn't the kind of thing where you can "just throw more k8s nodes" at the problem instead; rather, it's one of the simplest ways to throw a parser together quickly.

I'm not sure I've ever seen a skip list outside of an algorithms book.

Skip-lists are a common way to implement unflushed data in persistent LSM trees, for example.

Shows to go you! I'm super weak on durable data structures.

This field we're working in, it's pretty neat.

Redis ordered set is built on top of a skip list: https://github.com/redis/redis/blob/unstable/src/t_zset.c.

Having been in the industry for literally decades, I can’t remember ever having reason to write a parser (except for basic CSV type data or web scraping) in real life. shrug

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.

Having been in the industry literally decades I have worked on three compilers, two assemblers, a couple of DSLs (before we had some of the newer, fancier tools), a few linkers, a couple of tools that needed to figure out dependencies for assembling a build, a couple of databases and a number of video games that specifically required a recursive descent tree walking algorithm. I consider this class of algorithms to be essential alogrithms in the areas where I have worked, but I also know there are algorithms in use other areas of software development that I have absolutely no practical use for, even though, to reiterate, I have literally been in software for decades. Just because an algorithm is of no use to me, doesn't mean it is no use to you. And vice versa.

I think you get what you look after. If you don't feel you want to try to push the boundaries of computing and instead prefer working with people then there are way more opportunities there, you don't even have to be good as long as you can connect clients to databases people will pay you. However to me that isn't why I got into programming, that sort of job isn't anything like the jobs I've had, and it is a bit sad to see people in those jobs drowning out most other opinions about programming.

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.

> 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.

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.

I've never written a parser because I love parsing. I actually kind of hate it, and have always been baffled by the people who nerd out on it. But, like, when I'm working on a problem that needs a parser, I'm glad I can bang one out! Like I said elsewhere: that's happened a bunch of times in my career.

There’s another aspect of this that the knowledge and comfort of being able to put together a parser properly means you’re more likely to identify places where it would be useful, and consider it worth the trouble to do so.

That is, to one without a hammer, nothing looks like a nail.

> 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

I think the metaphor still works.

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.

That's super interesting. I had to within my first couple years of starting my career (I got tasked with writing a scripting language for a product). I'd guess I've parsed something-or-other --- firewall rules, some weird config file or other, C --- about every couple years. It seems super routine to me. But that's just me!

Generally there has always been some pre-existing parser or a basic regex that took 30 seconds to write that I’ve done that with. Maybe I’m blessed?

Could be! I've never had to draw a Bresenham line, but I'm sure lots of people have. :)

In-memory skiplists, I'm still skeptical of.

I skipped that by choosing lisp as my scripting language. took a day to implement. no complex parser required

for config I used ini files, super simple to parser (and now json so always can use an existing solution)

I would do it differently today than I did in 1997.

There are plenty of users for whom having to write configuration in JSON is a significant barrier, either because they find the syntax obtuse or because they want things like comments, multiline strings, or expressions. Using a DSL can be a huge UX improvement in many cases.

I think it's one of those things, where if you have a hammer in your toolset you'll probably bang on a lot more things :)

I've seldom implemented parsing, since we had Lisp, XML, and now YAML. However, I use language translation all the time.

There's lots of cases where people use regexes to do some kind of validation, where simple parsers work better, if you know how to do them.

I’ve written a few tens of parsers during my career using recursive descent…along with lots of type checkers. There are lots of tricks here.

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.

Huh, I did, many times. I think it’s more where we end up working, than universal applicability of these things.

(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)

When we wrote our compiler, it would have been kinda hard to do so without writing a parser.

There was one at work in the 90s. Few of us had heard of it but the search properties against our data in memory were practical and useful (it wasn't just spinning the propeller on our beanies). For years, whenever I'd mention it, no one knew what it was....I suppose it's become more known in the past 10 years.

AFAIK skip-lists are in some high-performance systems. See: https://en.wikipedia.org/wiki/Skip_list#Usages

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/

Tries are not mentioned in the OP and I have yet to see an example where they are actually working well.

They are very useful and widely used in blockchains.

They're different problems, you've got programming in the small, medium and large.

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.

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.

> system at FAANG by all the regular devs?

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 ?

I took the point to be that maybe scale of database engine can get you passed a lot of nuance.

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.

> Do they have special interview channels for 'regular devs' and another for people who can write dynamo ?

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.

I’d love to know more about how one gets to be in the second group at all as a non-Googler - might make working at a FAANG worth it.

The way I went: First get good at algorithms in some way. Then you join an unsexy infrastructure team at Google, there are tons of hard problems and potential for impact there. Then you use your accomplishments from the unsexy infrastructure team to join a sexy team, even at Google the kind of people who can actually improve the hard parts of Google are rare so that move isn't hard to make.

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.

When I interviewed for a high level engineering position at Facebook, the questions I got were were definitely harder than the ones some friends of mine got when interviewing at lower levels. I also had a "System Design Interview" which they did not have.

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.

> 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

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 mean, you aren't wrong. But there is more diversity and challenge in five minutes of many modern games than all of pit fall.

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.

Bloom filters have several applications in bioinformatics: https://en.wikipedia.org/wiki/Bloom_filters_in_bioinformatic...

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.

I work on a database team at Google, tricky algorithms are definitely used. Now did I write any of those? No, they were already implemented in places where it makes sense before I joined the team.

I'm sure the dynamo team, the spanner team and etc are using all the techniques to make their database performant.

Makes sense or made sense? Non native here sry.

You can do either if those choices still make sense. Those choices made sense in the past, and they might still make sense currently.

Reply on news.ycombinator.com