7 ms·

>I still don't get why such questions are even asked as most jobs I've ever had not even remotely touched those and I've touched quite a few industries, technol

>I still don't get why such questions are even asked as most jobs I've ever had not even remotely touched those and I've touched quite a few industries, technologies and types of companies. I've had to work on tree traversal stuff multiple times in my life, anything low level GUI related will work with trees a ton. I've also had to work with hash tables directly, and with memory caching layers. I really should learn to write a proper parser, as I've had to write parsers multiple times now and they are always an ugly hack job.

pseudalopex 2y ago
> I've had to work on tree traversal stuff multiple times in my life, anything low level GUI related will work with trees a ton. How many times did you have to write tree balancing code with no reference materials?
- Paul-Craft 2y ago
  Bingo. You forgot to add "with someone literally looking over your shoulder," though. I've written AVL trees, B-trees, red black trees, and a bunch of other things people have named here. But, right now, without looking at any references, I couldn't even tell you how to balance an AVL tree, much less sit down and write out code for it.
  - tharkun__ 2y ago
    That's why these interviews select for recent grads. Or leet code studiers. Yes we've all done this in university. We've learned the theory. We had to write an implementation of this or that algorithm in whatever language the university made us use. And we also know that great minds took a long time to come up with these in the first place. These "basic algorithms" are not something you think up in 5 minutes after first learning that computers exist or that some problem exists. Bin packing algorithms are another such thing. Sure ask me interview "questions" like "please prove whether P=NP". Eff off Mr. or Mrs. interviewer!
- devbent 2y ago
  The exact same number of times I've been asked that during an interview: 0! I do ask tree traversal questions when interviewing because I've had to traverse a lot of trees so I think being able to do an in order traversal of an already sorted binary tree (which is only a handful of lines of code) is fair game.
  - jjgreen 2y ago
    Just the once? [maths joke]
  - pseudalopex 2y ago
    In order traversal is simpler and more practical than the questions xandrius asked about.
josephg 2y ago
Yep. In a project I’m working on at the moment (collab text editing), I’ve implemented 2 different b-trees, a skip list, 2 custom file formats and a dozen or so algorithms which do various graph traversals. I get that this is uncommon, but if you scratch beneath the surface, most software (browsers, databases, compilers, OSes) are full of this stuff. Even while I was consulting stuff like this would come up. At one company we were using a custom graphql wrapper around a CMS, and it was missing some functions we needed. The wrapper was implemented like a compiler from the cms’s data format to a set of query functions. Fixing it to do what we needed it to do was really hard and broke my brain a bit. But I did it. And I wouldn’t have been able to without understanding compilers and algorithms. You can spend your whole career walking the beaten path adding features to apps and websites, and never traversing a tree at all. There’s lots of work like that out there. But if you ever want to go deeper, you’ve gotta understand data structures and algorithms. I know not everyone is suited to it, and that’s fine. But there’s definitely a reason big tech asks about this stuff.
- sanderjd 2y ago
  > But if you ever want to go deeper, you’ve gotta understand data structures and algorithms. I don't think this is quite right. I think it's more like: If you ever want to go deeper, you've gotta be able to recognize when the problem you're solving fits a pattern for which good data structures and/or algorithms exist, and you've gotta be able to find, understand, and apply good reference material. Solving this "knowing what you don't know" problem is the best and most important role of formal education, in my opinion. It's not as important to know a topic as it is to know that it exists, and some of the basic terminology necessary to get started researching it further.
  - josephg 2y ago
    Yeah I think that’s what I mean by “understand data structures and algorithms”. Or, I think your description is exactly what a useful working understanding looks like. You should know broadly what’s out there so if a problem comes up, you know where to look. (Would a hash table help? A priority queue? etc). And you should be skilled enough such that if you decide to use a red-black tree, you can find a good library or implement it yourself - with access to the whole internet as reference material. (And test it). Nobody expects you to memorise a text book. But if an API gives you a list of items and you want to count the occurrences of each item, you should be able to figure out how to do that. And ideally in less than O(n^2) time if necessary. It’s surprising how many otherwise productive coworkers I’ve had who struggle with stuff like that.

pseudalopex 2y ago

> I've had to work on tree traversal stuff multiple times in my life, anything low level GUI related will work with trees a ton. How many times did you have to write tree balancing code with no reference materials?

Paul-Craft 2y ago
Bingo. You forgot to add "with someone literally looking over your shoulder," though. I've written AVL trees, B-trees, red black trees, and a bunch of other things people have named here. But, right now, without looking at any references, I couldn't even tell you how to balance an AVL tree, much less sit down and write out code for it.
- tharkun__ 2y ago
  That's why these interviews select for recent grads. Or leet code studiers. Yes we've all done this in university. We've learned the theory. We had to write an implementation of this or that algorithm in whatever language the university made us use. And we also know that great minds took a long time to come up with these in the first place. These "basic algorithms" are not something you think up in 5 minutes after first learning that computers exist or that some problem exists. Bin packing algorithms are another such thing. Sure ask me interview "questions" like "please prove whether P=NP". Eff off Mr. or Mrs. interviewer!
devbent 2y ago
The exact same number of times I've been asked that during an interview: 0! I do ask tree traversal questions when interviewing because I've had to traverse a lot of trees so I think being able to do an in order traversal of an already sorted binary tree (which is only a handful of lines of code) is fair game.
- jjgreen 2y ago
  Just the once? [maths joke]
- pseudalopex 2y ago
  In order traversal is simpler and more practical than the questions xandrius asked about.

josephg 2y ago

Yep. In a project I’m working on at the moment (collab text editing), I’ve implemented 2 different b-trees, a skip list, 2 custom file formats and a dozen or so algorithms which do various graph traversals. I get that this is uncommon, but if you scratch beneath the surface, most software (browsers, databases, compilers, OSes) are full of this stuff. Even while I was consulting stuff like this would come up. At one company we were using a custom graphql wrapper around a CMS, and it was missing some functions we needed. The wrapper was implemented like a compiler from the cms’s data format to a set of query functions. Fixing it to do what we needed it to do was really hard and broke my brain a bit. But I did it. And I wouldn’t have been able to without understanding compilers and algorithms. You can spend your whole career walking the beaten path adding features to apps and websites, and never traversing a tree at all. There’s lots of work like that out there. But if you ever want to go deeper, you’ve gotta understand data structures and algorithms. I know not everyone is suited to it, and that’s fine. But there’s definitely a reason big tech asks about this stuff.

sanderjd 2y ago
> But if you ever want to go deeper, you’ve gotta understand data structures and algorithms. I don't think this is quite right. I think it's more like: If you ever want to go deeper, you've gotta be able to recognize when the problem you're solving fits a pattern for which good data structures and/or algorithms exist, and you've gotta be able to find, understand, and apply good reference material. Solving this "knowing what you don't know" problem is the best and most important role of formal education, in my opinion. It's not as important to know a topic as it is to know that it exists, and some of the basic terminology necessary to get started researching it further.
- josephg 2y ago
  Yeah I think that’s what I mean by “understand data structures and algorithms”. Or, I think your description is exactly what a useful working understanding looks like. You should know broadly what’s out there so if a problem comes up, you know where to look. (Would a hash table help? A priority queue? etc). And you should be skilled enough such that if you decide to use a red-black tree, you can find a good library or implement it yourself - with access to the whole internet as reference material. (And test it). Nobody expects you to memorise a text book. But if an API gives you a list of items and you want to count the occurrences of each item, you should be able to figure out how to do that. And ideally in less than O(n^2) time if necessary. It’s surprising how many otherwise productive coworkers I’ve had who struggle with stuff like that.