In my experience, the stuff you do in this kind of interview has very little relation with the stuff you do in the actual job. (I wish it did! I love those algorithmic puzzles.)
In fact, I would argue that one could know how to write one and have no idea of the practical use of it.
There is a whole world of development that is OS specific, UI specific, shipping commercial applications. Shipping quickly is always a higher priority than performance, because adequate performance is usually trivial to implement with hash tables/arrays/linked lists.
Are you sure about that? What if your code has to work for billion plus people correctly 99.999% time who are on all different kind of connections?
I would also argue that make a very clever algorithm do correct stuff (and be maintained to do that in the future) is more difficult than do it using simpler method/algo.
I you need to write so performance critical code that the choice of tree structures matters then this interview question sure as hell isn't going to find out if you are cut out for it.
If in my day-to-day I need to use an AVL tree, I will get a library for it, I won't be reimplementing it from scratch every single time.
In your day-to-day you have wikipedia, stackoverflow, hn and so on: software development hasn't qualitatively changed in the past decades to require multi-day interviews when 15 years ago a single 30-45 min interview was more than enough.
It would actually be interesting to compare the length of, say, a google interview a year after company inception compared to now. I am sure that despite the fact that nowadays the impact of a bad hire would be minuscule compared to back then, the interview process is way, way, way longer and more difficult.
I think we're discussing fluency. If you are hiring someone to edit books written in English, do you want a person who has to look up the meaning of "present participle", or do you want someone who just _knows_ what it means? I am sure that most people can figure out what "present participle" means in a few minutes with a search engine but those aren't the people I want as the editor.
Completely agree. How will you know you need an AVL tree, versus, say, a Red-Black tree? What are the performance characteristics of each? Why pick one over the other? When I interview someone, I ask algorithm questions to find out how they reason about the algorithms, not so I can watch them implement one.
They are both balanced binary trees with the same big-O complexity. Constant factors are different, but if and when you care about that, they're both binary trees so it should be easy to switch one implementation for another. In practice you're unlikely to care because most of the time you won't be working on performance-critical code. All speculation about performance is hearsay unless you run some benchmarks.
Google search brings up this discussion: http://discuss.fogcreek.com/joelonsoftware/default.asp?cmd=s... There's plenty of interesting stuff there, but it rather reminds me of medieval theologians debating how many angels can dance on the head of a pin.
There's a much, much more important distinction: binary trees (of all kinds) versus sorted arrays. There are many cases where a std::vector will be a lot faster than a tree, due to cache coherency, and use much less memory too.
So, discussing AVL trees and red-black trees in an interview is a waste of time. All it tells you is whether somebody once studied them (and remembers their studies), or possibly just memorized them the night before. Knowing that somebody studied those algorithms (except you don't know, because they may just have crammed it) would be a positive signal but doesn't actually tell you whether their CS course covered useful up-to-date topics, like cache-friendly algorithms and data structures.
this is also what is annoying me, the thought of so much ink being devoted to O complexity and so on when with modern processors in the end often "less optimal" algorithms are a lot faster based on how they work and often you end up writing the same thing 3 different ways so you can test and see which one is actually fastest given your language/compiler/toolchain/processor
In a book-level discussion whether a comparison in your algorithms evals to true or false in a predictable or unpredictable pattern doesn't make a difference in its performance, however write that out in code and the branch predictor of your CPU will be a LOT happier (and faster) if you make it so that all the "false" and "true" comparisons happen in streaks as opposed to randomly...
When they passed on me after my Google interview, the HR person actually told me "You can try again in 18 months. There are quite a few people who study for it during those 18 months and get it the next time!"
Yeah, I don't want to study for 18 months to get a job at Google, sorry.
I have a friend who was interviewed at Google, rejected, then interviewed again a year later, rejected again, and then a year later a Google recruiter got in touch to see if they'd like another interview. They said it started to feel like a cruel joke.
I might eventually try going through the gauntlet again, but I wasn't quite willing to move to the west coast during that time (new relationship, new home, new puppy, work was going well, I didn't really need more big life changes at that point).
I'm starting to consider a job change but I'm still not sure I want to move to the west coast. I'd probably have to downshift my home quite a bit out there.
To clarify, it seems to me the interviews tend to focus on things like "what's a good data structure for the social network in a Facebook clone?" but that's only 1% of the actual job, 5% tops.
It's true that those technical design decisions are very important, but they're not decisions that every engineer needs to make on their own on a day-to-day basis. They come up fairly rarely in a typical project and usually multiple people will be involved.
I don't have any easy answers -- I don't know a good way to interview for the other 95%+ of useful skills, like communicating well within a team, testing, debugging, benchmarking, writing documentation, good source control practice, knowledge of standard tools, meta-knowledge of how to learn about standard tools, how to evaluate new tools, system administration, dealing with production panics, etc.
I think some of this was why some time ago there was a way of interviews with "off the wall" questions, but those seemed to be fairly vilified so I guess that's why they aren't as common now, but personally I would get more of an understanding in how somebody thinks by giving them an unexpected question than by asking them something they could've studied for.
My most recent interview was very well done and not like an "algorithm quiz" at all. I had to bring my laptop and give a short overview of a project I had recently worked on. I think this really plays to the candidate's strengths.
I wrote millions and millions of lines of code in my 30 years career, I was once a top shot mac developer, and I was once a top shot computer geometry expert, and an OpenGL expert and all of that, and I've forgotten most of it... If someone asked me a trick question, I'd look like a fool.
Simply because I don't need it. My strength over all these years is my capacity at learning stuff quickly, and that doesn't come up in a trick-question interview.
So for these data structures questions: In 30 years I once had to implement a binary tree for any sort of problem I had in my job. Now it's not the same for hashes, lists, queues and many others, but trees? Quite frankly it's a CS toy. You know it's on the shelf in case it's needed, but it very rarely get a dusting.
This is what confuses me. I tend to take the problems I get during an interview as representative of the work I would be doing, and then get turned off by the job immediately.
At least at the PhD level, you'd expect that the job would be using more of my unique expertise, I'm not a BST expert (though I can write one when I need to, it definitely isn't "warm" in my brain).