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...) 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.
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.
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.
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.
> 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.
> It's a test of your ability to solve new things, which is a capability the company finds useful.
Correct.
I work with early-ish stage startups. There's always a library that solves any given known problem. We don't have the scale or nuance to need to reinvent the wheel.
Where I really need engineers to shine is in solving the parts that don't have a library because we've stumbled onto something new. Or at least something new to the team. Or the way we've cobbled libraries together creates something new.
The important work is the work you haven't done before. We're engineers not line cooks.
November should involve completely different work and a whole new set of problems than February. If you're still doing the same thing you did in February, something's gone wrong.
The GP isn't asking a very good question to identify that skill, is the point. Interviews in other technical industries don't ask these kinds of questions, because they're not really useful as a gauge of, well, anything useful.
I would love to ask questions like that. I'm pretty sure hiring committee would not like it though lol.
I do worry about asking questions that give candidates extremely large advantages if they have certain backgrounds. For example someone coming from mech, civ, or petroleum engineering will get a huge leg up on that question.
It is also worth noting that the structure for interviewing at a company with 30-50k+ engineers is different than the structure you need for interviewing at a company with <<1k engineers.
Me: "I'm a software developer, so I would let a material science engineer figure it out." You: "You can't do that... All the material science engineers have drowned." Me: "That's not very realistic..." You: "Thank you for your time. Don't call us, we'll call you."
"Ok the material science engineer gave you the fancy material. It was applied. As you know, nothing is perfect and lasts forever. How do you ensure your building doesn't sink?"
I'd let the material science engineer figure that one out too. No way in hell would I risk my ignorance of building maintenance be the cause of thousands of deaths.
The materials engineer can give you a great material. They can't design a system to monitor said material for defects.
S3 bucket had public access enabled... we asked a software engineer to do something that they're not the expert in.
One thing I learned in getting my engineering degree is that it’s unethical to practice engineering in an area you don’t understand. No way would I ever try to apply my software engineering skills to a materials problem
I feel it's only unethetical if there are "real" stakes on the line. E.g. Where people can get hurt. I don't mind a mechanical engineer writing code for a company that makes the zillionth vapid webapp nor do I mind a software engineer designing a mechanical watch.
Use <magic material> to build a wall around the city? Have the people who maintained each individual building form a team that can keep an eye on sections in shifts? If we have enough magic material, build a double wall system for breaches?
I'm done. Give me my paycheck.
> Use <magic material> to build a wall around the city?
That sounds expensive. Do we need to do that? Does it solve the problem better? Does it maybe create a worse solution? How would you find out?
> Have the people who maintained each individual building form a team that can keep an eye on sections in shifts?
How would you make this less time intensive? Can you use automation?
> If we have enough magic material, build a double wall system for breaches?
Is there a cost-benefit analysis you can run here? How would you find out? Should we keep adding walls ad infinitum or does each additional wall have diminishing returns?
> I'm done.
wrong.
It would be probably cheeper - simply because the perimeter would be shorter than the sum of perimeters for most of buildings included in the city/district. That is what cities did since at least Neolithic til moment when cities become undefendable (because of cannons and airstrike).
But that is probably not the point. In order to build wall around the city, you need to have power or consensus in society to deliver this decision. And achieve that in reasonable time might be unreal for someone in charge of one building.
I can't tell if you're asking these questions to elicit a longer discussion, or if you are doing so because you don't like the idea of a simple solution.
Seems reminiscent of the tales of early 2000s Google interviews, of the "estimate how many golf balls fit in an airplane" variety.
I'm not convinced this offers a useful selection criteria other than boosting your unconscious bias on who "seems smart", but on the other hand I'm also not convinced it's any worse than the standard modern Leetcode interview.
Funnily that old style of question is far closer to my day-to-day as an engineer than a leetcode algorithms question. Most of my job involves figuring out solutions to fuzzy problems based on unknown constraints, undiscovered requirements, and often unclear end-goals.
"How would you fill this airplane with golf balls?" is a fantastic question. If the candidate doesn't reply with "Why? What are you really trying to achieve?", they're gonna do poorly in modern software development.
Caveat: This does not apply to junior positions where you are expected to bang out code based on super fleshed out requirements and constraints.
I suppose it depends on how you grade the answers. Like I have bad spatial awareness in terms of how big things like planes are. I genuinely don't really have an idea how long a commercial airliner is, or how big a ping pong ball is. I feel like I'd do ok if I could get reasonable approximate values for things like the size of the plane, the balls, the seats, etc. if I also have to supply those values myself the end result is likely to be off
The end result being off is fine if I am being graded based on my thought process, but a disaster if I am being graded at having an idea of the size of airplanes before walking into the interview.
Like I said, the point of this question isn’t to seek your domain expertise, the point is to see how you use other people’s domain expertise to create a [software] system.
The way you ask it sure. I'm just not sure that is how everyone asks it, though maybe it is. I've never been asked something quite like that before but some comments I've seen around seem to imply some people want a close to accurate answer.
Commercial airliners vary in size more than an order of magnitude anyway. There are commercial aircraft that are shorter than an A380 is tall.
The fuselage of a 737 is the same diameter as the engine of a 777.
Why? Isn't the better question "how would you solve <the actual thing they are being hired to solve>"?
I hire people to track objects via computer vision. I ask them "hey, here's a system I want, what approaches would you take", and explain that this is a 3 year research project, of course they will be giving simplistic and wrong answers and there is knowledge asymmetry here, but I'll inform you as you go as to what works and not. "Optical flow". Okay, why? What's the general algorithm? Okay, so it turns out it doesn't work in our situation because X,Y,Z. Any ideas on what you'd look at next. And so on. Because that is exactly how my day-to-day conversations and work goes. Bounce ideas off of co-workers, latch onto something that seems promising, explore, maybe it works, maybe it fails. If it fails, what does that tell you about what to try next. Along the way you can have them code a tiny piece of something they mentioned if you want to see some code. But basically you are seeing if they understand the domain you are working in (which is not golf balls on airplanes), if they have some (not comprehensive) knowledge of the domain, and if they understand book solutions don't necessarily deal with the messiness of the real world and can adapt approaches to appropriately (i.e. a 20sec/frame algorithm is not going to cut it when I need 180fps).
It bothers me that this is still somewhat unfair due to the vast information asymmetry, but I try to deal with that. And my own biases can creep in. Are they mostly using 1980s style image processing techniques? Do they understand Bayes? Do they throw ML at problems that aren't tractable that way? It's unlikely that their past experience & preferences reflect exactly what we need. What is important - can they adapt, or even better, communicate why my choices are wrong and theirs are right (I don't need a robot to grind out code reflecting my ideas, I need them to figure things out and solve things in a fairly scientific manner).
So those are the questions I try to ask. I have no evidence that I get it right, but I haven't been disappointed with the hires.
I think your approach is pretty optimal, but at larger companies the candidates might be interviewing for the company as a whole and not for a specific team.
Interesting you mention 80’s style image processing techniques. Please take care with these kinds of biases. Often older techniques are superior than ones that are merely fashionable today. I’ve also been around long enough to see pendulums go back and forth at least once in the AI realm, never mind tech in general.
Mind you, I’m not saying you’re wrong to discount people who fail to stay abreast in their field, just know that sometimes there is wisdom in ignoring popular trends, or revisiting old techniques that might benefit from a different landscape.
I don't think they were looking for the right answer; I think the goal of that type of questions is to see how does the candidate approaches it. It's especially valuable with college hires.
Some candidates will simply freeze if they don't know the answer. Some will try to estimate the dimensions and come up with an estimate. I think Google wanted to try to anticipate what a person would do when stuck by asking these types of questions.
This is a terrible question. Problem solving ability doesn't exist in a vacuum. Our experiences give us resources to draw from to combine in new ways that allow us to solve novel problems. Asking a software engineer to solve a problem in a dissimilar domain is badly missing the point of screening software engineers.
Sure, you may say that everyone who does well turns out to be a great engineer. I'm sure Google says the same thing about their algorithm trivia tests. Presumably the goal is to move away from these seemingly arbitrary and irrelevant tests. Just replacing one arbitrary and irrelevant test with another isn't improving the state of things.
I disagree. The goal of this question is to see how you utilize domain experts as a resource, add your software expertise, and design a comprehensive solution. It is specifically not a question about what you already know.
In the interview I play the domain expert.
This is exactly what your job will look like: collaborate with domain experts, use your software skills, solve real world problems.
I don’t need an engineer who can build a queue. I need an engineer who can use a queue.
Have you considered asking questions that involve queues.
Properly testing for a "solution engineer" (which is what you appear to be testing for) would pose a question that is a legitimate "software" problem and "domain experts" would be in areas such as say "electronic payments". Candidate would be expected to demonstrate ability to devise proposals for a 'functional solution to a business requirement' using available domain experts.
The key phrase is yours: "real world problems". Your hypothetical misses that by a generous mile.
And I apologize about this but we're discussing actual issues with software recruitment:
One major problem noted by senior engineers subject to these interviews is the competence level of the interviewer. I had this one guy, a "principal engineer", ask me about "Optimistic locks" as his initial query into my knowledge of concurrent systems. It took a lot of self-restraint to not blurt out "You mean optimistic locking?"
It is amazing to me that we somehow managed to hire very good software workers in the 90s without any of these shenanigans. One thing that does stand out from my memory of the 90s: we had senior colleagues (with literal white hair) in senior engineering positions. Go figure.
I think you are doing it right.
That's... part of the plot of the novel "New York 2140". Was that intentional?
Call uber boat. Have people evacuate. Problem solved. Building gets collected by the garbage collector.
This is an awful question for hiring software engineers. It’d be like asking a building engineer what quicksort is.
It’s unfortunate that this bizarre and arbitrary stab at analytical thinking assessment is still used to evaluate the skill of software developers.
Here’s another idea: have them write software. Not algorithm trivia, but actual software. Keep the scope small so there isn’t an onerous time commitment and have them explain their choices.
> Design a system that ensures that doesn't happen
Well, if we live in a world with magic, I would just use the magic material to make a machine that removes the water magically.
I think they may also ask them because they want to see how you do at the specific task of taking a problem you remember the pseudocode algorithm for, and actually turning that into working code in a real programming language. You know, the "schlep" part of programming.
I feel like they don't realize that this is the goal they're calibrating these questions toward, though. If they did, they wouldn't require the "from memory" component—instead, they'd break the question into two parts:
1. tell me what algorithm you would use to solve this problem; or, failing that, tell me what criteria you'd use to select the best algorithm for solving this problem out of a set of candidate algorithms.
2. Here's a journal paper, explaining a particular data structure + set of algorithms that can† be used to solve the problem we're talking about. All the algorithms in the journal paper are in that sort of declarative, math-proof-phrased pseudo-pseudo-code form. Now take this journal paper and turn it into an implementation in your language of choice. Explain your thinking as you go.
† The paper chosen is not the one corresponding to the algorithm the candidate chose; nor is it the one corresponding to the algorithm that's "right" to pick for solving the problem. It is, in fact, randomly-chosen from the pool of sub-optimal solutions to the problem, filtered for the ones that get rarely used in practice and so have no easy non-journal-paper presentations of a reference impl laying about on the web to study. Alternately—if the interviewer has enough time to explain a second problem—it could even be a paper randomly-chosen from the pool of all algorithms papers!
Benefits:
• Both task 1 and task 2 are things "senior" engineers do every day in the real world.
• There's no component of memorization; the step "between" step 1 and step 2, where you'd look up the journal paper corresponding to the algorithm you thought of, is dropped.
• You can't really "burn" either task.
Yup if you are willing to explain the algorithm to the candidate and not dock them any "points" (or whatever) for having to explain the algorithm, then this works fine. I have no qualms about having a discussion about an algorithm that's tricky, and seeing how the candidate works through it.
That's not what I see in practice though. Not remembering the whole algorithm at best ends up wasting half of the interview (code the remainder in 20 minutes??), and at worst gets explicit language from the interviewer like "TC couldn't figure out <insert tricky algorithm> and I had to explain the algorithm to them explicitly, WEAK/BORDERLINE on algorithms".
I should also say, I dislike doing any engineer interviews that are purely talk-about-algorithm without any code, because I've interviewed a disturbingly large number of candidates who cannot write about 10 lines of mostly-bug-free code with a single state variable and like one loop, in 30+ minutes.
> That's not what I see in practice though. Not remembering the whole algorithm at best ends up wasting half of the interview (code the remainder in 20 minutes??), and at worst gets explicit language from the interviewer like "TC couldn't figure out <insert tricky algorithm> and I had to explain the algorithm to them explicitly, WEAK/BORDERLINE on algorithms".
It is kind of hilarious to get an algorithm problem which took eminent computer scientists years to solve the first time. "Why yes, I am Donald Knuth/Edsger Dijkstra/et al. – only smarter, luckier, and much faster!"
As you note, the initial question is basically "how well do you recall the solution to this problem?"
If I liked spending time memorizing long stretches of text, I'd be a doctor, not a software developer.
What on earth is wrong with asking to see the interviewee's code? Skim over it looking for neatness, how they comment, what build procedure is there and quiz them about what you see: anything from language choice, to build reproducibility, from architecture to install. And of course quiz them on algos you see.
All of these 'tricky' exam style questions don't show a thing about the person sitting in the interview room.
I've hired based on a good discussion alone, without code... And got a great engineer.
You lose out on candidates who work at companies that don't let them show you their current code, and have a home life that occupies their time outside of work.
So, you can ask to see candidate's existing code if you work at a small enough shop and/or don't care about missing out on candidates who don't have shareable code. But if you are trying to hire at a larger scale, it does not work.
Many great hiring schemes work until a certain scale and then they fall apart. Some hiring schemes also severely tilt your candidate pool towards a certain subset of the population. I'm sure whiteboard style interviewing also has similar issues.
In addition to the sibling's excellent "candidates who work at companies that don't let them show you their current code, and have a home life that occupies their time outside of work", here's another category of candidates you lose: people who code differently in their downtime than they do at work.
If you looked over my github, you would see most of my commits are ones that, at work, I wouldn't accept from anyone. The code is sloppy, there are no tests, it looks like someone was just trying to get something working as quickly as possible with no thought for maintainability or understandability. But, of course, that's exactly what I was doing! When I code in my spare time, I'm solving problems that I've run into in my spare time, and I approach it very differently from in my work life. The constraints are different, and so the solutions are different.
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.
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.
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?
"Never memorize what you can look up in books" is often attributed to Albert Einstein; the long version is "[I do not] carry such information in my mind since it is readily available in books. ...The value of a college education is not the learning of many facts but the training of the mind to think."
https://en.wikiquote.org/wiki/Albert_Einstein#1920s
Man, one time I had an interview at a startup. They asked me some fairly trivial questions and I wrote some pseudocode which they were fine with. Then in the last 5 minutes they were like, "well, let's get this ready to run in a browser." I was shocked and stuttered out something like "wait, this was pseudocode, I'm definitely not going to be able to make this run in the last 5 minutes," and they said something like "oh, OK" and wrapped up.
That was the entire phone screen, and they failed me. This still burns me years later because it was such an obvious communication failure on their part - if you're one of the rare interviews that actually require me to write working code, you better be darn sure to mention that upfront, rather than 5 minutes before the end of the hour! - and yet I was the one who failed.
The entire concept of asking someone to write code in Google Docs is just insane to me. No one would ever do that on a job, because it's remarkably awful and difficult, and the editor will fight against you every step of the way (auto-capitalization, just to name one thing).
And yet somehow interviewers think that this will give them a good picture of how you'd do work on the job. Baffling.
They're doing it so that they can see your edits live, "prooving" that you're not cheating in some way.
But yes, this is asinine. Sharing your desktop through a video conferencing program and using the IDE of your choice would be far more realistic test, but Google likes to put hoops up to jump through that are smaller than your body.
Why can't you contort yourself like an octopus!? Fail!
Nah, it's because this is the process for phone, not video, interviews, which are somewhat more accessible. And you need the ability to record the code at the end anyway (which docs provides and a video doesn't).
Yep, it was a struggle even when I thought I was supposed to be writing pseudocode. I've had some really great interviews using coderpad and similar software (including the company I'm at now), and it's such a better representation of how the interviewee actually codes.
I don't get how my interviewer (an engineer), didn't see the problem with it. I know that Google wants to use their own products, but that can't possibly be the norm for other Google interviews.
I had the opposite experience in a Google interview.
I just said, that can be solved with a topological sort, and then we moved on.
But I failed with another interviewer. He kept asking how to prevent hashing from producing collisions. The answer was universal hashing, but I had forgotten about that
Typical. Universal Hashing as a concept is only interesting to cryptographers, and people who are completely obsessed with obscure hashmap trivia (i.E. FAANG interviewers).
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.
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.
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.)
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.
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.
I think the point is that no one is being asked to derive a novel algorithm. It’s taken for granted that a person with enough experience will have an understanding of broad categories of algorithms and should be able to reason about the small changes to those algorithms that would be necessary for practical application.
Can you offhand write C++ code for a 2-3 Finger Tree, including the changes necessary to make it efficient in a strict language?
I think if it this way (very simplified): there are candidates that like challenges and who don't mind imperfect interviewing situations, and i had my fair share of people who dislike it would fare better if we just let them work on a real world problem. We did both for each candidate for some time, but the latter was much more costly and didn't provide such a good signal in the end.
Open-mindedness goes a long way. Also typically our interview questions are set up in a way where it's expected you won't finish but try, which reveals a lot about personality and how problems are attacked.
I don’t think the point is being able to use a specific language or to know a specific algorithm, unless the role requires it. If the goal is to test a person’s knowledge and understanding, then the actual implementation is probably less important than their ability to explain and reason about the problem. OTOH, if the goal is to find out whether the person is highly skilled in a specific language and has a lot of experience with an algorithmic domain, then what you’re asking isn’t unreasonable.
> why hire someone with just look-up skills before hiring someone who really tries, and enjoys the challenge
This attitude will keep you from hiring someone who will just "do the right thing," which is to look up stuff that can be looked up, and also persevere when an off-the-shelf solution won't be sufficient. Plenty of engineers will spend time trying to reinvent the wheel when it is totally unncesssary.
True, but in my experience it's easier to teach resourcefulness after hiring than injecting motivation for solving problems somehow.
At some point we had a brilliant junior dev who had a task to add some logic to some ES plugins in Java. When the code review went up, it was all a single Java 8 stream statement. He went out of his way to convert everything to a stream because he enjoyed the challenge I guess. It was 3 pages of nested declarations and inscrutable.
He left eventually but person was hard to work with because you had to beat back this kind of shenanigans every step of the way.
I don't really see a hard distinction between meat memory and silicone memory, so I've never bothered to memorize stuff that I could simply lookup. To me, it seems almost ridiculously inefficient to carry around large amounts of indepth data in your brain, which is limited, costs constant energy to maintain, and isn't even particularly good when it comes to fidelity of recollection and searchability.
It's much more efficient to remember the general shape of problems, to remember where you can find further information (books, chapters, etc). Remembering that something is a well-studied problem, and where to find a solution, is straight-up more efficient than remembering that solution.
Dijkstra once remarked that trying to make a computer act like a human brain was far less interesting than seeing what the limits are of a computer as something that is unlike a human brain. It seems the reverse observation is also true - human brains, once freed from rote memorization and computation (that's literally what programming does to us), can tackle much larger, more interesting, and more complex problems.
If I had any wit, I would have responded to the convex hull question: "I would look this up on the Internet, assuming there is a search engine good enough to find the algorithm."
Lovely!
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.
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. :)
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.
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)
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.
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?
I would never fail someone for asking questions.
I liked the convex hull problem because it's easy to sketch in 2D and explain in case someone doesn't know what it is.
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.
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.
> 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.
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).
Your entire premise is based upon the fact that this wouldn't be discoverable for anyone that didn't already know the algorithm.
Yeah, I remembered the sort by angle part and the broad strokes after that, but there were some details I forgot so I missed some corner cases.
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.
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)
“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).
> 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.
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.
“Never memorize something that you can look up.” - Albert Einstein
https://www.goodreads.com/quotes/24194-never-memorize-someth...
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.
And yet... I've read countless anecdotes about this kind of behavior, over multiple decades.
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.
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.
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.
Given that I gave my feedback about 10 years ago and it keeps happening, something is not right.
> 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.
But it didn’t sound like the job was for algorithm recital performances.
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.