> There is no point in giving me binary-tree-traversing questions; I don't know those answers and will never be interested in learning them.
Interview process: complete success.
Interview process: complete success.
This phrase precedes the one you mentioned. He's saying the process he has been through completely ignored his background and field.
OP says that his field is object-oriented design, which links to a page where he announces that "We've started work on a new programming language". The idea that a computer scientist/software engineer would embark on building a new programming language but also state that they don't know how to solve tree traversal problems and "will never be interested in learning them" seems strangely incongruous, given that building a language almost certainly involves working with ASTs.
Specifically, OP pushed a commit in late 2016 that contains code working with stacks, linked lists, and an AST class for the EO language.
https://github.com/yegor256/eo/commit/6df2281d8b0163b9f9e1b8...
I guess I just don't believe that interview questions about trees are ignoring the author's background and field.
Hiring a junior with such criteria might make sense; hiring a more seasoned person, probably not so much. Because the seasoned person will just not be as compelling as the more junior person, due to having spent the past few years working on other things.
There is one thing I want to point out though. Before starting my algorithms course I knew how to solve problems recursively. I had done project euler tasks and what not. I just never knew the words abstract syntax tree or binary search tree. I could guess what they were prior to the course but I didn't know what they were off the top of my head.
Do you think that it's possible that a self taught engineer would know how to solve these problems given time and enough questions to the interviewer? Maybe get frustrated with "How do you balance a search tree?" questions under pressure?
It's very easy for new interviewers to come up with problems that are easy for them (because they know the subject), but very difficult for the interviewee. Avoiding that is a priority for me, but I still strive to evaluate how the candidate approaches problems.
My strategy is to keep my questions as close to first-principles as possible, making the problem more about programming approach than algorithmic recollection. I had a Google interview once where they asked me to implement pivot tables, and I had to sheepishly ask: "What's a pivot table?" That set me back somewhat, and I try to avoid that in my own questions.
Most people can work with Vectors/DynamicArrays, linked lists etc. but they don't know how to implement one or even how it works in detail under the hood.
In response to not knowing the speed of sound as included in the Edison Test, Albert Einstein replied:
"[I do not] carry such information in my mind since it is readily available in books. ...The value of a college education is not the learning of many facts but the training of the mind to think."
This is even more true today with the vast trove of easily searchable called the Internet. A competent programmer should have high-level knowledge of different algorithm types, but should not strive to memorize their implementation (e.g. for interviews), since it is trivial to look that up.
And aside from that, let's face it, none of us here are Einsteins.
Same thing with algorithms like tree traversal. You should know the theory behind them, but unless you regularly implement them, there is zero reason to commit their implementation to memory to the extent that you can casually write them on the white board during an interview.
>>And aside from that, let's face it, none of us here are Einsteins.
Even more reason to not try to memorize something unless you use it constantly.
You mix two completely irrelevant things: education and experience.
You will be taught binary trees in CS, but not every programmer is studying that.
If you learn binary trees in CS, you will forget it after few years of experience, because skills that are not used are forgotten.
So yeah, Amazon/Googles of the world are looking mostly at recent CS graduates (most of the set of programmers that know many algos) and the very small set of programmers that deal with algos every day.
I know several people that did, taking several months off to prepare (and got in), and yes, you have to re-learn all the CS algorithms which will probably be irrelevant again after you pass the interview.
It would have been different if he was asked questions that only algorithms experts could answer, but really these are really basic questions.
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.)
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.
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.
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).
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.
I did a couple rounds of their interviews a while back just to see if they really were as bad as people said they were (yup!). And that was in response to a very persistent recruiter emailing me over and over and over again to apply, despite my knowing there was zero chance I'd be a fit for the job they asked me to apply to.
And more generally: I don't really care about binary trees. They're simply not relevant to the work I do. I suppose if someday the only way I can get a job is to buy a book with all the stock interview questions in it and memorize the answers, then that's what I'll do. But if somebody's hiring me, I want them to hire me for the things I know that aren't standard interview questions anyone can memorize.
The way I try to phrase this to people who don't get it is: my metaphorical working set in memory does not include basic algorithms (that's what libraries are for), and does not include brainteasers or riddles. It does include a lot of arcana about how web application stacks work, the network and gateway protocols they use, the points where security and reliability issues are most likely to happen and how to avoid those issues, the application and database architecture patterns most often needed, available libraries and frameworks which implement them, pros and cons of different approaches, etc., etc. I could, if so inclined, probably take the metaphor all the way and outline which things are in the equivalent of CPU cache vs. the equivalent of main memory.
So sure, I could page all that out to disk and forcibly cram a binary-tree answer into my brain's L1 or L2 cache, or load up one of the dynamic-programming questions Google loves (tip if you want to work for Google: memorize the Wikipedia article on longest common subsequence, even if it will never ever be relevant to anything you'll ever do, because they will have you do it in an interview). But that would be actively harming my own usefulness, and I'm not willing to do that for Google or for anyone else.
Which I guess raises the question: why do you apparently want me to harm my own usefulness just to try to get a status-symbol passing grade on a Google interview?
I'm not arguing that Google doesn't have a huge scale, but I'm pretty sure that Microsoft, Facebook, Amazon and most likely the NSA also have unique systems and challenges.
And all of them (well maybe not the NSA not sure on that one) do the entire "algorithms quiz".
They have this reputation because, it turns out, not every engineer at the company needs to be able to rebuild all of Google from first principles in order for it to keep running. And even at Google scale there's not enough interesting greenfield work to do to, or de novo problems to solve, to keep all those "famous engineers" busy all the time. The same is true at most companies -- you need a mix of talents and skillsets, and you need to match up people to roles based on that. The Google approach -- of putting people into drudge work and paying them enough to hope they won't quit -- is a grossly inefficient use of talent and knowledge. Which is another reason I wouldn't want to work there!
What distinction are you making between "expertise", "knowledge", and "outside experiences?" The outside experiences are the basis of the expertise and knowledge. If you understood, used, and contributed to other existing build systems, you are then in a good position to understand, use, and contribute to Google's in-house build system, because you have useful knowledge about the problem domain of building software. And so on.
This was my second phone screen at Google, for what it's worth.
Binary-tree traversing is a rote memory sort of thing. Somebody who can come in and play 20 questions about an algorithm and answer them perfectly shows me nothing other than they studied that algorithm and have a good memory. It does not show me any insight into how they solve problems which have not already been solved for them. It won't show me how they do under stress with a completely open ended question.
I don't work at google so I won't speak to their daily work, but very rarely should you be writing your own binary tree or traversal code. If you should find yourself on that task you hopefully won't be doing it from memory / without reference because unless that is the ONE thing you know like the back of your hand, even then you are likely going to make mistakes.
I also feel that anybody who has actually been productive on a large successful project does not have time to commit to learning things that can be looked up when needed. There has only been a few times that I have actually needed to implement any of these algorithms in the last 10 years. Of those they were very low level and implemented in a kernel driver where libraries are not so abundant. Can I remember all the fine details today? No. Did I make a system that runs on hundreds of thousands of linux systems across the world? Yes. If I were interviewed on the fine details of implementing some of these algorithms and data structures would I pass? Not likely. Does this make me a bad programmer? Depends who you ask. If you ask the guy interviewing me Yes. If you ask my boss and the many customers who use my product No.
Memorizing algorithms does not make you a good programmer. Knowing how to apply and when to apply them does. The hard part was done when the algorithm was created, not regurgitating an implementation.
Now you might say hey, they should at least know binary tree! Sure maybe they should have some knowledge of it, but there will always be some algorithm you don't know. I would feel completely different if Google said "Come ready to talk about these 5 algorithms and maybe implement one or two". That falls inline fairly well with the author of the article. At least then somebody can say, "Hey, I don't have time", or "Sorry, not interested". And both sides can have their expectations insync.
Now don't get me wrong. We are talking about Google and Amazon. So yeah, somebody there might need to know something about these algorithms. But I doubt they all do. The Few interviews I have been on at these organizations I was not even convinced that all the people interviewing me would be able to pass the round of 5 had they interviewed each other. I should note not all the people who interviewed me gave me that impression. I did meet some really nice people that I thought I would enjoy working with.
I also don't think that these companies don't take into account that some people just interview badly. There is a lot of stress involved. While I think people should be able to work unders stress, I think the type of stress these interviews cause is something entirely different. I live a fairly stress free and carefree life. But when I went to interview at Google my stress levels were so high that I felt sick and worn out for days after. What I am getting at is I am presented with hard problems and short deadlines daily at work. Not once did any of those challenges cause me any level of stress. On the other hand trying to figure out what the interviewer really was asking and cramming to memorize algorithms caused so much stress I did not sleep for days days before the interview. It's not that I was up studying, its that my mind was racing and I could not sleep if I wanted. I just lied there in bed staring at the ceiling. I think they call that anxiety.
> Interview process: complete success.
It was a failure because they wasted everybody's time. Had they been more upfront on what they were looking for then he could have declined without costing both the company money, and him time and stress.
Very good point. The amount of memorization involved in the process is excessive. It'd be helpful if each candidate was told what subset of all possible problems they should focus on.
But the real value is in being able to analyze an application's performance and deal with concepts like recursion.
I also feel that anybody who has actually been productive on a large successful project does not have time to commit to learning things that can be looked up when needed.
Some important concepts aren't the kind of thing that you "look up" then read a one paragraph blurb for 3 seconds. The pitfalls of concurrency and the pitfalls that ACID transactions are supposed to protect against are two more examples.
Implementing a delete on a binary search tree or traversing one has nothing to do with analyzing performance. If you want to ask questions that require recursion don't make them dependent on algorithms that require rote memorization. Or at least have a alternative recursion question if the candidate says - "Sorry, I don't remember all the rules for this algorithm". Or even be ready as a interviewer to go over how said algorithm works and see if the candidate picks up quickly. If you wanted to really talk about performance then you can talk about WHEN to use a given algorithm and WHY. You don't want to ask questions that there literally is ONE (maybe two) answer that are correct. You don't want to ask questions that when asked WHY the answer "is because that is how the algorithm dictates it." You want to ask questions that are open for interpretation that you then can ask the candidate why they chose that solution. This gives you much more information.
> Some important concepts aren't the kind of thing that you "look up" then read a one paragraph blurb for 3 seconds. The pitfalls of concurrency and the pitfalls that ACID transactions are supposed to protect against are two more examples.
Let's not conflate algorithm implementation from rote memory with not wanting to answer any technical questions. You can't just come in and start talking about ACID transactions and concurrency as if that is what people have been objecting to. Those are valid topics and I doubt most people would have any qualms talking about them. As those are concepts, not rote memorization. You have to have a good understanding of the problems to know where the pitfalls are and know how to spot them. Implementing a algorithm rally covers higher level concepts other than simply regurgitating something like "traverse the left subtree of the root node, accessing the node itself, then recursively traverse the right subtree of the node ....".
I think what most people are suggesting is that there is too high of a penalty on not being exposed to a given algorithm. It is not that these people incapable understanding the algorithm or even implementing one. They simply don't remember. I think this is because a large number of people working at google are fresh out of school. They literally have no experience other than the rote memory required to pass their classes (yes, I simplified that a bit).
I will say that I did find a correlation to the age of the interviewer and the type of question asked. The older 30+ and 50+ guys that interviewed me asked practical questions not related to a specific algorithm. The youngest interviewer I had was a complete hothead and started out the interview saying "he was not your normal interviewer so he was going to ask the hard questions" Then proceeded to ask me a rote memory question about a algorithm. Either I had knew it and memorize it or not. That is not a hard question. The hard question have nothing to do with a defined algorithm. They are often open ended and leave lots of rope for you to hang yourself.
Yes, surely! Have the algorithm explained, or even diagrammed for them with pseudocode.
Let's not conflate algorithm implementation from rote memory with not wanting to answer any technical questions. You can't just come in and start talking about ACID transactions and concurrency as if that is what people have been objecting to.
Let's not conflate the need for a good background with rote memory. I object to rote memory being rewarded by interview questions. I also object to programmers who maintain they don't need to know any of this stuff at all, because they can just Google it and spend a few seconds reading the Wikipedia article. Where in the Dickens did you get the idea I'm Captain Rote-man?
One purpose of training in a highly skilled field is to teach people how to avoid the egregious gotchas. Go ahead and read my other comments in this thread and on this site. I'm not the all conquering champion of rote memorization you seem to think I am.
If I read them in a different mindset then i can take them as a complement to what I said. That knowing how to analyze application performance and concepts like recursion are more important than rote memory. And that interviews should focus on things that can't be ""look up" then read a one paragraph blurb for 3 seconds". I can fully agree to that.
Once again, I am sorry I misread your reply and dumped a wall of text on you.