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.
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.
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.
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.
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.
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?"
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.
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.
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.
> 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.
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.
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.
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'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.
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.
"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 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.
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.
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.
I'm done. Give me my paycheck.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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?
And yet somehow interviewers think that this will give them a good picture of how you'd do work on the job. Baffling.
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!
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.
Their loss.
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
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.
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.
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.
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.
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.
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.
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.
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.
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. :)
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.
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 liked the convex hull problem because it's easy to sketch in 2D and explain in case someone doesn't know what it is.
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.
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.
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).
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.
And for what? Anyone that works with Android only has to wonder where do those algorithm magicians land at Google.
https://www.goodreads.com/quotes/24194-never-memorize-someth...
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.
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.