3 ms·

The last tip is the most important: practice. The industry loves tree questions, which is stupid -- the vast majority of us will never and definitely should ne

by x0x0 11y ago

The last tip is the most important: practice. The industry loves tree questions, which is stupid -- the vast majority of us will never and definitely should never implement a tree. Red black trees are notoriously fidgety to get right; just use the free, tested, implementations that someone has already beat on for you. But we love asking that shit in interviews. I actually got in an argument with a former engineering manager who loved tree questions; I demanded to see where in our 10m line codebase we implemented a tree. Nowhere. But if you wanted to work for him, you had to know how to implement trees on whiteboards. So practice so you're refreshed on trees and all the other trick questions we ask and not mentally refreshing yourself in the interview, and practice specifically coding on a whiteboard. That will help you remember to leave space to add more code and to write small and... the whole thing is fucking stupid, but sometimes life makes you jump through hoops. Also, and I think I read this on here, that stupid question about detecting loops in lists (hare and turtle) was an open research problem for quite a while, and wasn't published until 1969. Knuth, naturally. So either everyone in computing before then was stupid, or it's not obvious, and definitely not so obvious that thinking of it in 10 minutes at a whiteboard is reasonable. So really this is just asking if you studied, rather than if you're good at algorithms. edit: I thought I'd read on here that someone was awarded a phd for figuring out the list cycle detection, but maybe I'm wrong? I don't have my notes file handy. Either way, it's not an obvious algorithm until you've seen it, and then it looks trivial.

curiousjorge 11y ago
> Nowhere. But if you wanted to work for him, you had to know how to implement trees on whiteboards. That's troubling, seeing the VPE is a child, not an adult.
teraflop 11y ago
At the risk of focusing on your specific example, rather than your larger point which is a good one: If you're talking about balanced trees, I sort of agree with you. That's the kind of algorithm where it makes sense to write it once, test it thoroughly, stick it in a library and never worry about it again. But there are plenty of other uses for tree-like things. Think filesystems, or the HTML DOM, or JSON documents, or (generalizing a bit) dependency graphs, and so on... I actually like tree problems. You can take something with practical significance (laying out a web page, or syncing two directories, or simplifying a boolean expression) and strip away the details of the situation to get to a core algorithm that depends only on the tree's structure. In my experience, the biggest factor in how well interviewees cope with kind of question is their ability to reason clearly about what their code is doing, instead of just pattern-matching from their previous experience.
- x0x0 11y ago
  Right, but for most tree problems, you don't need to write your own tree. People should know how to use trees, and when one would use them (a map with ordered traversals.) For graph problems you will often have to write your own graph for the peculiarities of your problem, but the area I work in doesn't really have many graph problems.
MichaelGG 11y ago
Linked list questions are great. They're a simple data structure so it's easy to talk about without complicated details. Detect a loop? That's a great question! Any decent dev should be able to start coming up with suboptimal ideas right away and would be an interesting discussion. So long it's not a pop quiz type thing.

by x0x0 11y ago

curiousjorge 11y ago

> Nowhere. But if you wanted to work for him, you had to know how to implement trees on whiteboards. That's troubling, seeing the VPE is a child, not an adult.

teraflop 11y ago

At the risk of focusing on your specific example, rather than your larger point which is a good one: If you're talking about balanced trees, I sort of agree with you. That's the kind of algorithm where it makes sense to write it once, test it thoroughly, stick it in a library and never worry about it again. But there are plenty of other uses for tree-like things. Think filesystems, or the HTML DOM, or JSON documents, or (generalizing a bit) dependency graphs, and so on... I actually like tree problems. You can take something with practical significance (laying out a web page, or syncing two directories, or simplifying a boolean expression) and strip away the details of the situation to get to a core algorithm that depends only on the tree's structure. In my experience, the biggest factor in how well interviewees cope with kind of question is their ability to reason clearly about what their code is doing, instead of just pattern-matching from their previous experience.

x0x0 11y ago
Right, but for most tree problems, you don't need to write your own tree. People should know how to use trees, and when one would use them (a map with ordered traversals.) For graph problems you will often have to write your own graph for the peculiarities of your problem, but the area I work in doesn't really have many graph problems.

MichaelGG 11y ago

Linked list questions are great. They're a simple data structure so it's easy to talk about without complicated details. Detect a loop? That's a great question! Any decent dev should be able to start coming up with suboptimal ideas right away and would be an interesting discussion. So long it's not a pop quiz type thing.