28 ms·

Early in my career, I interviewed at Google. One of the interviewer asked me to recite the algorithm for constructing a Convex Hull. Since I hadn't done anythin

Early in my career, I interviewed at Google. One of the interviewer asked me to recite the algorithm for constructing a Convex Hull. Since I hadn't done anything related to convex hulls since my algorithms class as a sophomore in college (several years earlier), I couldn't remember all the details. At some point, I said, I know where in CLRS (https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press/dp/0262033844 https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press...) this is. The interviewer didn't like this, so he said "Pretend you're an engineer at Google. You need to have a convex hull. What do you do?" And I said probably the most correct thing I've said in any interview: "I would go look it up." He really didn't like this answer, but we struggled together for an hour, with him frustrated that I couldn't remember the details of an algorithm I last had seen 6 years earlier and couldn't recite in 60 minutes what took our professor 180 minutes of lectures to cover, and me frustrated that would have taken me 30 seconds to look up. I did not get the job at Google. I do make sure as a more senior engineer at my current company I use what leverage I have to make sure other interviewers don't ask pointless questions like this.

deleted 6y ago
[deleted]
dmoy 6y ago
Yea I interview (and have sat on HC) at Google, and interviewers who ask these types of questions really frustrate me. If your question requires having previously memorized or being able to come up with some tricky algorithm on the fly in 45 minutes and code a solution using it, your question is probably bad. I get why they ask them - they're easy to ask, they're easy to score, and when your question inevitably gets burned because someone posted it all over the internet in their blog post titled "How I got a job at Google!!" and then bumped way up the list on hackerrankcode-whatever I forget the websites... it's easier to come up with a new one, because you just pick a new esoteric algorithm and ask that. And honestly, coming up with interview questions can take awhile. When you have 5 or 6 very calibrated questions and all of them get burned and banned in a one quarter span, you now have to spend the better part of a whole workweek, plus dozens of more interviews coming up with new questions and recalibrating. But, I just refuse to ask those types of questions anymore. They really don't give useful signal. The only three bits of signal you get are "does the candidate already know this algorithm (or are they a supergenius who just figured it out under time pressure)? can they communicate it to another engineer? can they write code?" Importantly if the answer to the first question is no, then you get zero signal on the other two parts. That basically means as an interviewer you just failed your job.
- Swizec 6y ago
  My favorite question to ask in software engineering interviews is one that I believe to be un-burnable. > It's 2140 AD, New York is under water up to X feet high. Buildings have been retrofitted with <magical-ish material> to withstand the water. You are in charge of keeping your building dry. If water gets in and damages the foundation, a few thousand people die or become homeless. > Design a system that ensures that doesn't happen. How candidates approach this, how they think about redundancy, how they deal with additional constraints or extra scenarios thrown at them tells a lot about how they approach things. The question is not about software (explicitly) on purpose so that it gets people out of the coding mindset. With more software-focused systems you always get candidates who starts writing code and designing objects and classes and stuff. No, I want you to design a system. Stop writing code. The reason this question is unburnable is that there's no right answer. You're being asked to show how you work through an abstract problem and design a solution. You aren't being asked for an answer. So far everyone who did well on that question has turned out to be a great engineer. Whether they were fresh out of college (and learned a lot fast) or they were already experienced.
  - justicezyx 6y ago
    IMHO, this is not particular better than an algorithm question. Why not just summarizes the traits of the technical skills you expect from the candidate, lay it out, and come up appropriate questions for each interview? General software engineering interview does not work. But there can be more specific measures to improve the experience.
    - jlokier 6y ago
      > Why not just summarizes the traits of the technical skills you expect from the candidate, lay it out, and come up appropriate questions for each interview? That won't work; it's aimed at a different kind of skill. The skill the GP is looking for is ability to solve a problem you have never seen before, for a problem that bears little resemblance to anything you've done before, by transferring your existing general problem solving skills. It's a test of your ability to solve new things, which is a capability the company finds useful. This is a very useful skill, and you can learn to do it better, but it's not a "technical" skill as we usually mean it. However it is one of the things which might be associated with "great engineer". Listing technical skills and testing them will not tell you if the candidate has developed the above capability.
ladberg 6y ago
I had a very similar experience interviewing for Google. I was asked to do a task that eventually boiled down to a topological sort, and I thought the question consisted of recognizing that the answer was a topological sort and moving on because it was over the phone. However, that was not the case. The interviewer wanted me to code it all out over Google Docs, but I didn't remember the exact algorithm so I basically had to re-figure it out on the fly, which took most of the interview (I even similarly mention "in any real situation I would just look this up", but that didn't help). At the end, I had a bunch of pseudo-C++-code that should do it correctly. I thought I was done, then the interviewer said she would go go copy my code and compile it after the interview to see if I was right, which blew my mind. It was never mentioned previously that the code would actually be compiled and run, and with no syntax highlighting or ability to compile and test the code myself there is zero chance it was ever going to work. I never heard back, so I'm assuming my code failed and they left it at that. Anyway, I'm much happier now that I think I would have been at Google.
- sterlind 6y ago
  Yeah, Google's interviews are whack. I've been rejected twice -- I think because of flubbing an algorithm question -- and after that I designed a new algorithm for my work that's getting published in OSDI this year, I think. Their loss.
- tjr 6y ago
  A passage from one of Jon Bentley's Programming Pearls: As soon as we settled on the problem to be solved, I ran to my nearest copy of Knuth's _Seminumerical Algorithms_ (having copies of Knuth's three volumes both at home and at work has been well worth the investment). Because I had studied the book carefully a decade earlier, I vaguely recalled that it contained several algorithms for problems like this. After spending a few minutes considering several possible designs that we'll study shortly, I realized that Algorithm S in Knuth's Section 3.4.2 was the ideal solution to my problem. If Bentley needed to go look up an algorithm that he vaguely recalled studying in the past, just how awful of programmers are the rest of us that look things up, really?
  - 6y ago
derefr 6y ago
For a company whose main claim-to-fame is indexing the web (rather than mirroring it in their databases), Google sure doesn't seem to understand that CS learning is done by mentally indexing textbooks (rather than mirroring them in your brain.)
- linza 6y ago
  That may be true. But then why hire someone with just look-up skills before hiring someone who really tries, and enjoys the challenge? I'm interviewing engineers frequently and although I agree that the question asked by GP is maybe not the best it still gives the signal if someone is willing to power through a problem with minimal guidance and/or ambiguous constraints. Something I'm willing to find out at the peril of pissing off a few candidates.
  - derefr 6y ago
    I work with novel algorithms all day (I'm writing a decompiler.) The more I learn, the more I have confidence in the fact that I have absolutely no hope of inventing an algorithm that doesn't already exist; and that I shouldn't waste my time trying, when instead I could be spending that time digging through the nigh-infinite vault of potential solutions to my problem known as "the output of CS academia." Software engineers aren't mathematicians. We don't invent algorithms or data-structures. That's not our trade-skill. And even actual mathematicians don't sit down to solve a real-world problem that no maths they're aware of directly solve—and then produce novel maths, and then use them to solve the problem—the very same year, let alone the same hour. What I can do, as a software engineer, is to take algorithms that exist, and repurpose them or glue them together in novel ways that the designers of those algorithms never thought of, to do something new. Bitcoin, for one example, is a feat of pure software-engineering: it takes four or five existing well-known algorithms, and puts them together in a novel combination to solve a problem. I could maybe invent Bitcoin. But I can't invent Floyd-Warshall, if I don't know about it. Google doesn't employ computer scientists (i.e. mathematicians who invent algorithms.) Alphabet does, under DeepMind and Waymo; but Google itself only employs—and only needs—software engineers. Asking a software engineer, under pressure, to derive a novel algorithm, is a bit like asking a chemist, under pressure, to derive a novel class of chemical reaction; or a materials scientist, under pressure, to derive a novel material. That's not the type of pressure that a real-world person in these jobs will ever be under. And moreover, it's precisely the type of pressure that people with experience in these positions have learned to mentally associate with "going in the wrong direction, toward wasted effort", flinch away from, and to turn around and study the literature instead. It's ironic that Google expects its employees to all have university degrees. If there's one skill people who've gone to university are guaranteed to know (and to have built up a reliance on), it's consulting the literature.
NotSammyHagar 6y ago
That was a terrible interview experience. Of course anyone would look it up. I used to work at google and interviewed people as part of my job as a regular software engineer. I occasionally heard about these kinds of stories. Google didn't give much feedback to individual interviewers, no one told them if they were terrible or great questions or whatever. I also saw better interviews.
gedy 6y ago
I made the mistake of answering Google recruiter without a CS degree and "only" an EE/CompE and 10 years Software experience. Junior interviewer would not proceed past some algorithm question regarding boxes of pennies by weight, as he wanted a specific algorithm to be used in my solution, which I clearly didn't know. Recruiter then ghosted me, so F off Google for wasting my limited time like this.
jboggan 6y ago
Your story reminds me of when I interviewed at Google and did great on four interviews but the fifth one sunk me. I was asked an inheritance question which didn't make much sense (coming from a heavy Perl and Ruby background) but probably would have made more sense if I were a heavy C++ developer. I explained how the question wasn't really an issue in Ruby but the interviewer didn't like that and angrily said "you should have learned this in your compilers class at Georgia Tech!" I'm glad that the interviewer read my resume closely to learn my alma mater, but not closely enough to realize I had a biology degree from it. I tried again a year later and got luckier with my allocation of interviewers. I never did end up using any algorithms there.
rococode 6y ago
Another anecdote of an incompetent interviewer blindly looking for a certain answer: I once had an interview where, for a pretty long question, one trivial step was to check that one set was a subset of another set. Neither set had any special preconditions, just two plain unordered Java HashSets. Not thinking twice about it, I wrote a simple for loop that checked if every element in the smaller set was present in the bigger set. When I finished the question, the interviewer started questioning me about the runtime of the for loop. He started hinting that it could be more efficient, which confused me, since it seemed impossible to check every element of a set in faster than O(n) time. I also didn't see how it was useful to think so carefully about the runtime of such a trivial thing, seeing as the "story" of the problem indicated that the sets would never be particularly large and the task wasn't one that would be sensitive to a couple microseconds difference in runtime. We spent about 20 minutes stuck on this, with me awkwardly repeating I didn't see how it was possible to be faster and him telling me to just think harder and look at the problem "mathematically", "forget about the code, just think, in math, if you have a set A and a set B, how do you efficiently find if one is a subset of the other?". Eventually we ran out of time for the interview. As we wrapped up, he revealed to me the elusive answer: "Since you're checking if it's a subset, you should use the built-in isSubset() method that Java sets have". Of course, he hadn't conveyed to me at all that he was looking for a specific built-in method, so I thought there was some secret algorithm that I would have to write to make it go faster. I didn't mention that though, and instead replied that even if it were a built-in method I didn't see how it could be faster than O(n) in its implementation. He didn't have response, and just stammered something like "well it's built in and it's actually the most efficient way" and the interview ended awkwardly. Anyways, I had my doubts, so when I got home I checked. There is no isSubset() in Java sets. There is a containsAll(). It's implemented as a while loop that runs in O(n) time, making it no more efficient than writing your own loop. Naturally, the company ghosted me too.
- baddox 6y ago
  Three years ago I interviewed in house (after several hours of phone screens) at an SF tech company that has since gone public. The position was for a senior software engineer doing mostly backend Rails stuff. The biggest portion of the in-house interview was some fairly simple algorithm puzzle involving solving some word game given some rules and a list of valid English words. That section of the interview ended with me explaining how hash table lookups are constant time and the interviewer insisting that they are linear time. To be clear, there was no “gotcha” about collision resolution or anything subtle like that. My claim just came up as an obvious step in my explanation of the running time of my proposed solution and the interviewer jumped on it. I thought I was quite cordial, but I didn’t back down, and the interviewer seemed quite aggressive. The other interviewer in the room at the time seemed very uncomfortable with the fact that I would question something so basic, but didn’t intervene or express any “opinion” on the “debate.” I was rejected due to insufficient experience. :)
bjourne 6y ago
> I did not get the job at Google. Not to troll, but have you considered that you perhaps were not qualified for the job? There are people that can recite details of convex hull construction algorithms.
- tshaddox 6y ago
  But it didn’t sound like the job was for algorithm recital performances.
spankalee 6y ago
I work at Google and have performed plenty of interviews over the years. We're specifically trained not to do this. We have "feedback feedback" in our interview systems specifically for this type of situation.
- abtinf 6y ago
  And yet... I've read countless anecdotes about this kind of behavior, over multiple decades.
  - wutbrodo 6y ago
    Your surprise comes from the fact that you're modeling an institution as a single person when it in reality consists of a hundred thousand people. It's obviously less mental effort to reason about large entities this way, but it's obviously much less accurate.
    - phendrenad2 6y ago
      That's funny because institutions can only be modeled as a statistical average of all of the humans who contribute to a given property of the institution.
      - wutbrodo 6y ago
        Untrue (there's plenty of emergent behavior in large organizations), and ignoring that, irrelevant. An obvious trivial example is looking at the property of consistency in actions: an organization consisting of a hundred thousand people is going to be far less consistent in many sequences of actions than any given person would be.
- pjmlp 6y ago
  Given that I gave my feedback about 10 years ago and it keeps happening, something is not right.
devit 6y ago
Well, I probably used it last time 10 years ago and still remember it. All you need to remember is that you sort points by angle from a fixed point on the convex hull, and you can easily work out the rest of the algorithm as well as the proof of correctness. Not knowing it is a relevant signal that you did not seriously attempt to compete in computer science competitions during high school and college and did not otherwise have a burning desire to learn algorithms and data structures nor a specific interest in computational geometry. Whether it's in Google's interest to select for that of course is debatable.
- duskwuff 6y ago
  > Whether it's in Google's interest to select for that of course is debatable. I'd argue it does not. Computational geometry is a niche. It's not even a niche that's particularly relevant to most of Google's development operations. In modern software development, knowing the detail of specific algorithms off the top of your head and being able to implement them unaided is, at best, a parlor trick. I doubt very much that it even correlates to one's effectiveness as a developer. Even for development tasks which involve algorithmic work -- which many don't! -- knowing that various algorithms exist, and what they're used for, is much more valuable than having memorized the details of how those algorithms are implemented.
  - devit 6y ago
    The idea is that you might need to invent a new algorithm where a technique from an existing algorithm is used in a modified way or in a new setting, and then knowing the actual technique can be essential to find an inspiration. E.g. if you know that convex hulls can be computed by sorting by angle and sweeping, then you might come up with the idea of sorting by angle and sweeping in problems that are unrelated to convex hulls (e.g. determining what is visible from a given point in an environment with obstacles). In general, if you know a lot of those techniques and heuristics, you will be much more effective at problem solving in domains where these techniques apply. It is relatively rare for this to be a big factor in routine software development, so that's probably something one should filter for only if interviewing for roles where you might need to design novel algorithms (which Google probably has more than the average company).
sfteus 6y ago
I had several similar experiences through and after college. One in particular was while I was still in school, they had asked a question relative to performance when using views in an SQL database, and my answer wasn't satisfactory to them. Despite the interview going well up until that point, you could feel the tone shift immediately after, like they were just asking the rest of their questions as a formality and wanted me out of there as quick as possible. Didn't get called for a follow up, of course. Found out later that place was actually preying on foreign-based students (who received funding from the university to cover their out-of-state tuition difference if they worked up to 20 hours / week max for a company associated with campus) by making them work 60-80 hour weeks along side school and threatening to fire them if they told anyone, which would cause them to lose their funding and likely have to drop out / move back to their home country. I received offers from several others, some never called back. Ended up turning all those down though, as I had an interview with someone who helped step through the few mistakes I made as a learning process during the interview. One particular question I remember was basically building front-end components with Javascript, and my example had a loop with a write call in it. He mentioned he would compile the markup in the loop, then write it after it was finished, and asked why that would be better or worse. Had to think on it for a minute, but came up with a trade-off between more memory usage but less DOM writes, resulting in faster rendering. Worked that into the next coding example too, since it was similar but more complex. After the interview, when they called to schedule a follow up interview before I even made it home, I realized he was more concerned about whether I would ask for help, learn, and not make the same mistakes again. Worked there, learned a ton, became a senior dev just few years out of college, now I manage a suite of products for my current company. I don't think I would have gotten that kind of opportunity had I not had that first manager and job, so I strive to emulate that in my interviews. One of my favorite questions is something like "describe a crisis that occurred and the steps you took to resolve it," and give an example of one of my many stories of pushing bad code to production, having a server crash, etc, etc. I love the question because it involves no coding, no memorization, no regurgitating of info. Instead, it resolves around the person being a hero, which in my experience usually gets them relaxed, comfortable, and talking. You also learn a lot about their thought process: How did they first notice the issue? What was their process for triaging it? How did they debug it? If something involved in it was out of their wheelhouse did they go to someone else more experienced for help, or did they search for similar problems online to try and narrow it down? Did they delegate tasks if the workload was too high for them? Once it was fixed what was the procedure it went through for testing / verification? Did you monitor the issue afterwards to make sure it didn't come back? Once it was deployed, did you search for similar issues affecting your other systems? Did it ever come up again in new code and you were able to identify it before it was deployed? Obviously not all of these will apply to everyone, but the open-endedness of the question means you can probe a bit here and there throughout their story and gain a ton of relevant insight. And most importantly, it answers the question of "when things get tough, can you keep a cool head and think critically?" I can teach code, data structures, algorithms, whatever, to anyone. But the difference between someone who is always trying to learn and grow, takes initiative, asks for help, etc, and someone who just wants to do the bare minimum is night and day. Side benefit is this usually takes up several minutes of an interview so they can't be used on BS questions like the one you mentioned.
jiggawatts 6y ago
One day I will understand why seemingly half of all CS papers seem to be concerned with convex hulls and Voronoi decomposition. What is so fascinating about these two topics as to warrant hundreds, if not thousands of papers? I've never heard of anyone using them anywhere ever for any purpose in industry, yet these topics are a focus of concentrated intellectual study as if they were the cure for cancer.
- urschrei 6y ago
  An entire industry – geospatial – and a variety of related industries depend on high-performance CH, Voronoi, and line simplification algorithms, among others. Not to mention their importance in medical imaging applications, tomography (so, in a sense, they directly contribute to healthcare improvements). This should be self-evident, but I can provide further direct evidence if need be; I’ve implemented QuickHull, Visvalingam-Whyatt etc from the papers, and the resulting libraries see enthusiastic use in a variety of sometimes surprising fields. They get lots of attention because the problem domain is well-understood and often resistant to low-hanging optimisation efforts (computational geometry algorithms tend to be difficult to optimise)
mianos 6y ago
I interviewed at Google quite a few years ago and had a similar experience but over multiple interviews. I had 5 interviews slowly getting harder and harder questions. By the fifth interview I got past the first question pretty fast so he moved onto a second harder one that my answer did not seem to impress. After all these interviews they just never called me back again. The whole process was senseless. It was as if they wanted to find the point at which I would fail so they could stop. I'll probably hate Google forever after that. I am sure they have great people but I am always very interested when I meet someone who works there so I can ask them about what they do and they always seemed kinda average good not amazing.
- wutbrodo 6y ago
  My experience at Google was that the secret sauce wasn't that it was full of geniuses. It's that everyone was _reliably_ competent and very smart. It's hard to overstate how valuable that certainty is, and how impressive it is to manage that at scale. It enables an entirely new world of employer-employee relationships, including their famous transparency and policies that could (and would) be abused by people too dumb to understand coordination problems. The cost of this is of course going to be plenty of false negatives. (Bear in mind they were a fifth of their current size when I was there, so I don't know how much this applies anymore)
eyelidlessness 6y ago
“I would probably look it up” is the correct answer unless you’re interviewing for a very specialized role. I had a similar experience interviewing at google (and I regret not walking out), and a much more pronounced experience at MS (where I did walk out and don’t regret it).
pjmlp 6y ago
Exactly my experience twice over phone interviews with them, after the second one I actually got some kind of survey question, my answer was not to ever bother me again with stupid emails how great my CV looks like, that I would be the right person that they are looking for and then waste a couple of hours of my life with such exercises. And for what? Anyone that works with Android only has to wonder where do those algorithm magicians land at Google.
908B64B197 6y ago
I'll play devil's advocate and say I don't dislike coding interviews. Most of the time they are done completely wrong however. They are extremely useful to filter out candidates that simply cannot program, and who won't be able to no matter how much mentoring time you 'invest' in them. I've heard about interviews for senior engineers that were totally derailed by a simple FizzBuzz. I like wordcount (the wc *nix command) as a warmup/screening question simply because either: The candidate comes up with an algorithm for it and test cases OR starts counting whitespace and derails the implementation with a cascade of if-else for every new test cases that breaks the previous implementation (I've seen if-else to check for the n cases I suggested...). But honestly I feel there is so much cargo-culting for coding interview. Especially if you ask for compliable code of well known (as described by a textbook) algorithms you ultimately assess rote memorizations skills and not engineering. Convex Hull doesn't sound so bad to be honest. If I was using this question I would expect someone to be able to come up with the gift wrapping algorithm with maybe a little bit of help. What, as an interviewer, would really want to see is if the candidate can come up with test cases and a way to test whether his solution is actually a convex hull and then try to break down the problem and come up with an algorithm. I sure wouldn't expect to be able to type what's on the board and for it to compile right away (it's a board, not an IDE!) but I expect the candidate to be able to walk me through the code and run it line by line through some test cases.
- PlanetLotus 6y ago
  I don't dislike coding interviews either. But if I were asked about a Convex Hull, my response would have to be, "What is a convex hull?" otherwise I'd have to guess. I have a computer science degree, did I miss something? Is that common knowledge? Right now I have the power to look it up, but it's a little strange to me that I could be asked about that in an interview and my pass/fail would potentially depend on it (granted when I am the interviewer, my pass/fail rarely depends on the response to the coding questions). So the next question is, will interviewers explain the problem if you're unfamiliar and not "fail" you if you can explain how you'd approach a solution?
  - 908B64B197 6y ago
deleted 6y ago
[deleted]
musicale 6y ago
> with him frustrated that I couldn't remember the details of an algorithm I last had seen 6 years earlier and couldn't recite in 60 minutes what took our professor 180 minutes of lectures to cover, and me frustrated that would have taken me 30 seconds to look up. Sounds like a very effective way to filter out people who haven't taken algorithms courses recently and/or don't spend hours every week on algorithm puzzle contests or solving algorithm puzzles for "fun." They could probably save a lot of time by asking your graduation year and looking at your hackerrank score.
vs4vijay 6y ago
“Never memorize something that you can look up.” - Albert Einstein https://www.goodreads.com/quotes/24194-never-memorize-something-that-you-can-look-up https://www.goodreads.com/quotes/24194-never-memorize-someth...

deleted 6y ago

[deleted]

dmoy 6y ago

Yea I interview (and have sat on HC) at Google, and interviewers who ask these types of questions really frustrate me. If your question requires having previously memorized or being able to come up with some tricky algorithm on the fly in 45 minutes and code a solution using it, your question is probably bad. I get why they ask them - they're easy to ask, they're easy to score, and when your question inevitably gets burned because someone posted it all over the internet in their blog post titled "How I got a job at Google!!" and then bumped way up the list on hackerrankcode-whatever I forget the websites... it's easier to come up with a new one, because you just pick a new esoteric algorithm and ask that. And honestly, coming up with interview questions can take awhile. When you have 5 or 6 very calibrated questions and all of them get burned and banned in a one quarter span, you now have to spend the better part of a whole workweek, plus dozens of more interviews coming up with new questions and recalibrating. But, I just refuse to ask those types of questions anymore. They really don't give useful signal. The only three bits of signal you get are "does the candidate already know this algorithm (or are they a supergenius who just figured it out under time pressure)? can they communicate it to another engineer? can they write code?" Importantly if the answer to the first question is no, then you get zero signal on the other two parts. That basically means as an interviewer you just failed your job.

Swizec 6y ago
My favorite question to ask in software engineering interviews is one that I believe to be un-burnable. > It's 2140 AD, New York is under water up to X feet high. Buildings have been retrofitted with <magical-ish material> to withstand the water. You are in charge of keeping your building dry. If water gets in and damages the foundation, a few thousand people die or become homeless. > Design a system that ensures that doesn't happen. How candidates approach this, how they think about redundancy, how they deal with additional constraints or extra scenarios thrown at them tells a lot about how they approach things. The question is not about software (explicitly) on purpose so that it gets people out of the coding mindset. With more software-focused systems you always get candidates who starts writing code and designing objects and classes and stuff. No, I want you to design a system. Stop writing code. The reason this question is unburnable is that there's no right answer. You're being asked to show how you work through an abstract problem and design a solution. You aren't being asked for an answer. So far everyone who did well on that question has turned out to be a great engineer. Whether they were fresh out of college (and learned a lot fast) or they were already experienced.
- justicezyx 6y ago
  IMHO, this is not particular better than an algorithm question. Why not just summarizes the traits of the technical skills you expect from the candidate, lay it out, and come up appropriate questions for each interview? General software engineering interview does not work. But there can be more specific measures to improve the experience.
  - jlokier 6y ago
    > Why not just summarizes the traits of the technical skills you expect from the candidate, lay it out, and come up appropriate questions for each interview? That won't work; it's aimed at a different kind of skill. The skill the GP is looking for is ability to solve a problem you have never seen before, for a problem that bears little resemblance to anything you've done before, by transferring your existing general problem solving skills. It's a test of your ability to solve new things, which is a capability the company finds useful. This is a very useful skill, and you can learn to do it better, but it's not a "technical" skill as we usually mean it. However it is one of the things which might be associated with "great engineer". Listing technical skills and testing them will not tell you if the candidate has developed the above capability.

ladberg 6y ago

I had a very similar experience interviewing for Google. I was asked to do a task that eventually boiled down to a topological sort, and I thought the question consisted of recognizing that the answer was a topological sort and moving on because it was over the phone. However, that was not the case. The interviewer wanted me to code it all out over Google Docs, but I didn't remember the exact algorithm so I basically had to re-figure it out on the fly, which took most of the interview (I even similarly mention "in any real situation I would just look this up", but that didn't help). At the end, I had a bunch of pseudo-C++-code that should do it correctly. I thought I was done, then the interviewer said she would go go copy my code and compile it after the interview to see if I was right, which blew my mind. It was never mentioned previously that the code would actually be compiled and run, and with no syntax highlighting or ability to compile and test the code myself there is zero chance it was ever going to work. I never heard back, so I'm assuming my code failed and they left it at that. Anyway, I'm much happier now that I think I would have been at Google.

sterlind 6y ago
Yeah, Google's interviews are whack. I've been rejected twice -- I think because of flubbing an algorithm question -- and after that I designed a new algorithm for my work that's getting published in OSDI this year, I think. Their loss.
tjr 6y ago
A passage from one of Jon Bentley's Programming Pearls: As soon as we settled on the problem to be solved, I ran to my nearest copy of Knuth's _Seminumerical Algorithms_ (having copies of Knuth's three volumes both at home and at work has been well worth the investment). Because I had studied the book carefully a decade earlier, I vaguely recalled that it contained several algorithms for problems like this. After spending a few minutes considering several possible designs that we'll study shortly, I realized that Algorithm S in Knuth's Section 3.4.2 was the ideal solution to my problem. If Bentley needed to go look up an algorithm that he vaguely recalled studying in the past, just how awful of programmers are the rest of us that look things up, really?
- 6y ago

derefr 6y ago

For a company whose main claim-to-fame is indexing the web (rather than mirroring it in their databases), Google sure doesn't seem to understand that CS learning is done by mentally indexing textbooks (rather than mirroring them in your brain.)

linza 6y ago
That may be true. But then why hire someone with just look-up skills before hiring someone who really tries, and enjoys the challenge? I'm interviewing engineers frequently and although I agree that the question asked by GP is maybe not the best it still gives the signal if someone is willing to power through a problem with minimal guidance and/or ambiguous constraints. Something I'm willing to find out at the peril of pissing off a few candidates.
- derefr 6y ago
  I work with novel algorithms all day (I'm writing a decompiler.) The more I learn, the more I have confidence in the fact that I have absolutely no hope of inventing an algorithm that doesn't already exist; and that I shouldn't waste my time trying, when instead I could be spending that time digging through the nigh-infinite vault of potential solutions to my problem known as "the output of CS academia." Software engineers aren't mathematicians. We don't invent algorithms or data-structures. That's not our trade-skill. And even actual mathematicians don't sit down to solve a real-world problem that no maths they're aware of directly solve—and then produce novel maths, and then use them to solve the problem—the very same year, let alone the same hour. What I can do, as a software engineer, is to take algorithms that exist, and repurpose them or glue them together in novel ways that the designers of those algorithms never thought of, to do something new. Bitcoin, for one example, is a feat of pure software-engineering: it takes four or five existing well-known algorithms, and puts them together in a novel combination to solve a problem. I could maybe invent Bitcoin. But I can't invent Floyd-Warshall, if I don't know about it. Google doesn't employ computer scientists (i.e. mathematicians who invent algorithms.) Alphabet does, under DeepMind and Waymo; but Google itself only employs—and only needs—software engineers. Asking a software engineer, under pressure, to derive a novel algorithm, is a bit like asking a chemist, under pressure, to derive a novel class of chemical reaction; or a materials scientist, under pressure, to derive a novel material. That's not the type of pressure that a real-world person in these jobs will ever be under. And moreover, it's precisely the type of pressure that people with experience in these positions have learned to mentally associate with "going in the wrong direction, toward wasted effort", flinch away from, and to turn around and study the literature instead. It's ironic that Google expects its employees to all have university degrees. If there's one skill people who've gone to university are guaranteed to know (and to have built up a reliance on), it's consulting the literature.

NotSammyHagar 6y ago

That was a terrible interview experience. Of course anyone would look it up. I used to work at google and interviewed people as part of my job as a regular software engineer. I occasionally heard about these kinds of stories. Google didn't give much feedback to individual interviewers, no one told them if they were terrible or great questions or whatever. I also saw better interviews.

gedy 6y ago

I made the mistake of answering Google recruiter without a CS degree and "only" an EE/CompE and 10 years Software experience. Junior interviewer would not proceed past some algorithm question regarding boxes of pennies by weight, as he wanted a specific algorithm to be used in my solution, which I clearly didn't know. Recruiter then ghosted me, so F off Google for wasting my limited time like this.

jboggan 6y ago

Your story reminds me of when I interviewed at Google and did great on four interviews but the fifth one sunk me. I was asked an inheritance question which didn't make much sense (coming from a heavy Perl and Ruby background) but probably would have made more sense if I were a heavy C++ developer. I explained how the question wasn't really an issue in Ruby but the interviewer didn't like that and angrily said "you should have learned this in your compilers class at Georgia Tech!" I'm glad that the interviewer read my resume closely to learn my alma mater, but not closely enough to realize I had a biology degree from it. I tried again a year later and got luckier with my allocation of interviewers. I never did end up using any algorithms there.

rococode 6y ago

Another anecdote of an incompetent interviewer blindly looking for a certain answer: I once had an interview where, for a pretty long question, one trivial step was to check that one set was a subset of another set. Neither set had any special preconditions, just two plain unordered Java HashSets. Not thinking twice about it, I wrote a simple for loop that checked if every element in the smaller set was present in the bigger set. When I finished the question, the interviewer started questioning me about the runtime of the for loop. He started hinting that it could be more efficient, which confused me, since it seemed impossible to check every element of a set in faster than O(n) time. I also didn't see how it was useful to think so carefully about the runtime of such a trivial thing, seeing as the "story" of the problem indicated that the sets would never be particularly large and the task wasn't one that would be sensitive to a couple microseconds difference in runtime. We spent about 20 minutes stuck on this, with me awkwardly repeating I didn't see how it was possible to be faster and him telling me to just think harder and look at the problem "mathematically", "forget about the code, just think, in math, if you have a set A and a set B, how do you efficiently find if one is a subset of the other?". Eventually we ran out of time for the interview. As we wrapped up, he revealed to me the elusive answer: "Since you're checking if it's a subset, you should use the built-in isSubset() method that Java sets have". Of course, he hadn't conveyed to me at all that he was looking for a specific built-in method, so I thought there was some secret algorithm that I would have to write to make it go faster. I didn't mention that though, and instead replied that even if it were a built-in method I didn't see how it could be faster than O(n) in its implementation. He didn't have response, and just stammered something like "well it's built in and it's actually the most efficient way" and the interview ended awkwardly. Anyways, I had my doubts, so when I got home I checked. There is no isSubset() in Java sets. There is a containsAll(). It's implemented as a while loop that runs in O(n) time, making it no more efficient than writing your own loop. Naturally, the company ghosted me too.

baddox 6y ago
Three years ago I interviewed in house (after several hours of phone screens) at an SF tech company that has since gone public. The position was for a senior software engineer doing mostly backend Rails stuff. The biggest portion of the in-house interview was some fairly simple algorithm puzzle involving solving some word game given some rules and a list of valid English words. That section of the interview ended with me explaining how hash table lookups are constant time and the interviewer insisting that they are linear time. To be clear, there was no “gotcha” about collision resolution or anything subtle like that. My claim just came up as an obvious step in my explanation of the running time of my proposed solution and the interviewer jumped on it. I thought I was quite cordial, but I didn’t back down, and the interviewer seemed quite aggressive. The other interviewer in the room at the time seemed very uncomfortable with the fact that I would question something so basic, but didn’t intervene or express any “opinion” on the “debate.” I was rejected due to insufficient experience. :)

bjourne 6y ago

> I did not get the job at Google. Not to troll, but have you considered that you perhaps were not qualified for the job? There are people that can recite details of convex hull construction algorithms.

tshaddox 6y ago
But it didn’t sound like the job was for algorithm recital performances.

spankalee 6y ago

I work at Google and have performed plenty of interviews over the years. We're specifically trained not to do this. We have "feedback feedback" in our interview systems specifically for this type of situation.

abtinf 6y ago
And yet... I've read countless anecdotes about this kind of behavior, over multiple decades.
- wutbrodo 6y ago
  Your surprise comes from the fact that you're modeling an institution as a single person when it in reality consists of a hundred thousand people. It's obviously less mental effort to reason about large entities this way, but it's obviously much less accurate.
  - phendrenad2 6y ago
    That's funny because institutions can only be modeled as a statistical average of all of the humans who contribute to a given property of the institution.
    - wutbrodo 6y ago
      Untrue (there's plenty of emergent behavior in large organizations), and ignoring that, irrelevant. An obvious trivial example is looking at the property of consistency in actions: an organization consisting of a hundred thousand people is going to be far less consistent in many sequences of actions than any given person would be.
pjmlp 6y ago
Given that I gave my feedback about 10 years ago and it keeps happening, something is not right.

devit 6y ago

Well, I probably used it last time 10 years ago and still remember it. All you need to remember is that you sort points by angle from a fixed point on the convex hull, and you can easily work out the rest of the algorithm as well as the proof of correctness. Not knowing it is a relevant signal that you did not seriously attempt to compete in computer science competitions during high school and college and did not otherwise have a burning desire to learn algorithms and data structures nor a specific interest in computational geometry. Whether it's in Google's interest to select for that of course is debatable.

duskwuff 6y ago
> Whether it's in Google's interest to select for that of course is debatable. I'd argue it does not. Computational geometry is a niche. It's not even a niche that's particularly relevant to most of Google's development operations. In modern software development, knowing the detail of specific algorithms off the top of your head and being able to implement them unaided is, at best, a parlor trick. I doubt very much that it even correlates to one's effectiveness as a developer. Even for development tasks which involve algorithmic work -- which many don't! -- knowing that various algorithms exist, and what they're used for, is much more valuable than having memorized the details of how those algorithms are implemented.
- devit 6y ago
  The idea is that you might need to invent a new algorithm where a technique from an existing algorithm is used in a modified way or in a new setting, and then knowing the actual technique can be essential to find an inspiration. E.g. if you know that convex hulls can be computed by sorting by angle and sweeping, then you might come up with the idea of sorting by angle and sweeping in problems that are unrelated to convex hulls (e.g. determining what is visible from a given point in an environment with obstacles). In general, if you know a lot of those techniques and heuristics, you will be much more effective at problem solving in domains where these techniques apply. It is relatively rare for this to be a big factor in routine software development, so that's probably something one should filter for only if interviewing for roles where you might need to design novel algorithms (which Google probably has more than the average company).

sfteus 6y ago

I had several similar experiences through and after college. One in particular was while I was still in school, they had asked a question relative to performance when using views in an SQL database, and my answer wasn't satisfactory to them. Despite the interview going well up until that point, you could feel the tone shift immediately after, like they were just asking the rest of their questions as a formality and wanted me out of there as quick as possible. Didn't get called for a follow up, of course. Found out later that place was actually preying on foreign-based students (who received funding from the university to cover their out-of-state tuition difference if they worked up to 20 hours / week max for a company associated with campus) by making them work 60-80 hour weeks along side school and threatening to fire them if they told anyone, which would cause them to lose their funding and likely have to drop out / move back to their home country. I received offers from several others, some never called back. Ended up turning all those down though, as I had an interview with someone who helped step through the few mistakes I made as a learning process during the interview. One particular question I remember was basically building front-end components with Javascript, and my example had a loop with a write call in it. He mentioned he would compile the markup in the loop, then write it after it was finished, and asked why that would be better or worse. Had to think on it for a minute, but came up with a trade-off between more memory usage but less DOM writes, resulting in faster rendering. Worked that into the next coding example too, since it was similar but more complex. After the interview, when they called to schedule a follow up interview before I even made it home, I realized he was more concerned about whether I would ask for help, learn, and not make the same mistakes again. Worked there, learned a ton, became a senior dev just few years out of college, now I manage a suite of products for my current company. I don't think I would have gotten that kind of opportunity had I not had that first manager and job, so I strive to emulate that in my interviews. One of my favorite questions is something like "describe a crisis that occurred and the steps you took to resolve it," and give an example of one of my many stories of pushing bad code to production, having a server crash, etc, etc. I love the question because it involves no coding, no memorization, no regurgitating of info. Instead, it resolves around the person being a hero, which in my experience usually gets them relaxed, comfortable, and talking. You also learn a lot about their thought process: How did they first notice the issue? What was their process for triaging it? How did they debug it? If something involved in it was out of their wheelhouse did they go to someone else more experienced for help, or did they search for similar problems online to try and narrow it down? Did they delegate tasks if the workload was too high for them? Once it was fixed what was the procedure it went through for testing / verification? Did you monitor the issue afterwards to make sure it didn't come back? Once it was deployed, did you search for similar issues affecting your other systems? Did it ever come up again in new code and you were able to identify it before it was deployed? Obviously not all of these will apply to everyone, but the open-endedness of the question means you can probe a bit here and there throughout their story and gain a ton of relevant insight. And most importantly, it answers the question of "when things get tough, can you keep a cool head and think critically?" I can teach code, data structures, algorithms, whatever, to anyone. But the difference between someone who is always trying to learn and grow, takes initiative, asks for help, etc, and someone who just wants to do the bare minimum is night and day. Side benefit is this usually takes up several minutes of an interview so they can't be used on BS questions like the one you mentioned.

jiggawatts 6y ago

One day I will understand why seemingly half of all CS papers seem to be concerned with convex hulls and Voronoi decomposition. What is so fascinating about these two topics as to warrant hundreds, if not thousands of papers? I've never heard of anyone using them anywhere ever for any purpose in industry, yet these topics are a focus of concentrated intellectual study as if they were the cure for cancer.

urschrei 6y ago
An entire industry – geospatial – and a variety of related industries depend on high-performance CH, Voronoi, and line simplification algorithms, among others. Not to mention their importance in medical imaging applications, tomography (so, in a sense, they directly contribute to healthcare improvements). This should be self-evident, but I can provide further direct evidence if need be; I’ve implemented QuickHull, Visvalingam-Whyatt etc from the papers, and the resulting libraries see enthusiastic use in a variety of sometimes surprising fields. They get lots of attention because the problem domain is well-understood and often resistant to low-hanging optimisation efforts (computational geometry algorithms tend to be difficult to optimise)

mianos 6y ago

I interviewed at Google quite a few years ago and had a similar experience but over multiple interviews. I had 5 interviews slowly getting harder and harder questions. By the fifth interview I got past the first question pretty fast so he moved onto a second harder one that my answer did not seem to impress. After all these interviews they just never called me back again. The whole process was senseless. It was as if they wanted to find the point at which I would fail so they could stop. I'll probably hate Google forever after that. I am sure they have great people but I am always very interested when I meet someone who works there so I can ask them about what they do and they always seemed kinda average good not amazing.

wutbrodo 6y ago
My experience at Google was that the secret sauce wasn't that it was full of geniuses. It's that everyone was _reliably_ competent and very smart. It's hard to overstate how valuable that certainty is, and how impressive it is to manage that at scale. It enables an entirely new world of employer-employee relationships, including their famous transparency and policies that could (and would) be abused by people too dumb to understand coordination problems. The cost of this is of course going to be plenty of false negatives. (Bear in mind they were a fifth of their current size when I was there, so I don't know how much this applies anymore)

eyelidlessness 6y ago

“I would probably look it up” is the correct answer unless you’re interviewing for a very specialized role. I had a similar experience interviewing at google (and I regret not walking out), and a much more pronounced experience at MS (where I did walk out and don’t regret it).

pjmlp 6y ago

Exactly my experience twice over phone interviews with them, after the second one I actually got some kind of survey question, my answer was not to ever bother me again with stupid emails how great my CV looks like, that I would be the right person that they are looking for and then waste a couple of hours of my life with such exercises. And for what? Anyone that works with Android only has to wonder where do those algorithm magicians land at Google.

908B64B197 6y ago

I'll play devil's advocate and say I don't dislike coding interviews. Most of the time they are done completely wrong however. They are extremely useful to filter out candidates that simply cannot program, and who won't be able to no matter how much mentoring time you 'invest' in them. I've heard about interviews for senior engineers that were totally derailed by a simple FizzBuzz. I like wordcount (the wc *nix command) as a warmup/screening question simply because either: The candidate comes up with an algorithm for it and test cases OR starts counting whitespace and derails the implementation with a cascade of if-else for every new test cases that breaks the previous implementation (I've seen if-else to check for the n cases I suggested...). But honestly I feel there is so much cargo-culting for coding interview. Especially if you ask for compliable code of well known (as described by a textbook) algorithms you ultimately assess rote memorizations skills and not engineering. Convex Hull doesn't sound so bad to be honest. If I was using this question I would expect someone to be able to come up with the gift wrapping algorithm with maybe a little bit of help. What, as an interviewer, would really want to see is if the candidate can come up with test cases and a way to test whether his solution is actually a convex hull and then try to break down the problem and come up with an algorithm. I sure wouldn't expect to be able to type what's on the board and for it to compile right away (it's a board, not an IDE!) but I expect the candidate to be able to walk me through the code and run it line by line through some test cases.

PlanetLotus 6y ago
I don't dislike coding interviews either. But if I were asked about a Convex Hull, my response would have to be, "What is a convex hull?" otherwise I'd have to guess. I have a computer science degree, did I miss something? Is that common knowledge? Right now I have the power to look it up, but it's a little strange to me that I could be asked about that in an interview and my pass/fail would potentially depend on it (granted when I am the interviewer, my pass/fail rarely depends on the response to the coding questions). So the next question is, will interviewers explain the problem if you're unfamiliar and not "fail" you if you can explain how you'd approach a solution?
- 908B64B197 6y ago

deleted 6y ago

[deleted]

musicale 6y ago

> with him frustrated that I couldn't remember the details of an algorithm I last had seen 6 years earlier and couldn't recite in 60 minutes what took our professor 180 minutes of lectures to cover, and me frustrated that would have taken me 30 seconds to look up. Sounds like a very effective way to filter out people who haven't taken algorithms courses recently and/or don't spend hours every week on algorithm puzzle contests or solving algorithm puzzles for "fun." They could probably save a lot of time by asking your graduation year and looking at your hackerrank score.

vs4vijay 6y ago

“Never memorize something that you can look up.” - Albert Einstein https://www.goodreads.com/quotes/24194-never-memorize-something-that-you-can-look-up https://www.goodreads.com/quotes/24194-never-memorize-someth...