6 ms·

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

> 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.
mythhouse 4y ago
> 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 ?
- taeric 4y ago
  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.
- ahh 4y ago
  > 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.
  - lukeramsden 4y ago
    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.
    - Jensson 4y ago
      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.
taeric 4y ago
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.
didibus 4y ago
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.
armchairhacker 4y ago
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
- tptacek 4y ago
  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.
  - morelisp 4y ago
    Skip-lists are a common way to implement unflushed data in persistent LSM trees, for example.
    - tptacek 4y ago
      Shows to go you! I'm super weak on durable data structures. This field we're working in, it's pretty neat.
  - rad_gruchalski 4y ago
    Redis ordered set is built on top of a skip list: https://github.com/redis/redis/blob/unstable/src/t_zset.c https://github.com/redis/redis/blob/unstable/src/t_zset.c.
  - lazide 4y ago
    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.
analyst74 4y ago
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.
- javaunsafe2019 4y ago
  Makes sense or made sense? Non native here sry.
  - tylersmith 4y ago
    You can do either if those choices still make sense. Those choices made sense in the past, and they might still make sense currently.
wnolens 4y ago
> 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.
flobosg 4y ago
Bloom filters have several applications in bioinformatics: https://en.wikipedia.org/wiki/Bloom_filters_in_bioinformatics https://en.wikipedia.org/wiki/Bloom_filters_in_bioinformatic...

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.

mythhouse 4y ago

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

taeric 4y ago
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.
ahh 4y ago
> 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.
- lukeramsden 4y ago
  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.
  - Jensson 4y ago
    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.

taeric 4y ago

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.

didibus 4y ago

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.

armchairhacker 4y ago

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

tptacek 4y ago
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.
- morelisp 4y ago
  Skip-lists are a common way to implement unflushed data in persistent LSM trees, for example.
  - tptacek 4y ago
    Shows to go you! I'm super weak on durable data structures. This field we're working in, it's pretty neat.
- rad_gruchalski 4y ago
  Redis ordered set is built on top of a skip list: https://github.com/redis/redis/blob/unstable/src/t_zset.c https://github.com/redis/redis/blob/unstable/src/t_zset.c.
- lazide 4y ago
  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.

analyst74 4y ago

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.

javaunsafe2019 4y ago
Makes sense or made sense? Non native here sry.
- tylersmith 4y ago
  You can do either if those choices still make sense. Those choices made sense in the past, and they might still make sense currently.

wnolens 4y ago

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

flobosg 4y ago

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