21 ms·

Inverting Binary Trees Considered Harmful

• swang 11y ago
  Not sure what OP is being proud of exactly. I was subjected to this style when I interviewed at Twitter. Sorry my op sounded like I was accusing the author of something but this whiteboard approach is what I did at Twitter.
  • BinaryIdiot 11y ago
    Yeah I don't think OP was defending Twitter I think it was just more of a story about how crappy the interview process is at most tech companies. My experience with Twitter was really odd. I knew someone internal and had them directly submit my resume with a recommendation. The resume was tailored for exactly the position they wanted showing me besting all of their requirements. I got an email 4 months later telling me my resume was not good enough for even a phone screening. I've never had that happen before and it's still perplexing.
    • Xorlev 11y ago
      It's possible the position was filled, so some hiring manager just cleared the queue.
      • BinaryIdiot 11y ago
        Good point; never really thought about that. I just found it odd because their email response actually gave me a reason stating my resume didn't have enough experience for the position when it far exceeded everything they wanted for the position.
        • Xorlev 11y ago
          At least in our resume-tracking software, there's a bunch of pre-canned messages you can use if you choose to, I imagine it's much the same there.
    • sriram_sun 11y ago
      Did you consider the possibility that you might not be the only person tailoring their resume?
• wyager 11y ago
  >You are then ushered into a room with the programmer's worst nightmare - a blank whiteboard. Am I the only one who enjoys programming interviews? Even if you screw it up, it's still fun to try your hand at whatever problem they give you. They also don't expect you to do it perfectly; you're allowed to have sub-superhuman performance.
  • viraptor 11y ago
    I believe that was the point - are you expected to do perfectly or not. There are different interviewers - some even just want to show off, probably like the strong hashing one. It's great if you can have a reasonable discussion that actually shows your knowledge.
  • MichaelGG 11y ago
    I interviewed at Microsoft and it was about 10 hours of this stuff and I loved it. Had a great time, and I think I did pretty well. One guy wanted me to write a shuffling program. So I came up with one which I later discovered was Fisher-Yates and optimal. But he kept saying "how can it be faster" so I'm not sure what I was missing. Most of the other stuff was pretty fun and straightforward - pointer stuff, string copying, synchronization. It felt like if you had gone through Sedgewick's algorithm book you'd be set for the most part. Unfortunately by 7pm or so I was sorta exhausted (didn't sleep the night before 'cause I was so excited). I met the hiring manager, and he asked something fun like make a ring buffer and also write a non-recursive inorder traversal function of a binary tree. I apparently had some off-by-one bug in the ring buffer code, and then I just blanked out on the traversal question. No hire :\. (OTOH, that team wasn't sure if they were going to be using VB6, or C++, or maybe .NET, but probably not because they wanted to ship with Office and Office severely limits dependencies. So maybe it was for the better.)
    • nulltype 11y ago
      Sounds like a blast.
  • adamkochanowicz 11y ago
    It's not fun when you've sacrificed one of your finite vacation days to do it, and under the pressure of needing to find a new job.
• davexunit 11y ago
  That was a really entertaining read. I'm not involved in the interviewing process often, but I'd like to be better prepared for the future so that I can ask meaningful questions and not waste anyone's time. I certainly won't be asking anyone to invert a binary tree.
• ww520 11y ago
  That was very funny. The failed Ruby interview with the soon to be defunct HN company was hilarious. It's a good advice to go out to interviews from time to time. Just to see what's out there.
• DanFeldman 11y ago
  I'm only a rising junior in CS on my second internship and I completely agree. I did really well in my Data Structs & Algorithms class (A+...) and I just hate these types of problems. I bombed Google and Dropbox's interviews, and am ready to never go through another process like that again if I can. I've been exceedingly lucky landing gigs at great companies that don't filter with these questions. I worked for LeadGenius (YC S11!) and the technical portion of the interview was super fun and effective; I was asked to write a useful piece of software in python which I later applied to school projects! No whiteboarding, no data structures. I'm currently interning at General Motors and their interview was similarly sans whiteboarding, and I'm surrounded by brilliant interns and coworkers. Hmm. At least for me and a few of my peers, being asked to solve the type of problems presented in the article raises some red flags about a company's culture.
  • deleted 11y ago
    [deleted]
  • graycoder 11y ago
    Congrats! Keep working hard and polishing your skills. It's good to hear that there's a little disruption happening in the interview world.
  • Gibbon1 11y ago
    It's not just CS, but probably more common with CS. There are two kinds of engineers. 1. Those that love love love solving Puzzles. 2. Those that question whether solving this or that puzzle is going to bring in any money for the company. For a places like google or deranged YC startups, whether what you are assigned has any bearing on cash flow is something way above the typical engineers paygrade. There are a lot of companies where that isn't true.
    • Gibbon1 11y ago
      BTW: Bit of advice for anyone going into a technical fields. Learn to write, English. Learn it well. How to clearly explain idea's and requirements. How things work, how they are broken. Justify what you did, or cover your butt. Where you are in twenty years will depend mostly on this. Learn to speak fluently in front of a group of people. Or whatever the locally appropriate language is.
• smaili 11y ago
  While I'm completely, 100%, against these kinds of questions, how else can a company that receives thousands of resumes a day filter out the good from bad?
  • derekp7 11y ago
    How about sitting the candidate down in front of an actual computer, or ask the candidate to bring in their own laptop? Then if you want to see how they do, pick out some open source projects that need a feature or two added, or a bug fixed, and have the candidate walk through some solution? This way, you are getting to see what their style is, and the random open source projects gets a potential improvement. And you won't get accused of having the candidate programming for you without pay, because contributing to random open source projects is kind of like charity or community volunteer work. Or, here's a fun project. Have the candidate write up (in the language of their choice, or preferably multiple languages) a program that generates solutions for the Cracker Barrel peg board game (or variations thereof).
    • matchu 11y ago
      I like this idea for small firms, but how does this scale to the level that the parent comment is asking about? If we want to interview a few hundred candidates this month, who finds the few hundred open-source project tasks and audits them for appropriateness? And, for what it's worth, the peg game problem sounds to me like standard interview fare: an interesting puzzle that bears little resemblance to real-world software challenges. Why is it a better alternative?
    • gnuvince 11y ago
      So instead of giving them an algorithm problem that they might have seen in the past (or seen something similar) you give them a random open source project -- along with all the idiosycracies it certainly contains -- that they are 100% unfamiliar with and ask them within a few minutes to make sense of the entire codebase and produce a meaningful contribution? Sorry, but that sounds even more cruel and unusual than asking a very obscure algorithm question.
• marvy 11y ago
  What does it mean to invert a binary tree?
  • VieElm 11y ago
    To change the nodes to point the other way around. So if the left edge of N1 points to N2 and the right edge points to N3 you make it so that N1's left edge points to N3 and the right edge points to N2. It's a trivial problem of changing pointers around. It's like 4 or 5 lines of code if you write a recursive function.
    • TheLoneWolfling 11y ago
      def invert(node): if node is None: return invert(node.left) invert(node.right) node.left, node.right = node.right, node.left Yep, pretty much. But, to be honest, if you hadn't described it I wouldn't have had a clue what was meant by inverting a tree. Zippering it or something? I wouldn't know.
      • VieElm 11y ago
        You can ask the interviewer to clarify what the question is or what the result should look like. You should always ask for more details ask if you don't understand the question, and sometimes people ask in a vague way to see if the candidate will ask for clarification for better or for worse. It will not make you look stupid. The simple action of saying "I don't know what you mean by X" or "I don't understand what X is" builds up your credibility, not reduce it. People who aren't afraid to ask questions demonstrate credibility because when they do say they know something you know they probably actually do. I have learned so much from not being afraid to say "What is X" when someone starts talking to me about something and assume I know what it is already. Nobody has ever laughed at me for this. Even if they did, it wouldn't bother me, because I'd rather I look silly and then learn what it is than to pretend I know and then actually end up not learning what it was someone was talking to me about. Finally if they did think you should have known what the topic was you'd rather they know that about you while they're evaluating you not after you're hired and end up in over your head. This is a really unlikely scenario. These interviews are not so much about what you know, but how you solve problems.
• saryant 11y ago
  I just interviewed at a company that asked me to invert a binary tree on a (virtual) whiteboard. In fact, they asked me twice! Once in the initial technical interview, again in the follow-up! Haven't heard back yet but I'm really disinclined to keep talking to them.
• rdtsc 11y ago
  Yeah I remember the Google interview a few years back. I did it mostly for fun, and because their recruiters kept contacting me. So there we were, building a tree out of a forest of existing smaller trees or such. That was after they couldn't find my resume, and used a 5 year old one they found some place. They seemed annoyed and tired. By that time I felt nothing short of me proving P!=NP would have help changed their mood. I mean, they didn't even ask me what I knew, what I worked on lately. Heck, I could have been herding goats for the previous 5 years, but if I could have solved that tree problem, well, Googleplex here I come, I could have been herding goats there, maybe as part of some a green eco-initiative project... I guess half way through I just kind of decided that Google must be a pretty bad place to work at and kind of gave up. I was tempted to ask them how often they had to build the tree out of subtrees at Google. Or in this case how many times did they really have to invert the binary tree, but I am nicer that than, maybe they really did have a pretty shitty day. Ever since then I've declined to interview at Google. I get contacted every year like clockwork "Wanna try again?", "No thanks, good luck inverting binary trees though..."
  • desdiv 11y ago
    >...I could have been herding goats there, maybe as part of some a green eco-initiative project... Truth is stranger than fiction: http://googleblog.blogspot.sg/2009/05/mowing-with-goats.html http://googleblog.blogspot.sg/2009/05/mowing-with-goats.html
  • deleted 11y ago
    [deleted]
  • melling 11y ago
    I was told by someone many years ago to always take a copy of my resume with me to an interview. That advice has paid off a couple of times. These days I also keep an email draft ready to send.
    • x0x0 11y ago
      While that's good advice, I don't follow it. If a company doesn't have their shit together enough to coordinate an interview schedule and get the right people into the right room at the right time with my resume in their hands, ideally in their hands ahead of time, I don't want to work there. It's a basic competence test.
• wetmore 11y ago
  Context for the title: https://twitter.com/mxcl/status/608682016205344768 https://twitter.com/mxcl/status/608682016205344768
• detrino 11y ago
  This just comes off as a bunch of bragging with the issue in the title sitting in the periphery. Also, people would be well served to realize that companies use these tests as a proxy for intelligence and education. They very much try to avoid making it a trivia contest.
• deleted 11y ago
  [deleted]
• wyldfire 11y ago
  I enjoy the challenge of programming interviews. When I interviewed in Mountain View, I thought it was just super cool to have been invited. It was like the mother ship had summoned me home! I was mega-underwhelmed when I botched the last session, though. And after doing so poorly, no one escorted me out or summed things up. Efficient, I suppose -- I'd met with the recruiter at the beginning of the day and there was nothing left to discuss. But there was no denouement. A big build up all day and all of a sudden -- nothing. That last session I was asked to implement a particular matrix manipulation. IMO a bit more utility than tree inversion. And I tried to talk through my thought process but I'll admit it just wasn't getting there. After it was over, I went back to the hotel, wrote a test case and kept coding until I made it work. I'm a little ashamed to admit that it took 1.5-2hrs to get it to work -- so probably not just intimidation/stage fright. After writing the code, I don't think I understood the design well enough to explain it -- but I did do it on my own w/o any reference. I guess I wasn't surprised when I didn't get an offer. So I've been contacted again as a part of this latest hiring campaign. I'll give it another try, I suppose. My ego's buoyed by being contacted again and doing well on phone screens, so I suppose I can take another bruising. :)
  • waterlesscloud 11y ago
    I don't mean to personalize this to you, but your story kinda illustrates one of the problems. There's so much ego and self-worth tied up in both sides of this style of "interview". Both sides have this overwhelming need to show how smart they are. It's understandable in some ways. It's part of what attracts people to the field, showing off intelligence. I'm guilty of it myself. But it makes the "interview" process have an adversarial nature most of the time. That's not helpful to the actual goal of hiring people who will make your team successful. One thing that might work along these lines- Bring in a hard problem that the interviewer doesn't know how to solve and spend some time trying to solve it with the candidate. As a team, discussing different options and problems with those options. You know, like people do in actual work situations...
    • morganvachon 11y ago
      > One thing that might work along these lines- Bring in a hard problem that the interviewer doesn't know how to solve and spend some time trying to solve it with the candidate. As a team, discussing different options and problems with those options. You know, like people do in actual work situations... ^This guy gets it. I've never understood why interviews are set up to put the interviewee on edge and make him or her feel out of place, while simultaneously putting the interviewer in a temporary position of ultimate power. Said position does one of two things based on their personality: Makes the interviewer feel superior and aggressive, or makes them uncomfortable and ready to get it over with. Neither situation is good for the people involved nor the process itself. You're basically testing an employee on non-work-related problems under artificial pressure, which is pointless. And I say all of that as both an interviewee and interviewer in the past.
• waterlesscloud 11y ago
  There's not so much a shortage of talented programmers as there is a shortage of people able to identify talented programmers. If there's anything in need of serious disruption, it's the adversarial hiring process in technology. It's all mindless cargo-culting, and it doesn't actually work.
  • jheriko 11y ago
    > It's all mindless cargo-culting, and it doesn't actually work amen.
• powera 11y ago
  Data counter-point: When I interviewed at Google, I used "echo foo" in my Java code through two white-board coding interviews, and I still got the job. Sure, there are some terrible interviewers in the Valley (and I've been interviewed by some) but there are also some terrible interviewees (candidates?) out there.
• BobTheCoder 11y ago
  A lot of these posts don't actually address the problem of hiring and filtering people. If you think whiteboard tests or logic puzzles are not effective, why do you think this and what is a better alternative? I personally think they are ok, but should more be a means to test if the candidate can reason intelligently and it shouldn't matter much if the end answer they get is correct or not.
  • mrcsparker 11y ago
    I always try to find out if the candidate could - with enough information - solve the puzzle. Can you, given time, figure out a good solution to the problem I am asking? How would you go about solving the problem? What is your methodology? I agree with you. These sorts of problems are really to understand how someone reacts to a new idea that he or she does not understand. A lot of times people tell me that they don't know they answer to a problem, which is fine. Knowing that there are things that we don't know if a sign of maturity, and the curiosity to figure out how to solve a problem is what we should be looking for.
  • sanxiyn 11y ago
    Work sample tests, of course. Basically everybody who read the literature knows what is the better alternative.
    • reagency 11y ago
      Coding a simple algorithm is a work-d sample test.
  • BinaryIdiot 11y ago
    Personally I think there are two good ways, in combination, to determining if a person is a good hire. 1. Ask questions about past projects. Probing questions to make sure their resume sounds accurate. Get a sense for how they solved problems in the past and explain them. 2. Give them something to code. On a computer. Some small example. Even better if you can try a pair programming exercise to see how they code and how they can communicate with others on a team. Asking academic questions has been entirely useless in my opinion. I've worked with multiple people who can pass all the academic questions about algorithms and data set and couldn't write an application to save their live...and the vice versa too. I'd rather see how they can code, now and how they can communicate about projects (active and in the past).
• jheriko 11y ago
  i saw the thing on twitter earlier. what i don't get is why not ask the question of what that means? its such a simple problem once you know... and irl you don't know everything, if your interviewer expects it then you reject them for being a bad place to work.
• scotth 11y ago
  Fact is, it just isn't true. As a Googler, I am surrounded by enormously talented engineers, the likes of which I rarely encountered on the outside. They love what they do, and it shows. I have no doubt that there are false negatives/positives, but I am convinced that Google is doing something right.
  • modarts 11y ago
    A slightly...biased perspective?
    • scotth 11y ago
      How so?
      • grumblestumble 11y ago
        "How so?" pretty much describes the situation to a t.
  • ashwinaj 11y ago
    Have you encountered anyone outside? Sure there are talented engineers there but so are engineers in startups and other companies. I'm afraid that's a very myopic statement.
    • scotth 11y ago
      Yeah, definitely. I worked for eight years in the Toronto startup scene. Several coworkers were unquestionably awesome, but they were few and far between. The bar here is much higher.
  • jsolson 11y ago
    I think we do very well at hiring the sort of people who already work at Google. The false positive rate seems to be very low, and the people I work with mostly seem very happy (I know I certainly am). The false negative rate worries me, though, and I keep wondering if there's a way I could structure my interviews (and feedback) differently to help change that problem.
• linux_devil 11y ago
  I faced similar experience but here in India , since good interview questions are rare , most of the times questions are repeated from forums such as Career cup , I was asked questions irrespective of my role . I do take interviews at my current organization and ask simple practical problems with very simple solutions but most of the times candidates think in terms of complex data structures instead of simply trying to solve a problem, they do premature optimization and what not .
• rayiner 11y ago
  I don't think inverting binary trees is the problem per se. I mean, algorithms are the bread and butter of programming. You should be able to implement simple ones like that even if you'd never actually do that in practice. The real problem in my opinion is the whiteboard and time pressure.
  • gnuvince 11y ago
    I gave this example on Reddit this morning, but I'll repeat it. If a programmer was given an array of elements [a1, a2, a3, a4, ..., an-1, an] and asked to produce the array [a2, a1, a4, a3, ..., an, an-1] and couldn't do it, he'd be the laughing stock of /r/programming for a couple of days and we'd hear about this problem for years to come, the same way we hear about FizzBuzz. Certainly a programmer should know how to traverse an array and manipulate its elements! For the case of inverting a binary tree, we haven't gotten a clear answer to what it means, but the concensus seems to be to swap every left and right nodes in the tree. Well, that's exactly like the array problem above: traverse the structure and manipulate its elements! The traversal is not a simple loop, you use recursion (or if you're fancier, use an explicit stack to avoid causing an overflow of the call stack), but I'd argue that recursion is a fundamental notion for a programmer to know. A commenter on Reddit mentioned that there's a difference between programmers and computer scientists and that the programmer is responsible for writing software and the computer scientists are responsible for coming up with algorithms and data structures. But then, what do the programmers use? If we cannot expect them to know about trees, what about linked lists? Resizable arrays? Hash tables? Graphs? These data structures are extremely important tools for creating solutions, shouldn't programmers be aware of them and how to use them?
    • ubernostrum 11y ago
      A couple of things: 1. I think phrasing matters a lot. Saying "invert a binary tree" creates an immediate suspicion in my mind that what I'm really being asked is not "do you know how to swap elements", but rather some kind of weeding-out trivia looking for a specific, probably named-after-a-person, algorithm they're expecting me to remember from a college course (tricky for me in particular, as I didn't do CS in college). 2. A whole lot depends on the context of the interview. While I know what a binary tree is and how it works, I've never -- in 11 years of programming professionally, and several more as a recreational/amateur before that -- actually needed to implement or even explicitly use one. There are a lot of things people will deride lack of knowledge of, things that people will consider to be hugely important CS fundamentals, that can literally just never come up in a lot of programmers' careers because they are not actually universally fundamental in all fields of programming. So jumping into things that aren't relevant to the field you're interviewing for can achieve the opposite of what the interviewer hopes for: it's putting the candidate off-balance, but in the wrong way by making them wonder if they're interviewing for the wrong job or misunderstood what the job actually involved. Which in turn is going to affect their performance.
• orangecat 11y ago
  I'll be the contrarian and claim that inverting a binary tree is a perfectly reasonable interview question. (Although not anymore now that it's famous). It combines basic background knowledge (what is a binary tree and how is it structured?), ability to reason logically (binary tree algorithms are often recursive, "inverting" a tree with no children is a no-op, otherwise you want to swap the children, and the children's children, and...), and enough familiarity in one language to write simple constructs without an IDE or stackoverflow holding your hand. None of this requires you to be Jeff Dean. I will agree that the guy who kicked all this off has a legitimate complaint if the recruiter failed to adequately explain the interview process, and I'm sure there are lots of bad interviewers that focus on meaningless details or obscure trivia. But I don't agree that the concept of having candidates write code is fundamentally awful.
  • TylerE 11y ago
    I don't get the obsession with binary trees questions on interviews. I've had several in a couple different interviews. You know how many times I've coded a binary tree algorithmn, in 15 years as a professional programmer? Zeeeeero. They just aren't that common in actual code. Why not ask questions about, say, working with a general tree data structure, like XML or an HTML DOM? That's something that comes up all the time in many fields. Why the obsession with low-level pointer juggling?
    • zzygan 11y ago
      http://www.joelonsoftware.com/articles/GuerrillaInterviewing3.html http://www.joelonsoftware.com/articles/GuerrillaInterviewing... There were earlier versions of that article as well. Joel kinda popularized the notion of those kind of problems
  • bliti 11y ago
    In your daily programming activities, how many times do you have to implement a binary tree? I'm genuinely interested.
    • kd0amg 11y ago
• Osiris 11y ago
  The last interview I did was for a node.js position. I was told to bring my laptop. When I got there, the put me in an office and handed me a packet with instructions on checking out a nearly empty git repo. Then they said "Write an API that meets as many of the following requirements as possible and push the code. We'll be back in 3 hours." After 3 hours, I was taken to a conference room where I demonstrated the API. I also talked about a bug I had that had hung me up, but I fixed it right there in the conference room. Got the offer. It was a great experience. I enjoyed the challenge, but it felt useful and related to the work rather than just esoteric problem that would not likely ever be required by the job, and if it was I'd have time to research it and figure it out.
  • BinaryIdiot 11y ago
    That actually sounds like a decent way to do things. The only thing I'd change is making it shorter and trying to incorporate some pair programming at least to some minor degree to see how well they communicate along with developing.
    • vidarh 11y ago
      Pair programming is incredibly divisive. In a company that does pair programming, sure, do that, because those of us that hate pair programming would then instantly tell them we're not interested and leave rather than waste time on an interview somewhere we won't want to work. But likewise, if you're not actually doing pair programming day to day, don't do it in an interview setting.
      • BinaryIdiot 11y ago
        Erm, okay, I used the wrong terminology. I simply meant two people working on the same project. I didn't mean on the same workstation, that would be terrible.
  • mcv 11y ago
    This, especially if the conference room is filled with a reasonable representation of their programmers, rather than just one or two people, and they get to ask questions and we get to talk about the code. Hearing someone talk about their own code and explain their approach and the up and down sides of it, is a lot more valuable than simply having the correct answer roll out.
• TylerE 11y ago
  I recently interviewed for (and got) a new job. The interview process took about two weeks and on the whole was pretty reasonable for both sides. There was a short phone screen (~30 minutes) Then I had two technical exercises to do. For each, I was given a reasonable time period (4 hours) that started when I visited a special link to the get the problem description, and then used whatever tools I wanted to get it done, then email in the completed exercise. The two exercises were not completely trivial, but were relatively straightforward and actually involved skills relevant to the position and not arcane puzzles or comp-sci theory. (Basically, the first was to write a Postgres schema from scratch (total 5 or 6 tables and maybe 30 columns across all the tables). The second task was to write a CSV parser (including reasonable error checking/recovery) to load data into the schema from the first problem. Finally, there was the main interview (conducted via Facetime, this is a remote position). That ran for close to 3 hours. This worked well, since it gave me a feel for what the work would actually be like, and I was given, as the candidate, every oppurtunity to put my best foot forward - no whiteboard exercises, no surprises.
  • zbyte64 11y ago
    The correct way to write a CSV parser is to import one.
    • chrisseaton 11y ago
      Someone has to write that CSV parser though, don't they? And sometimes you actually need to write things like sort algorithms. I implemented an insertion sort from scratch recently, because it needed to be done in a particular way to take advantage of the capabilities of a specific JIT compiler. People do actually do this stuff - it's not all academic.
      • jbdigriz 11y ago
        Did you have to do this on a whiteboard or paper as part of the interview process for your job? The point: not being able to do this on a interview in completely contrived circumstances with all the anxiety that comes with close scrutiny of a person who had the power to determine your future career is not a good gauge of your ability to do so when matters, given all the resources we as developers generally afford ourselves. My biggest problem is that the vast majority of these tests is they only test two skills, neither of which is all that critical to software development beyond a certain minimum threshold: recollection and pattern matching known solutions to familiar problems. In my current level of competency with a decade of tenure in software development is this: if you're asking me to solve problems which I can easily "solve" with a few minutes of searching the web, you probably don't want or need someone like me whose spent the majority of their career on big projects which require a multitude of disciplines from being creative to quantifying results to forethought of future use to systematically testing and releasing at a minimum of risk.... What I find ironic is that I've never been tested on some of the few rote tasks which I find most developers struggle with: committing/branching/merging/commenting code, producing post release documentation, developing robust API functions, etc etc
• unoti 11y ago
  Funny, I thought this was going to be "inverting binary trees considered harmful" because the sensible way to do it is to change your traversal algorithm to be right-before-left, and leave the data alone. Silly me!
• IgorPartola 11y ago
  I love interviewing and being interviewed. Don't know why but I do. However, I hate these types of interviews. I mean, sure if I am a new grad or you suspect I might not know my shit, ask me some probing questions. However, almost nobody these days needs to invert a binary tree or compute the hash of a string by hand. Here is my secret go to question when interviewing someone: "can you describe how an AJAX request works, from start to finish?". The answer involves knowing that AJAX works over HTTP, same as regular page requests, knowing what IP, TCP, and HTTP are, and how client and server interact using them. It is a question most competent people can answer, yet it has lots of room for depth of detail. By discussing technical subjects, challenges and solutions I think you get a much better idea of how good someone is vs some predefined set of puzzles.
• sriram_sun 11y ago
  The rules are pretty clear on what the interview will cover. The recruiter tells you months before the interview and they (Google) even send you a list of what books and papers to read before you consider yourself ready. That is more than fair. I just joined a start up. It consists of 3 non-minorities and 3 minorities. All three non-minorities were recruited early on because they all knew someone within the company (and they all were competent). All three minorities came in through a recruiter - expensive and the bar definitely was a little higher than the internal referral-hire process. So In summary, I like Google's process for its fairness. They also seem to hire quite a few good engineers and a few great ones too.
  • discardorama 11y ago
    > The recruiter tells you months before the interview and they (Google) even send you a list of what books and papers to read before you consider yourself ready. Right, because I have nothing better do in those months than to rehash CS 101 and waste my time inverting trees and reversing strings.
    • sriram_sun 11y ago
      Nobody is telling you to spend all your free time on CS101 for months. It shouldn't take months. Go back, pick up an OS textbook and read a few pages without all that academic pressure. I bet you'll appreciate the writing a little more.
      • kamaal 11y ago
        You totally missed the point, may be this makes sense for a few people. But a whole majority of people don't find it a very good use of their time to gain knowledge just for its own sake. If I were writing a OS, I would bury myself in all the OS books in the world, and work atrocious hours to build one. But if you are asking me to do it, because I have to face an hour of interview 6 months from now, I find this a pointless exercise.
  • kkapelon 11y ago
    I had an interview (and got rejected) at Google in 2012. Nobody sent me a list of papers and books to read. I applied for a software engineer position. I was rejected when I couldn't answer system administration questions (the guy asking the questions was a system administrator at Google)
• cnp 11y ago
  Probably my favorite hiring writeup of all time. So good!
  • kluck 11y ago
    I think you are underestimating the sheer magnitude of writing that is that piece of literature.
    • cnp 11y ago
      The subject matter might elude me in its technical details, but oh how he got his point across ;)
• deleted 11y ago
  [deleted]
• CamperBob2 11y ago
  This passage gives me a good idea: The OPower guy said they had a ton of problems where they will be using Scalding, so I asked him what they are doing in its absence. He said Oh we pojo it. Then he said pojo this and pojo that, and soon I was drowning in pojos, so I asked, Sorry, what exactly is a pojo ? Now, bear in mind I am a Scala programmer and haven't touched Java in ages, and they knew that. Their whole pitch was they wanted to inject some new Scala blood into their tired Java veins, and that's why I interviewed there. So the guy is agape, and says, you don't know what a pojo is? When was the last time you wrote Java? When interviewing a candidate, use some wacky made-up term like "pojo" a lot in offhand conversation, and reject anyone who doesn't ask what it is.
  • x0x0 11y ago
    pojo is a common term for java devs, at least any who have been molested by spring
    • notduncansmith 11y ago
      It's also seen some use in the Javascript community as well (though not nearly as common).
      • gkop 11y ago
        And Ruby too (PORO naturally). Leave it to Martin Foweler et al. coin a useful [category of] term[s].
    • strathmeyer 11y ago
      Never heard of spring, never heard of pojo. Specialized in C/C++, STL, Boost, OpenGL and GLUT, GLx... over the decade have only found interviews for Java jobs. Have tried to learn Java, used them a jobs where none of my bosses knew it or cowokers could spend time talking to me about it. Still, I can only get interviews of Java jobs because that is the only work experience on my resume. Why are we all so screwed?
    • ExpiredLink 11y ago
• sown 11y ago
  This burns a little as I got turned down for a job I think I would have done really well at. I'm wondering what I did wrong exactly. I accepted defeat as graciously as I could but I don't know what my future holds. I love programming but I'm wondering if programming doesn't love me.
  • mingmecca 11y ago
    I wouldn't fret about it too much. There are a lot of interviewer egos out there and kids being put in the position of Ultimate Power(tm) can really do a lot of damage to the self-worth of qualified candidates. Just keep coding, studying algorithms, etc, and putting yourself out there. Eventually you'll get a job that you want and is well suited for you. You're fortunate to live in a time where it's a seller's market, employment-wise.
• rcthompson 11y ago
  I guess encouraging their employees to interview is Twitter's strategy for retaining them by reminding them how much they don't want to be looking for a new job.
• istvan__ 11y ago
  Twitter interview went sideways, I got one shot with a question (that I won't share) that required finding Hamiltonian path in a tree, over the phone of course. I am not sure what is the mindset of the interviewer. I am hiring engineers (systems, software and security) in the last 5 years, got trained up on recruiting by Amazon, so I would say I have a pretty good understanding on hiring. The right approach with these interviews to find out the best of the candidate. In order to achieve that you always start with simple questions like what is a variable, what sort of data is out there, do you use version control etc. After that you switch gears. On the subject of inverting binary trees on a whiteboard. Is this the core of your business? How many times did you need to do that last week? If it is irrelevant for your daily operations than why are you asking this question? The problem is that (especially companies like Google) like to hire Stanford graduates and those guys think after being in the job for few months that the best way on interviewing is to measure how well the candidate would have done during the last semester in theoretical CS class at the university. While we probably all know that running a service for millions of users in production in a distributed environment requires many other skills that are not represented too much in the interviews, yet this is what you can run into during the interview loops. I think at certain extent this is known to the Google recruiting team and they are ok with it. The way to beat the interview is to read books like Cracking the Coding Interview and train up extremely well on those trees and search algos and all, if you are really committed to work there. There are several very senior guys turned down by Google simple because they failed one or two of these ridiculous questions. I think the last incident kind of a good example of this: https://twitter.com/mxcl/status/608682016205344768 https://twitter.com/mxcl/status/608682016205344768 Now I get back to my read about how the heck I am inverting a binary tree.
  • reagency 11y ago
    Loops in a tree?
    • istvan__ 11y ago
      Thanks for pointing out, my bad, fixed now. I meant Hamiltonian path. Guys might have leaked on Glassdoor among other questions.
• trynumber9 11y ago
  This type of interview questions worries me. My nervousness then permeates throughout the whole interview so I've never been asked these type of questions, which is unfortunate as perhaps it's not as bad as I make it. Someone recommended Skiena's "The Algorithm Design Manual" and I picked it up. If you feel like more exposure to data structures can be useful, it has a section titled "A Catalog of Algorithmic Problems" which I find useful to read before an interview.
  • trentmb 11y ago
    Coursera has a couple courses coming up: Algorithms: Design and Analysis, Part 1: https://www.coursera.org/course/algo https://www.coursera.org/course/algo Algorithms, Part I: https://www.coursera.org/course/algs4partI https://www.coursera.org/course/algs4partI
• nsxwolf 11y ago
  Anyone know what a dag is? Seems like a term from finance, but it is literally unGoogleable.
  • mceachen 11y ago
    directed acyclic graph
  • deleted 11y ago
    [deleted]
  • drakenot 11y ago
    Directed Acyclic Graph maybe?
  • deleted 11y ago
    [deleted]
  • msds 11y ago
    Erm, it's the second result when I google 'dag'.
    • ExpiredLink 11y ago
      Your Google but not his.
  • necrodawg 11y ago
    Graph theory related questions are the perfect candidates for shitty interview questions. Graph theory for the most part is fairly simple and it has quite a lot of specific terminology. It's straightforward if you have ever had to use it to any extent. For those who don't they won't have much of a clue.
• benihana 11y ago
  >The first programmer with/without a shadow walks in. He's quite annoyed, because he was neck deep in jira or git or debugging some hairy stack-trace on eclipse, and he's been unceremoniously yanked off to interview YOU - the new dude, who has no fucking idea how things really work here. Well, he must show YOU your place. You lowly worm... Oh man, I hope I n ever come off that way when I'm the interviewer. I always try to give myself a good fifteen to twenty minutes to cool down before the interview and get prepared mentally. But I generally kind of look angry when I'm thinking and listening. Would it be helpful to explain to candidates that I have rbf?
  • dagw 11y ago
    I always try to give myself a good fifteen to twenty minutes to cool down before the interview and get prepared mentally. You're lucky you get a heads up. On more than one occasion I've had a manager come up to me and say "We're in the middle of interviewing a candidate right now in conference room X. Please come and ask a few questions and see what you think of him".
• kbd 11y ago
  I interviewed at Google twice in Mountain View after getting through the whole phone interview and coding process each time, but failed in person. I was way too nervous and performed poorly, but did well enough that they wanted me to come back a third time. I said no thanks. Ironically, I wound up working at Google anyway after my startup (where I was a core developer for years) was acquired. Another case of real-world skills not being borne out in Google's interview process.
• nickysielicki 11y ago
  The problem that I see with the interview process is the same problem that I see in computer science cirruculum: focusing too much on things programmers should know, rather than how to know things.
• lohengramm 11y ago
  Really fun article. I cannot make a point about the state of affairs of recruiting in SV because I've never been there, but those examples of interview processes are quite daunting.
• _joe 11y ago
  Interviewing is hard. Both for the candidate and the interviewer, if he/she knows the value of hiring - as assessing the overall qualities of a candidate in a one-hour chat is mostly impossible. Also, you're interviewing someone whose future life depends on the outcome of that exam, to some extent. That makes a fraction of the people you interview very nervous and thus perform badly. Then, you have the introverts, and people that don't have great communication skills, who usually get the interviewer in a bad mood because the conversation gets uneasy. It's really a minefield not to create a huge amount of false negatives. So, I agree that uber-specific CS questions would just test your memory, or more precisely your luck. That's the same as "cultural fit", only in terms of technology. My strategy, when interviewing is: - If the candidate has some FLOSS project he mentions in his resume (we actively encourage them to do so), I take a look at his/her code. That is usually one of the best indicators of their abilities. If the project is interesting, I usually start the interview from it. - Ask general questions which a candidate for this position should reasonably know. Try to get the candidate to talk to you, and then try to get the conversation to a more detailed level, to test how deep the knowledge of the field has gone - Ask the candidate to talk to you about something they have passion about in the tech field, a project they loved to work on. Again, use things the candidate is describing to get to dig a little deeper - Look at the CV, find any language that the candidate affirms to know well and to use daily, and ask some specifics about it. - Finally, make a small thought experiment of building an application. These are normally questions that should not weed out anyone because they don't remember that particular detailed thing I love so much, and still weeds out very quickly whoever is superficial, or is pretending to know things he/se doesn't know. You'd be amazed how many "rockstar web developers" fill their mouths with "RESTful webservices" and then have no idea of which the HTTP caching headers are. Or what's the HTTP status code for Not Modified. Or by how many python "hackers" can't tell the difference between a list and a set in their favourite language. So, I definitely try to make the candidate be in a comfortable place during the interview. I know of at least one guy that told our internal recruiter that I use the interviews to show off... and that was because I explained a senior Java programmer that yes, Java's GC system is a bit different than Perl's. So be advised, sometimes people are just bitter with the interviewer because they performed badly and can't admit that to themselves.
• neumino 11y ago
  > You are then ushered into a room with the programmer's worst nightmare - a blank whiteboard. It may be the case for a few, but some people (including me) feel pretty comfortable with a white board. There's nothing hard in using a whiteboard. It's just a big sheet of paper... Then if people think that they will never have to use a whiteboard to explain the design of their system to someone, maybe it's because they just "design" simple system.
• kmonsen 11y ago
  Sure it is bullshit. But it is also highly trainable. If you want a job, spend a month at http://hackerrank.com/ http://hackerrank.com/ and similar sites and just get better at it. I think most engineers will pass after that. Oh, and always use a language you are very comfortable in. Just stay safe and boring. I think all companies will let you pick the language as long as they have heard about it.
• SquidLord 11y ago
  Is there a reason the standard response isn't "I write code for money. Are you giving me money yet?" "Don't give it away for free" is the rallying cry of photographers and graphic designers. Why is it not for programmers?
• suyash 11y ago
  He should name those HN companies, really entertaining read after yesterday's blow up. We need to start a hashtag and trend invertingBinaryTrees
• fdej 11y ago
  > So it exponentiates 31 by one less than the length of the string and multiples that with the first character's ascii, then exponentiates 31 by two less than the length of the string and multiples that with the second character's ascii, and so on and so forth, and sums the whole mess. And I'm supposed to know this. It's not such a "mess" if you see that it just evaluates the string as a polynomial.
  • radicality 11y ago
    And then the author writes: > Now, in his defense, computing the dot product of the string with a random prime vector is a well known Universal Multiplicative Hash Function, but forgive me, father, for I did not pay much attention to this invaluable nugget in my Algorithms 101. Well, I didn't pay much attention in such a class either, but isn't that just intuitively obvious? Dot-product a vector `x` with a vector `p` of (unique) primes, and well, you've got yourself a number unique to `x`.
    • dagw 11y ago
      The question was explain the exact approach Java uses to hash strings, not come up with a way to hash string or explain why does this particular approach work for hashing strings. Much like hashes themselves going one direction is much harder than the other.
      • CHY872 11y ago
        Meanwhile, my actual Google interviewer asked me how I might do it. He then explained why my Gödel numbering scheme was bad, showed me how Java does it, was seemingly satisfied enough and offered me a job on his team. Google has a bad rep, but it is possible to sort it out.
        • dagw 11y ago
          That sounds eminently reasonable.
• deleted 11y ago
  [deleted]
• dasdasd 11y ago
  [speaking for myself only, not my employers past or present] [I am guessing this will be an unpopular opinion, so posting anonymously] I feel that interviews are essential. Every alternative I've heard seems to not work. I've tried. 0. Review their contributions to open source --a. Some brilliant people have none - they prefer to get paid for their work & not disseminate it openly for free - that does not mean they should be disqualified --b. I've personally seen people with stellar resumes claiming to have contributed to many projects who could not even tell me when they'd use a hashtable in any scenario of their choice 1. Ask about their last project --a. It is easy to lie, to any level of detail. Anyone who tells you otherwise has never watched a politician speak. --b. Speaking about engineering (even well) does not mean you can actually engineer well. 2. Pair program with them --a. This tends to waste a lot of time, since either you use an abstract problem (and you're back to a normal interview) or you use a real problem and you spend 10000 hours explaining it. 3. Hire them on a trial period --a. This is insulting to the brilliant people --b. This is a waste of company time on the not brilliant people
  • inglor 11y ago
    Trial period: It's not just "insulting" - I wouldn't do it. If I have a job I'm very satisfied with and you dragged me to your place in order to interview after contacting me. I won't be willing to spend a week in a trial. This is a sellers market anyway. What we found works is asking practical questions and not theoretical ones. You can ask people to code with a computer and internet and whatever editor they want simulating a real environment.
  • geebee 11y ago
    Thanks for going ahead and expressing what you think may be an unpopular point of view. Your points are fair, and are a bit part of why I feel so ambivalent about technical interviews. While I don't really like how they're handled, I think they may be necessary, and they may be an unfortunate byproduct of a good thing. For instance, I majored in math, not CS. I took some basic computer science, but much of my programming was done in math classes, sometimes informally, sometimes as part of the course itself, and sometimes as part of those optional 1-2 unit pass/fail labs. When I first opened a data structures and algorithms book, I was slightly amused by what I'd already covered and what I hadn't. For instance, I'd written DFS and BFS code for my graph theory class in college, and I'd done a lot of the linear programming at the end of the algorithms book. Various numerical programming exercises had touched on a lotos other things, recursion, lists, and so forth. But there were gaps, and I've studied a lot on my own for them. Now, in most fields that wouldn't be possible. You can't study something that overlaps quite a bit with law, nursing, or medicine, and then fill in the gaps on your own, demonstrate knowledge to an employer's satisfaction, and go off to work as a lawyer, nurse or physician. I think this is a pretty wonderful thing about software development, and things like the google "entrance exams" are actually part of why it is possible. I didn't get an offer from google, and reading these threads, I'm realizing that I should have taken months, not weeks, to review. However, I didn't encounter any of the arrogance or hostility, I found that the interviewers did a good job keeping things friendly and collaborative. That said, it's stressful. People in other fields are often kind of astounded to hear what we go through. You have nowhere to hide, you are at the whiteboard, with a pen, getting grilled technically, and you only have 45 minutes to solve the problem. You fear looking like an idiot, even if the interviewer tries to be positive. You may feel like an idiot, even if the interviewer had no intention of making you feel this way and made an effort to make sure you didn't. And of course, there are plenty of interviewers who may actually kind of enjoy making someone squirm a bit. So while I may have a somewhat more positive view of the tech "exam" than a lot of people here, I still think something is broken here. I've discussed this a few times with people here on HN, and I honestly do think that three big interviews may be roughly equivalent to taking the bar exam. Seriously. I could have studied for several months (though like I said, I have bigger gaps to plug than a CS major probably would). I read a blog post about a guy who passed the California bar with 100 hours of study. People talk about the "grueling" three days of exams. Well, interview at google, amazon, and microsoft. Between phone interviews, in person interviews, and so forth, sure it can get to that level. Even if it falls short of "bar exam" level effort, the fact that we're starting to talk about it reasonably in the same breath shows just how much effort goes into it. And here's the problem - it's just an interview. You get no feedback, no credential, nothing. You might do well enough to "pass" under a reasonable set of scoring criteria, but all you get is a "no hire" with very minimal information about how you did. I've heard people say (again here on HN) that they'd happily take a bar exam for software if it meant that they could be done, for once and for all, with the never-ending series of technical exams that we have to do over and over. I'd be ok with studying three months, six, hell, even a year. Because the exam would be consistent, rigorous, and would provide me with a lasting credential. I'm just not willing to put this sort of effort into a single interview that may be decided very capriciously. So, all in all, I see merit in these difficult technical exams (first step, let's stop calling them interviews). I think the whole thing could be handled vastly better, though.
• throwitaway_sam 11y ago
  It's stuff like this that makes me glad I'll never be an employee again. I work for myself, and it may not be as "prestigious" as Google, Facebook, etc, but at least I own my time, and I don't have to deal with self-important jackasses (except myself!) telling me I have to be to work by 11am to make 150k (a pittance, really) in Silicon Valley.
• georgerobinson 11y ago
  I'm more than happy to participate in a technical interview and I always prepare the best I can. However, I find it odd that technical interviews don't work both ways. The interviewer can ask you to solve problem x, but if you ask the interviewer to solve problem y (fair play, right?) I suspect you would be shown the door. Interviewer: "Can you show me on the whiteboard how you would invert a binary tree?" You: "Of course." Writes on whiteboard. Interviewer: "Excellent!" You: "Your turn. Can you show me on the whiteboard how you would implement a priority queue first with O(1) insert and O(n) remove complexity, and then with O(n log n) insert and remove complexity." I think even better would be to solve a problem on the whiteboard WITH the interviewer: one which the interviewer did not know or prepare an answer to. - First, it would reflect the type of problems you may have to solve in the role you're interviewing for. - Second, it demonstrates your interpersonal skills, your ability to de-construct, understand and then solve the problem at hand. - Third, it demonstrates how you work with others to solve a technical problem. - Finally, it puts both the interviewer and interviewee on the same level. It's not so much of "you v.s. me", but a "we". Hopefully, by the end the interviewer thinks: "Hey, I'd really like to work with this person. They're really smart, solved the problem faster than I could, they were very easy to work with, etc." I think this would make technical interviews more fair, more fun, and at last, representative of real work you would do in the role as I doubt the interviewer will want to solve the 8 queens problem under pressure either.
  • rkuykendall-com 11y ago
    > I think even better would be to solve a problem on the whiteboard WITH the interviewer: one which the interviewer did not know or prepare an answer to. wow, that's a great idea. I would love that interview. In addition, they should solve a problem with an engineer that would be their junior and their senior, to show how they contribute to those situations.
• faragon 11y ago
  Interviews requiring genius-level capabilities for doing boring daily trivial stuff. Quite deceptive. There is a rush in SAT and automated tests (e.g. hackerrank) stuff that is getting crazy. Anyway, no matter how good you do in SAT/programming tests, you may be discarded because of your personality, political views, or even because of plain xenophobia. Brave new world! :-D
• parados 11y ago
  I know Google interviews generate a lot of traffic on HN but I thought that I'd add something that I haven't seen covered, that is, the job itself. I interviewed twice successfully for Google and the interview experience was impeccable (interviewers were great, HR was completely on the ball etc.). The first time there was a hiring freeze so that didn't go anywhere, the second led to offers in several countries in Googles empire. Most of these I could not accept for family reasons but one I could although Google were quite secretive about what the job was. I accepted thinking that, well they know me well enough by now and what I can do. A mistake. Upon arrival it turned out to be writing an Android app which is completely the wrong end of the spectrum for me - I have never even written Java. I was been benchmarked against people who seem only to have done only that. The other thing that made me realise that I had no long term future in Google is that it was made clear to me that any experience of working for other software companies or other industries was neither interesting or useful. If you have a lot on your C.V. like I have this is problematic. So I left after a few months. Sure Google is a fabulous company, does some amazing stuff and has some great people (perhaps not as uniformly great as they'd like you to believe). If you fit the mould tightly enough you will have a lovely time. TL;DR - They should not have hired someone like me, I should not have accepted.
• vladaionescu 11y ago
  IMHO, I feel like people who are not up to it don't agree with coding interviews. Also, in my experience, the employers that didn't check coding skills at the interview had the worst engineers I met (surprise!). Now I can see why it's easy to disagree with interviews that check your algorithms 101 knowledge: that stuff is really really rarely used in real-life and you can just google it if you ever need it. But! Keep these in mind: - Can you come up with a better process that scales with the number of interviewers in your company, but also maintains reasonable consistency and keeps reasonable costs? Maybe you think you can, but keep in mind that the tech giants have data-crunched their interview stats over and over and this process is what they stuck with. (Of course, with scale there's also the problem you occasionally have arrogant interviewers - but I think that problem should be decoupled from the coding/non-coding interviews problem). - In places where they look for A* engineers, the point of the interview is often not to test what you know best, but how you get along with problems you have never seen before. An algorithm or data structure question often fits the bill. - Geeks love geeky puzzles (like inverting binary trees). Companies often look for geeks in love with abstract stuff. Also, IMHO, knowing only one language is a red flag for me too at 10+ years experience level.
  • JoeAltmaier 11y ago
    I think its just inbreeding. Folks who know that stuff, hire folks who know that stuff. Like any other industry we are self-selected for similar types. Never mind the discrimination issues; we're a very narrow-minded population. Better engineers could be found with other sieves.
  • kamaal 11y ago
    >>- Can you come up with a better process that scales with the number of interviewers in your company, but also maintains reasonable consistency and keeps reasonable costs? The last time I was looking for a job, a company gave me a small project and asked me to come back once I had finished it(or don't bother coming back). Around a week's worth time was given. The next rounds were spent around code review and discussing other ways in which the project could be completed. They basically tested my ability to get work done, and how good I was in it. >>Maybe you think you can, but keep in mind that the tech giants have data-crunched their interview stats over and over and this process is what they stuck with. May be you think they have it all figured out, but they routinely have to spend billions to acquire companies in order to grow. If really hired good people, they could have achieved it all in house. >>- In places where they look for A* engineers, the point of the interview is often not to test what you know best A* engineers ace in making things happen, not in being scholars of trivia. >>but how you get along with problems you have never seen before. You use your knowledge to systematically work for hours and sometimes days. Algorithms are a science that developed over decades, if some one claims they can do that over a whiteboard in an hour, they should go claim their fields medal. >> An algorithm or data structure question often fits the bill. What possible analytical skills can you test by knowing how well the candidate has memorized the answer to a math problem. >>- Geeks love geeky puzzles (like inverting binary trees). Geeks love getting stuff done, doing new things and building stuff. Not spending months memorizing math theorems. >>Also, IMHO, knowing only one language is a red flag for me too at 10+ years experience level. Let me guess, are you talking about people like Linus Torvalds and Theo de Raadt?
• meshko 11y ago
  Before reading the discussion let me just say that this is a trivial problem with a 10 lines solution which I expect anyone be able to write correctly on the first attempt and I would not want to hire someone who can't do it.