[iainmerrick]

I'd be interested in hearing from people who work at Google, and get to figure out a cool algorithm for solving an interesting puzzle-problem more an about once a year. I bet there aren't very many.

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

[stuckagain]

I don't know about the average but at Google I probably write a new call to std::set::find twice an hour, and it's important to know that std::set is a red-black tree, and how std::set::find is implemented and how much that costs and so forth. Fluency with data structures and algorithms is not some kind of brain candy. It's absolutely necessary to get the job done.

[valuearb]

I've been a developer for 30 years, helped start a half dozen companies. Since college I've never written a single tree traversing algorithm, and would need to Google red-black tree to know what it is.

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.

[eridius]

You don't generally need to write tree-traversal algorithms because other people have already done so and you can use their implementations. But you should still understand the tree traversal algorithm, so you know what the thing you're using is doing, what its complexity is, etc. And if you understand it, then you should be able to reimplement it yourself.

[yomly]

I'm not entirely sure adequate performance is good enough when you work at the scale of Google...

[fnovd]

The performance bottleneck is not always where you think it is.

[perfmode]

That's why Google measures.

[perfmode]

That's right. Adequate performance will keep 1000's of extra cores burning cycles 24 hours a day.

[maverick_iceman]

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

[krzyk]

Correct is orthogonal to performant.

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.

[metaphorm]

I understand the perfomance characteristics of red/black trees very well. I couldn't implement one in 30 minutes on a whiteboard.

[devy]

After preparing and studying the interview questions on data structure, algorithms etc. with the help of guide books like https://books.google.com/books/about/Cracking_the_Coding_Int... You definitely can!

[joshuamorton]

Neither could I, but that was also well beyond the scope of my Google interviews.

[kisstheblade]

Yes but jeesus here we are discussing an algorithm that I first heard about in literally my first CS course on algorithms in my first year at the university, some 20 years ago. And I had to manipulate red black threes on the blackboard. Haven't seen them since in my 20 years of work in the industry.

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.

[DesiLurker]

I've interviewed many candidates for one of the big 4 & sat on the decision loops too. 'Attribute substitution'[1] one thing that does stands out in these interviews. essentially interviewers substitute answering the larger question of judging the candidate's suitability for the job at hand with a simpler but easier to judge (& defend!) problem of solve this particular coding problem that I have 'normalized' over many candidates. Also, deep domain knowledge is often hard to judge.

1. https://en.wikipedia.org/wiki/Attribute_substitution

[alistproducer2]

one does not need to know how to write an algorithm on a white board to understand it. Seems like it would better to ask what a red-black tree is, what's it's time complexity, and what would be a good situation to use one.

In fact, I would argue that one could know how to write one and have no idea of the practical use of it.

[stcredzero]

It pretty much has no practical use, that a different data structure couldn't do more efficiently.

[poikniok]

What in the world are you talking about, RB trees are incredibly useful.

[stcredzero]

There's a well known analysis that shows they're asymptotically equivalent to B-trees. You can tune a B-tree to better exploit cache locality. Other kinds of ordered binary trees are far less complicated to code and have similar performance characteristics.

[koyote]

Maybe I am missing something but if you're using set::find so often, why not an unordered_set?

[tetraodonpuffer]

figuring out a cool algorithm is not the same as learning 1000 algorithms by rote to prepare for an interview. Just because doesn't feel like doing test prep for an interview, it doesn't mean they don't have the brain capacity to actually solve the business problem when it comes up.

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.

[thewhitetulip]

This is what has confused me for a long time, I interviewed at Flipkart an Indian ecommerce major (ex?) and their process was horrible. At the second round they asked us to implement a toc tac toe program, others didn't even have compilers, I had Python because it was a Linux machine, was rejected because "code contained bugs and didn't run", the third round was algorithms. I think these companies don't know how to hire that's why they are sticking to algorithms, in real life nobody is going to implement an algo from scratch, if I can learn Go in a week, learn how to write a webapp in 2-3 weeks when I have never written a webapp before why does it matter if I don't know how to implement some random algorithm?

[rpdillon]

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

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.

[iainmerrick]

OK, I'll bite: this is not something the vast majority of engineers ever need to know.

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.

[tetraodonpuffer]

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

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

[iainmerrick]

I'm not sure I understand your point -- possibly we're agreeing?

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.

[tetraodonpuffer]

my point was more along the lines that even if you need to figure out cool algorithms as part of your job, interviews as they are now don't seem to be not testing for that, but more for "can you rote learn these specific algorithms".

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.

[sumeno]

You don't have to memorize 1000 algorithms. Honestly you could have a really good understanding of when and how to use about 10 algorithms and probably do very well on most interviews.

[cableshaft]

The problem is each company will ask you a different set of algorithms, and you're not sure which they'll ask, so you effectively have to memorize a LOT more than 10 if you want to be prepared for whatever they throw at you (not literally 1000, but maybe 40 or 50, which will take considerable time to prepare for, in addition to all the other preparation or unrelated questions they could end up asking you (architecture, OS, process, design patterns, optimization, advanced language-specific quirks and gotchas, terminology, 3D math and graphics (if games), databases, networking, behavior questions, solving math problems you've never encountered before, questions about your past projects, etc, etc, etc).

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.

[iainmerrick]

The other downside of that is: in 18 months they're going to hassle you for an interview again, whether you want one or not.

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.

[cableshaft]

Oh yeah, recruiters from Google have contacted me three times since then. Actually the most recent recruiter said I could contact her whenever I felt like having another interview.

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.

[stcredzero]

You probably won't even get to use all 10 in your 1st two years of work. All the computer science you use in 99% of a typical programming career could be described in a single conference presentation. (Not that one would master all of it that fast, but it would describe what you need to know and know you don't know.)

[numbsafari]

You might not need to implement it, but you needed to know enough to know what an AVL tree is, why you might (or might not) need it, and to be able to do some basic validations on the library you selected to make sure that it does what you are hiring it to do.

[tetraodonpuffer]

agreed, but let's assume you don't know what an AVL tree is or what the trade-offs are between an AVL, red-black or other type of trees: how long does in this age to find that information if you know what you are doing? I mean, you could allow your interviewee access to a computer and based on the type of googling they do it should be fairly obvious if they know what they are talking about.

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.

[stuckagain]

> how long does in this age to find that information if you know what you are doing?

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.

[Xcelerate]

My problem is that I forget things very quickly. I've implemented optimized k-d trees and VP trees from scratch, but I forget the complexity of searching, rebalancing, etc. Even though I've implemented it before. I normally just Google something simple like that when I need to "re-remember". I suppose interview performance at those types of companies is kind of like high school and college — just cram all that stuff into memory beforehand and forget it right after the test.

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.

[buserror]

I so totally agree! Forgetting stuff is as important as learning new one, because it forces you to learn/re-learn quickly.

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.

[seanmcdirmid]

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

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

[iainmerrick]

I used to enjoy giving interviews because it was fun coming up with these little problems, and discussing them with smart people. Because I didn't otherwise get to do that very often at work! But I felt guilty about giving a false impression to interviewees about what the work actually involved...