| For quad-trees and oct-trees--they are fairly common in gaming and not a particularly time consuming to implement. For Red-Black and B-Trees, I've never heard of anyone being asked to implement the entire thing from scratch, but significant portions sure. Also explaining the implementation of significant portions. Here's a similar post from 2015 by tptacek >You're a 55-year old engineer who graduated from school in '81. You're being interviewed by a 24-year old engineer who graduated 2 years ago. You're asked, in an "algorithm interview", to explain some detail of the implementation of an AVL tree. >In reality, despite the fact that they're covered in CS courses, virtually nobody uses AVL trees in industry. In fact, people barely use balanced binary trees at all, and when they do, they use red-black trees, and they use someone else's implementation, because they're a bear to debug. >The 24-year old has an advantage with this question because they were recently taught about, and perhaps had to do exercises/homework/tests based on, AVL trees. >That this happens is stupid, because it's very unlikely that conversance with AVL trees is going to make much of a difference to your on-the-job performance. Almost all the narratives you can come up with about this involve reading tea leaves and are shot down easily by better selection/hiring/interviewing techniques that answer questions more directly. >This line of questioning can go too far; I don't, for instance, think knowing the big-O characteristics of an AVL tree is unreasonable (it's a balanced binary tree, and you should have the complexity of operations on those in resident set throughout your career). Here's another coment from tptacek in the same thread. If you don't know who he is--you definitely want to hire him if you can. Him failing out of your hiring process would be a travesty. >I was asked to do Bellman-Ford. I bombed that question, and was so shaken that I bombed the rest of the interview as well. >The irony was, I'd just spent the preceding 2 years writing multicast link-state routing code. I could have coded a decent C++ Bellman-Ford in a couple hours, but couldn't pull it out of my head on the spot in an interview without babbling. (I tried to dodge by describing link-state LSP forwarding and then Djikstra, but wasn't given credit for knowing the more sophisticated algorithm). >Algorithm interviews suck. We should stop doing them entirely. |