Ask HN: Can engineers from Google or Facebook solve whiteboard questions easily?
I don't know any people from those companies. I am just curious.
However, large numbers of engineers at Google are very good at solving whiteboard questions. A lot of it comes from practice, a lot comes from knowing the common problems and solutions, and a lot comes from knowing the algorithmic primitives from which modern algorithms are born.
For many, whiteboard questions are "fun"- in the same way my parents like to do crossword puzzles for the intellectual exercise, Googlers like to discuss challenging, abstract-but-related-to-ads-or-search questions.
What is a good way to learn more about these?
What a utterly stupid and broken process. All it's testing is recall, that you've memorized some algorithms that 99% of developers will never need. Especially when these are really hard problems that people have studied for years, to think that anyone who hasn't memorised the solution is working this stuff out in an hour on a whiteboard is craziness.
You might be "fine" without it in a certain category of job, but rather than be dismissive about it you could be excited about having a massive wealth of information that you can use to do your job better.
There will always be something else to learn, wether it be how to apply Domain Driven Design to your work or how to work with graphs when munging data. It's always worth it.
[edit] Run on sentence
Having a basic understanding of these things is NOT the same as being able to regurgitate them on a whiteboard, under the stress of the interview process.
Because of this. So that when you encounter a problem, you know how it can be solved efficiently. If you disregard existing knowledge, you are likely to spend a lot of time cooking up something complex and half-assed that creates an unnecessary maintenance load.
Like music is composed of fundamentals, similarly most problems in computing can be decomposed such that familiar approaches can be applied to them. I think the categorization of Aho's "Foundations of Computer Science" is pretty much to the point on which fundamental formulations are practical to know.
Unless you are stuck on an Island coding during a vacation, not one person on earth faces this kind of a situation.
Almost anybody doing anything apart from basic beginner level coding work knows to look up to a solution on the internet if a solution is not scaling already.
This applies to some practical areas, but some are murky and need more than agile google-fu to waid through of an algorithmic jungle to a solution that provides added value to end user.
There is a discipline and domain dependent threshold where the internet suddenly becomes obscure and unhelpful when one is trying to find solutions. In these instances either you are solving the wrong problem, or the problem is quite complex and/or does not have a closed form/ready solution. The best thing to happen in these instances is that one can limit ones input domain just so that it maps to some algorithmic concept or another. It's not rocket science, but in these instances having an intuitive feel toward the big O behaviour and various algorithmic constructs is really, really helpfull.
Sometimes you just need to implement your own fudged QR decomposition and understand a little bit of numerics, or build custom octrees and whatnot. Couldn't really do it without my books. I do CAD and computational geometry stuff, YMMV.
In fact that is exactly I was trying to imply. Questions need to be about the area of your work, rather than testing candidates on proxy subject totally irrelevant to their jobs.
While I agree that the process is broken, a solid understanding of algorithms and data structures is very important for developers at my company. And nobody knows all, or even most of the algos or data structures! But we do have large amounts of data and some pretty complex analytic problems, and a poor design can cost a lot of time and AWS $. Likewise over-engineering something small is a waste of time not just in writing but maintaining it.
I agree that most e-commerce or business web developent probably don't need this level of formal skill.
Whiteboard questions are useful, but not for figuring out trick questions. Instead for figuring out how the candidate approaches problems.
What new problems are you working on that require you to invent novel algorithmic techniques?
For example, the reduce phase of MapReduce is pretty much "apply the algorithm you want on this List", and that's where knowing good list algorithms (for example) shine.
Which why I ask again. Please list your problem which is so novel it requires you to invent a novel algorithm.
Please note statistics is a science that has existed for centuries now. Unless you are in a university, its highly unlikely you have a problem that will need to you to work on something that novel.
It seems to me you mix statisticals approaches and algorithms, meaning you completely ignore the fact that code runs on computers, and that computers have mechanical characteristics, making two implementations of the same statistical approach wildly different in performance.
I used to work at a company where some guys spent literally weeks inventing a fast way to do a dot product over huge vectors. Which doesn't mean they invented the concept of dot product.
Very nice that you bought up this point. This is exactly what I was trying to point out. If a team of full time working people took weeks to arrive at a working solution, despite a massive body of open knowledge available as a reference to prior solutions, there is absolutely no way a candidate can give even arrive at a decent direction to the solution in under 45 minutes in a interview situation.
No one is saying algorithms are not useful.
But there is a very big difference between knowing an algorithm and inventing an algorithm. Testing the former is no indication of the latter, as illustrated by your own example.
[1] https://lintool.github.io/bigdata-2018w/slides/didp-part02b....
[2] https://lintool.github.io/bigdata-2018w/slides/didp-part09b....
Secondly, you are not inventing any algorithm there. You are only using algorithm invented by others.
Thirdly, you are only deciding what solution works better.
Lastly, in an interview you have to invent this algorithm in 45 minutes.
None of this involves you to invent a new algorithm. At least not in 45 minutes. I doubt if the person giving that talk himself did it so quickly.
Another example is lexicographic range sharding, which uses reservoir sampling to compute optimal tablet key split points by doing a constant-space-and-time heuristic sampling over the keyspace.
I used to think MR was just brute force, but it has many levels of algorithms. Probably too many- at some point it because hard to analyze how the system worked because of the various kinds of hedging and recovery strategies.
Which is precisely why testing candidates on such questions doesn't make much sense.
I understand every once in a while something like that needs to get written, but again that's like an exception.
Aho and Ullmann: Foundations of Computer Science (old but really, really, really good)
Steven Skiena: Algorithm Design Manual
Abelson: Structure and Interpretation of Computer Programs
Foundations of Computer Science, full book: http://infolab.stanford.edu/~ullman/focs.html
Also turns out Skiena's website is a very large resource!
I guess that would be a trick-question then, as nobody ever solved an NP-hard problem in linearithmic time.
I had never heard of that happening! It would be extremely cool if it ever worked.
>An event in Dantzig's life became the origin of a famous story in 1939, while he was a graduate student at UC Berkeley. Near the beginning of a class for which Dantzig was late, professor Jerzy Neyman wrote two examples of famously unsolved statistics problems on the blackboard. When Dantzig arrived, he assumed that the two problems were a homework assignment and wrote them down. According to Dantzig, the problems "seemed to be a little harder than usual", but a few days later he handed in completed solutions for the two problems, still believing that they were an assignment that was overdue.[4][7]
>Six weeks later, Dantzig received a visit from an excited professor Neyman, who was eager to tell him that the homework problems he had solved were two of the most famous unsolved problems in statistics
https://en.wikipedia.org/wiki/H._Christopher_Longuet-Higgins
https://www.nctm.org/Publications/Teaching-Children-Mathemat...
The problem sets would have several questions you were expected to solve, and then often 1-3 questions marked with 1 or 2 stars. I forget exactly the language, but there was some explanation that you probably couldn't solve the 1-star problems, and solving the two-star questions could be someone's PhD thesis, as it would require novel insight into an unsolved problem.
The point was that it was a class for young aspiring mathematicians many of whom were used to being the smartest person around, and this helped them confront problems they couldn't solve without feeling like total failures. Also at that kind of school, you never know, someone might be able to solve one.
[1] http://www.huffmancoding.com/my-uncle/scientific-american
That class led to a ton of imposter syndrome that took me decades to overcome. Thanks, Huffman.
What is the time resolved flourescence of a fluorophore in 4 dimensions?
The solution, explained to me by my friend who was a very smart physicist, was the first time I heard the word "tensor" (this was a long time ago, long before machine learning used that word) and I was obsessed with the idea that there was all this cool math you could use to solve hard problems.
Many problem solutions at Google are effectively heuristic approximate solutions to NP-hard problems (or less hard but interesting problems).
There's no trick, they just want to know you can figure out how to compute things quickly so they can run online in a server or a batch job. And the things that need to be computed are often problems with high time or space complexity and the exact answer doesn't need to be known.
Often (most?) of the time, heuristic solutions are also found by Complexity Theorists, and they usually can prove that their solution is efficient for problems with certain characteristics, e.g. random data, not random data in a particular way, etc. These are then applied by the industry when they come across problems with these characteristics.
1. Most data sets are roughly similar (or at least fall into one of a few cases).
2. Most algorithms are designed beforehand, on ideas of what data could be, not necessarily for actual data.
Take for example sort algs. Sure, you could look at your data and devise a sort that exactly matches it most effectively. But in reality, in most cases, people just use quick sort, which is proven to be efficient on most data sets.
I am, I think objectively, a pretty good software engineer and often couldn't solve my peers interview questions in the time allotted. I try to do my part by conducting interviews with questions that I think demonstrate the ability to actually code and think abstractly as opposed to regurgitating some random algorithm that has been memorized. I ask a simple CS 100-200 level, one-word-answer question about an algorithm and then move on to a coding question.
Despite the difficulty of some of the questions that others ask, often the interviewer wants the interviewee to pass and so will throw a hint. It's important to keep commicating because that is how those hints will be delivered.
Ironically, I never interviewed because I came in from an acquisition. Yes, I was very lucky.
I didn't know what "CLR" was, so I searched around: Cormen, Leiserson, Rivest's "Introduction to Algorithms" [1].
[1] https://en.wikipedia.org/wiki/Introduction_to_Algorithms
[1] https://www.quora.com/What-is-the-difference-between-CLRS-se...
That said I see two kinds of interviewers. One kind (the good kind) takes a medium difficulty question and uses it to explore the candidate's coding, algorithms, communication, and problem solving skills.
The other kind has a super hard question with a single algorithmic solution that tells you nothing about what kind of engineer the person would be. This kind of interviewer takes too much pleasure in being a gatekeeper to Google.
FWIW my understanding is that the Hiring Committee tends to discard feedback from interviewers like your latter type here.
Just like getting into YC isn't necessary to be a successful founder, getting into Google isn't necessary to be a successful engineer. There are tons of companies out there, and many pay better than Google.
I didn't feel like giving that feedback to the recruiter would help if it was already known well in advance. That and a lot of other signals in two interview cycles seemed to indicate that the recruiter and/or Google were perfectly happy wasting my time, and I've not really felt like bothering to interview with Google since.
Those would be? The only one I have actually seen (claimed) numbers out of that can beat Google is Facebook.
I don't see how companies that claim it's hard to find talent can be OK with a system that would reject more than a small portion (<5%) of their current productive engineers.
Edit: fixed word sense ambiguity
Also, good SAT scores don't always translate into good college students and the same could be said for good whiteboarding skills don't translate into good software engineers or vice versa.
I don't either, but it's an easy game to play: start a company with an impossibly difficult goal (e.g. build a more popular social network than Facebook in two years, colonize Neptune, cure cancer) and then complain that there isn't enough talent in the labor pool. Finally, blame the government.
I’ve heard this joke at a lot of tech companies. Also, “the hardest thing I’ve ever done at my job was pass the interview.” Just shows how divorced from day-to-day work skills interviewing has become.
I think most tech companies severely overestimate the cost of false positives, particularly in the USA where it’s trivially easy to fire someone who turns out to be a dud.
Also think it represents an opportunity: if you could reliably figure out who made it to the interview stage at these top companies but did not get an offer, you could forego your recruiting expense, simply hire all those people and likely end up with a well above average team, minus the few false positives.
I don't think that's actually true. People who are net-negative on a team may be very personable and hence emotionally difficult to fire. And of course the U.S. does have a number of protected classes, who can be very difficult & expensive to fire for cause (because the assumption is that they were not fired for cause). I'm a member of a protected class, and I often worry that it actually makes it more difficult for me to get hired: will folks be willing to take a chance on me, knowing that were I a jerk I could make life difficult for them? I'm not a jerk (I think!), but they can hardly know that!
Those people are rare and generally caught by much lighter screening.
> And of course the U.S. does have a number of protected classes, who can be very difficult & expensive to fire for cause (because the assumption is that they were not fired for cause).
I don't think you are using "for cause" in the proper legal sense. Firing "for cause" is indeed an time-consuming and potentially expensive process because of the effects on things like unemployment benefits. Firing "without cause" is not, and is permissible in almost every state.
What you are describing are potential accusations of illegal discrimination. This is largely orthogonal to cause.
Technically speaking, we all are, no? We all have genders, sexual orientations, races, ethnicities? Of course you probably meant that you fall into a minority group in one of those classes, but pretty much anyone could allege they were discriminated against based on their protected characteristics, even if sometimes it's not a particularly believable claim.
There is also a concept of 'machine coding round' in a few companies here in Bangalore. Where you are given like an hour to implement sort of like fairly medium application.
You could write a perfectly working application, but if the evaluator thinks its not simple or complicated for their taste, its still a straight reject.
Its almost like they want cookie cut candidates who practiced interviewing day in and out for years.
The real practical world experience is largely considered useless.
https://programmingpraxis.com/2012/01/20/knights-on-a-keypad...
This is a great question because it has several levels of solutions:
1. A recursive solution that iterates over all sequences, exponential time and logarithmic in space. Interviewing for T3 (entry level, think college grad), getting only this far in 45 minutes earns a "leaning no hire" in my book.
2. The above solution except with memoization, which reduces the runtime to linear but requires linear space. This one earns a "leaning hire" from me.
3. A dynamic programming solution that takes linear time and constant space. This one gets a "hire" to a "strong hire," depending on the elegance of the implementation and the strength of the discussion we have around it.
4. A logarithmic time solution involving adjacency matrices, matrix multiplication, and binary decomposition of numbers. I've never seen anyone get this and I only learned about it after months of asking this question.
It's shocking how few candidates actually got as far as solution 1. I kinda want to open this up to the HN comments section, because this does not strike me as a brutally difficult problem, but the rate at which people fell on their faces when presented with this question suggests either something about our interview process or about the candidates we interview.
EDIT: A clarification about “getting as far as” a particular solution: I’m not sitting there stone faced taking notes, I provide hints and prods and suggestions to push candidates toward more optimal solutions. I want the candidate to get as far as possible because it feels good to watch someone succeed, but oftentimes they run out of steam or take forever to implement their solution. In particular with respect to solution 1, if that’s as far as a candidate can get despite my recommendations, that’s not a good sign for their algorithmic ability.
I've had to deal with an algorithm problem of this difficulty once in my entire work life and I was given a week time to go figure out the best way to go about this.
Your problem creates an unrealistic standard of a software developer. You don't get to see something like their coding quality which is a lot more important in a candidate than their ability to solve an arbitrary algorithms question. Especially since these algorithm quesstions are now being studied for the sake of interviews. Rather than to learn something.
It's shocking to me how many engineers I come across that think having an algorithms based interview actually gives them good results.
Its more psychological than technical.
Once a person knows how to do a thing, they start to think any one who doesn't, is stupid.
Their intelligence becomes the baseline to measure others intelligence.
My question always is why do you think this is important for the position you're hiring. Does knowing this question mean they're actually good for your position?
This is turning into the situation I've seen in places with serious entrance exams for universities. For example in Iran, a lot of not so talented but have great memorization and afforded to do mindless practice exams are making it into higher education while creative and talented and less fortunate people are staying out.
There are entire businesses built around practicing algorithm questions now, this is not a good sign.
1. having seen the specific class of problem before and knowing, as you're writing that solution, to stop and switch to the class of solution you've seen before that would solve the problem more efficiently, or
2. finishing the obvious, poorly performing solution and then optimizing it like an real engineer would do. The problem is that there's not going to be enough time for this to occur in the interview session. The act of writing out the poorly performing solution will consume the entire session.
Therefore, the only way someone would have passed your interview question would have been if they had seen this class of problem before.
If someone fails to design anything more sophisticated than number 1 despite my guidance, or takes an unreasonable amount of time to implement it, that’s a signal.
Also, let’s keep in mind a hiring recommendation isn’t a judgment of a person’a abilities as an engineer, it’s a judgement of how badly we should be trying to hire them relative to other candidates. My LNH is a statement that the candidate is solid but not stellar enough to extend an offer to. If our hiring pool were restricted or we needed to hire more people my assessment would be accordingly softened.
Because whiteboard coding is stressful and hard. I still kick myself for almost failing to get a basic sorting question right back in 2009, because the interviewer disguised it as a question about horse racing and it was interview 8 at the end of the day. (I still ended up getting an offer, but I turned it down.)
How many people in the real world sit around and practice dynamic programming questions all day?? The answer is ZERO!
You will surprised how many people as a matter of fact actually do this.
In fact for a lot of people the whole purpose of a day job is to pay them salaries so that practice interview questions to hop on the next jobs.
The bad news is many companies think these sort of puzzle solving skills are penultimate level of software engineering skills and pay top salaries, so these people don't even worry about being bad at their current jobs.
Do these for a few years, and pad big brands to your resume and then you are automatically considered something special and qualified for big title promotions.
It's that last one that I think algorithms/white-board coding entirely fails to see the trees for the forest. You would think as an industry that seems to lean heavily towards introverts and people in various places on the autism and social disorder spectrums, that the industry would not rely so much on high-pressure inter-personal communication scenarios for interviewing.
Which is not to say that soft skills don't matter: they absolutely do, and most industries their job interviews are much more highly focused on soft skills. The point is that you are testing soft and hard skills together in a highly charged mix.
If I want to sit down and play with an algorithms problem, I'd probably like to do it in a quiet room with no one watching/looking over my shoulder, and if I'm writing anything for most of the thought time it's scribbles and doodles, not algorithm-appropriate diagrams. "Programmer's Tourette's" of a sort imply that I'd probably be swearing at it for a while as I work to make sense of it. Asking a complicated algorithms question in a whiteboard scenario requires me to "play-act" a more linear string of thoughts, which diagram nicely, than I would use in an actual puzzle situation, while trying to be personal/presentable/well-spoken. I can certainly do that, but that mix of social skills and problem solving skills is very rarely needed in real life where we mostly compartmentalize such things to meetings versus coding time.
Then add in the ticking clock anxiety, that I don't feel like I have time to breathe, much less patiently tease out a solution to the problem.
Then add in the exhaustions of jet lag and trying to do all of that for 8 hours.
I feel like a lot of these sorts of questions, I could solve the problem rather well on my own time, or I could be a great, sociable, and presentable candidate with smart thoughts but maybe not immediate solutions. You want to the test for the former, but present only situations where the latter works well.
I feel like I'm not far from a baseline human on inter-personal skills, and even am somewhat more extrovert than the average programmer, and knowing that I have problems doing "both" the soft and hard skills for an eight hour interview day, I sometimes can't imagine how anyone in this industry gets hired because it's almost like we've optimized interviews to be intentional hells for programmers by trying to test hard skills in high pressure soft skills environments.
I very much believe that the technical interview culture as it exists today meets the definition of hazing [1], and that one day the industry will look back on it and wonder what was it thinking.
The worst part about this is if you get the first attempt wrong. Then you have very little time to start again and go to a working solution.
By then your anxiety begins to multiply.
My interviewer offered suggestions. Finally I described memoizing it (can be done with 2 lines in Python with a dictionary) though he was more interested in how to do it without extra space by utilizing a BFS that uses the input list as a queue. Then he ran off for another meeting.
I presume it's Google and Facebook's extremely high hiring bar that you're attributing to elitism? Let me attempt to reframe that for you in a way that I hope will let you let go of some of the anger I'm picking up on:
There's no denying that Google and Facebook target top-tier institutions and put their candidates through hell. However, I don't attribute this to elitism. I personally got my start at a less-than-stellar CS program, and I go out of my way to recruit there as an alum. I've detected no elitism from any recruiters, interviewers, or hiring managers, and I've seen a number of people hired as interns and full time engineers as a direct result of my outreach. If Google were as elitist an organization as you seem to think, I and the people I've helped get hired would never have had a chance.
So then what explains the high bar? Simple necessity. I can't share details, but the number of applications we receive for every opening is staggering. What's more, when we approach people in industry and academia, we see a high rate of interest. The blunt truth is that we are more selective about hiring because we can be. When a hundred people (not real figures) apply for each available posting and your hiring pipeline is staffed well enough to interview all of them, you'd better believe you're going to hire the best one in that pool. This isn't a Google thing, this isn't a Facebook thing, this is a rational actor thing.
So no, I don't think you're stupid for coming up with a suboptimal solution, I have no reason to think you're a bad engineer, and I wouldn't reject you because your background. However, given a pool of candidates of whom some got as far as solution 3 and some got as far as solution 1, I'm going to more enthusiastically recommend hiring the ones who got solution 3.
Yes and no. It's that I'm inferior and stupid for being at a lower tier company than at Facebook or Google. I can see it in every condescending hiring post about how easy it is to pass interviews without seeing similar problems before, switch companies and save for retirement and how nice it is to work at a company that treats you like an ubermensch.
>I've detected no elitism from any recruiters, interviewers, or hiring managers, and I've seen a number of people hired as interns and full time engineers as a direct result of my outreach.
I have absolutely heard of individuals from top tier schools getting easy questions while I got tougher ones, cases where people from top programs and other top companies (like Facebook) getting the benefit of a doubt in borderline situations, etc.
In some ways its even worse than at Facebook, at least at Facebook there isn't a hiring committee after a team match like there is at Google now.
Sometimes interviewers will respond to questions about the question. Others will only repeat the question as-stated. With the latter, I'd be sunk.
Pólya's first principle.
can you post a link to this solution? sounds cool.
edit: lol i just realized this is simply multiplying the adjacency matrix and what you mean by binary decomposition of numbers is just exponentiation by squaring. it's funny now that i realized i'll probably never figure out the dp solution.
edit2: got it. number of length n paths for some key u is sum of n-1 paths across "knight neighbors" of u. base case is length 1 path which is just # of neighbors.
it's funny this problem is designed in a particular way. using the keypad instead of a chessboard lets you write down the graph by hand rather than actually procedurally generating it (which is awkward with lots of literal edge conditions to check).
long moves(int start = 1, int len) {
assert(len > 0);
long[] cur = new long[10];
for (int i = 0; i < 10; i++) {
cur[i] = 1;
}
long[] nxt = new long[10];
while (len-- > 0) {
nxt[0] = cur[4] + cur[6];
nxt[1] = cur[8] + cur[6];
nxt[2] = cur[7] + cur[9];
nxt[3] = cur[4] + cur[8];
nxt[4] = cur[3] + cur[9] + cur[0];
nxt[5] = 0;
nxt[6] = cur[1] + cur[7] + cur[0];
nxt[7] = cur[2] + cur[6];
nxt[8] = cur[1] + cur[3];
nxt[9] = cur[4] + cur[2];
for (int i = 0; i < 10; i++) {
cur[i] = nxt[i];
}
}
return cur[start];
}I'm still going to consider myself a pretty good coder. Perhaps not Google material, but pretty damn good still. :)
Personally I find that I can get a lot more useful signal from simple practical problems (eg "take a .txt file as input, modify all the words which contain the letter 'q' to be uppercase, write the results to a new file") which have a lot of room for expansion (What if we instead want to capitalise each word where the word after it contains a 'q'? What if we only want to modify the third instance of each word? What if the .txt file is too large for RAM? What if a single 'word' is too large for ram and the letter q is right at the end of the word?) -- starting out with something that any programmer should be able to solve in one or two minutes, and then cranking up the difficulty; adding in bits where a strong algorithmic coder has an opportunity to come up with a more efficient solution, but it isn't just a binary "has the candidate memorised the appropriate algorithm yes/no?".
(Example question made up off the top of my head because NDA, I haven't actually given much throught as to if it's a good question or not, just giving an example of "question which starts simple and then you can add complexity on top")
As someone with access to the entire canon of Google interview questions, I've gone through the 20 or 30 with the highest rating, and none of them are ridiculously hard. The general pattern is either 1. a coding problem, meaning a relatively easy algorithm with plenty of opportunities to screw up the implementation so we can see how well you code and how well you catch your own errors, test your code, etc and 2. an algorithms problem that's really just a dressed-up version of some basic algorithm like BFS or dynamic programming so we can see if you can make the leap from theory to application.
Obviously I'm at an advantage here because I've seen most of the questions in use today, but whenever I encounter a new one I can intuit what's being asked and what it'll take to solve. I'm sure other companies have different sorts of questions that optimize for different things, but for our questions once you do enough of them you can sort of do any of them.
--
By the way, in my experience, those seem to be the biggest pitfalls for both job candidates at Google and programmers I meet in the real world. Sure, you crammed algorithms before you came here, but can you apply them in any real-world way? Sure you know your web/mobile app framework back to front, but will you hit a wall when asked to do something novel? Sure you can write a for loop to iterate over a data set, but will you fall on your face when that data set is petabytes in size?
I've become good at Google's questions because they generally test for those two things: nitty-gritty coding skills and an ability to generalize basic algorithms. The best candidates are those who know their algorithms inside and out, have the ability to break down and transform a problem until they can apply something in their toolkit, and have the coding chops to translate their concept into an implementation. All skills which, you may notice, make for a good engineer.
If you've ever wondered why we still do whiteboard interviews, that's why. Except you can use a chromebook now if you prefer, but you get the point.
I also asked a question in HN yesterday. It looks like there are more questions on data structure and algorithm for big data. However, books I read don't focus much in this area. As I haven't worked on big data before, that would also be a challenge for me.
* You obviously need more than one machine to do computation. Things become more difficult as you go from one machine to many, so learn about parallel programming tactics like MapReduce[1] and Flume[2].
* Storing stuff is also much more difficult. You'll either be working with distributed filesystems like GFS [3] or Colossus [4], NoSQL databases like bigtable [5], or SQL-like databases like Spanner [6] and F1 [7]
* Algorithms are tricky, because things that take no time at all on a single machine get to be very difficult when done on multiple machines. I don't actually know of any resources on this one, but if you know the algorithms and learn distribution tactics like I outlined above, it should make more and more sense with practice.
* Finally, you need to know your operating systems and networks. What operations are cheap (RAM access, local disk access, most local computation, same-cluster network operations, streaming remote disk access) and what operations are expensive (longer network hops, random-access remote disk operations). You also should be able to ballpark (to an order of magnitude) things like latencies of operations, dataset sizes, QPS's per machine, etc.
Also, when reading the papers, pay more attention to the interface than the implementation. One of the hardest things is transitioning from being spoiled by the local OS interface, where everything is cheap, to the distributed world, where seemingly random things are expensive or impossible.
[1] https://static.googleusercontent.com/media/research.google.c...
[2] https://ai.google/research/pubs/pub35650
[3] https://static.googleusercontent.com/media/research.google.c...
[4] https://www.systutorials.com/3202/colossus-successor-to-goog...
[5] https://static.googleusercontent.com/media/research.google.c...
[6] https://static.googleusercontent.com/media/research.google.c...
[7] https://static.googleusercontent.com/media/research.google.c...
Perhaps the answer is that there is no systematic interviewing system that actually works well. It seems like trying to create one was the origin of all this pain, and the cargo-culting by companies that don't need a systematic process has amplified it.
Interviewing is an inherently social, inherently subjective process. Such things are highly resistant to systematic approaches.
I understand what you are trying to say here. But how many candidates are capable of inventing path breaking algorithms in 45 minutes, just to crack a job interview? I guess only a countable people in the world could achieve a feat that amazing, where they could invent a totally new novel algorithms from the scratch in 45 minutes. If I'm not wrong the very people who invented these algorithms went through years of research to publish them.
Now if you are not testing this, and just testing if the person knows an existing algorithm. Then really this a scaled version of testing the ability to memorize multiplication tables.
There is nothing novel in merely knowing an algorithm. And you also have not tested a person's ability in inventing an algorithm either.
I keep hearing, how startups use multiple online judge algorithm screening sessions, to filter and hire the best. But the candidates just can't do any real world work, because they are busy practicing interview questions for the next job they seek while they are in their current jobs.
In other words you are optimizing to hire people who are good at clearing interviews, not doing their day job- Because they have to be bad enough at day jobs, as they have to be practicing these algo questions all day to clear your interviews.
for whom? who is the intended audience of your response?
The goal of this is too test whether the interviewee can recognize that this is a case to apply this algorithm in. It pattern recognition, not memorization, that is being tested here.
Whether that is particularly useful is of course the million dollar question.
That's the easy part. Everyone knows if you have sort a large data set, then you partition it in someway. Searching a huge data set requires building a tree on some criteria before hand and eliminating whole branches at every node. Or that they have to use a graph algorithm to figure out shortest paths and cost associated with the paths. Or that if you face a situation where you recompute many results you memoize. Or that writing nested for loops is a very bad idea. These are easy things to spot.
But they won't clear you in the interview if you don't get the mechanics right. Knowing BST helps in sorting doesn't cut it. They want you tell them how you would traverse across a tree in some 'level ordered' fashion. Or list different ways you could order a graph and list the exact heuristic. From here on this is pure memorization.
There is huge difference between inventing a new framework of thought even at an abstract level, and knowing the precise mechanics of balancing a tree.
I strongly disagree with the assertion that you get no useful information from an unsolved problem. The goal of giving a candidate a problem should not be to have them solve it. The goal should be to learn how they approach a problem, think it through, and work on solving it. Actually coming up with a solution is the least important part.
As an interviewer I've intentionally given people problems that would take more time than they have. I'm always upfront about it, making sure they know they may not solve it and that they should get as far as possible while explaining their choices.
As an interviewee I've been dinged for not solving problems. The reason why was because I spent most of my time talking through my approach and planning how I'd solve it. Without proper planning you get sloppy code, technical debt, and miss deadlines. Planning seems to be greatly undervalued in tech, especially in small startups.
What are your experiences with this? I've thought about doing this but decided against it because I figure the candidate's anxiety and stress levels are already high enough without the knowledge that they've been given a problem that's impossible for them to solve.
I mean, I guess, but in the many hiring discussions I've been on I found that the interviewers who asked those questions and based their feedback on them had very noisy signals. They frequently gave "lean no hire" feedback on our best hires. The interviewers who actually asked questions relevant to the work had much better signals.
The ones I had at my FB interviews are questions I would describe as "any competent engineer should be able to solve most of these in an interview slot" sort of questions — Simple data structures (sometimes explicit, sometimes implicit as part of the problem statement), simple strategies (breadth first, depth first), and a basic understanding of time (and space!) complexity.
Of course, you can hike up the difficulty a tonne (e.g. by replacing plain binary trees with red/black trees) and progressively fewer people will be able to solve those, but in my experience that's not common in an interview environment at FB.
Ultimately, the fact that the interview process includes whiteboard questions means that people at those companies _do_ perform decently (for some definition of decently) at those problems — that's how people are selected.
The speed required makes me skeptical many people can solve these problems in the required time without luck of having seen similar problems before.
The hire rate is also super low at the majors so it could have also been noise.
One of them did tell me this after his round (said we got further than he thought we would), the other one explicitly said my solution was optimal and what he was looking for.
The 2 questions per interview "rule" is an open secret now among people that have interviewed there. I've never heard of someone who only answered 1 per round get a follow up or an offer.
*Also, they generally don't move onto a second question if they don't think the first one was good enough.
I don't actually mind doing whiteboard interviews even on minimal prep. I've gotten a few of the "flagship" company offers and failed a few. I think part of it is internalising that nothing is going to guarantee you anything. You can always hit a question you bomb on and have an interviewer that will move on or bury you for it.
Phone screens are 2-4 questions and on-sites can add another 6-10. A 5% bomb rate for an on-site question will put you into the 60-70% pass rate.
I'm confident that if I do all the interviews I'll land atleast one offer but if you're putting all your eggs in one basket you're going to have a rough go of it.
I'm not sure I follow the math here, can you expand a little?
But if you do even two interviews your chance at getting one offer jumps to 1-.4^2 thru 1-.3^2 (84-91%).
(Am I out of practice? Did I do that wrong?) -- I tapped out painful on my phone.
My point was addressing the frustration with whiteboard interviews. It sucks to feel qualified and still get rejected. That doesn't necessarily mean they all way outclass you (they might!). If you treat interviewing like applying to colleges (3 or 4 big schools, a few backups) you're going to be a lot less burned by the system.
Sure, hate the system. But we've covered blaming the interviews. But that's not helping anyone right now.
As to the model, in my experience if you do sufficiently poorly on one and leave any doubt on another no one interview will save you. Sure you could add in the probability of failing two vs one. But that's numerically the same as just making that .95 a .9. It's a made up number, so what. The conclusion is kinda the same: doing pretty well can still lead to a failure for any given job, but you can still do pretty well in your job hunt.
I cant really judge, I would be hapy to have received this on an interview cause I've seen a variation of the problem on leetcode.
I just went through the interview loops at several FANGS, firs time doing this and got several offers, including G. I used to be super scared of even applying for fear of rejection because I thought I wasn't smart enough. I am self taught with lib arts degree from an average school, low gpa.
but I actually enjoyed learning these problems and figuring out solutions, and as time went on it got easier and easier. I enjoyed the interview process and had a good experience everywhere except FB.
my suggestion to those who are striving for FANG is just to keep practicing the questions and try to have fun with it, and go into the interviews with a positive, collaborative attitude.
The output for an index i was the product of the full input sequence excluding the element at i in the input.
The followup question was how do you do it in linear time.
I don't know how questions are created and filtered for interviews.
[1] https://en.wikipedia.org/wiki/Closest_pair_of_points_problem
This has the nice property of acting like a fizzbuzz and a sample of how do I work on hard problems stage. The first part is pretty pass fail the second is observational. This unfortunately requires a better thoughtful proctor which isn't always the case.
If I had a candidate that couldn't do the (n^2)/2 solution that's pretty bad. It's nested fors, man. Bang out in like 10 lines.
Still though, I agree, not great.
However, you probably wanted to know if that means that they would all get back in if re-interviewed, and the answer is no. Google is famous for tolerating huge numbers of false negatives in exchange for a small reduction in false positives. So, by definition, many would fail, even if they are capable Google engineers.
When I interviewed, I knew nothing of this process. Which was probably good, it would have made me a lot more nervous if I had know what lottery I was about to enter. In fact, I was pretty arrogant, seeing that typical questions were "just CS", and thinking my CS knowledge was pretty solid, I didn't even do any prep work. So I was probably pretty lucky to get in.
My own assessment of the 5 interviews I had were that 3 of them went very well. 1 went so-so (the interviewer assumed I was a webdev and ask me all sorts of specific server balancing questions, whereas I have worked mostly on compilers and game engines.. I managed to do ok-ish since I do know distributed systems). The final one I felt went badly since there I actually didn't manage to solve the problem the interviewer asked (it was one of those more puzzle-y questions), but I guess I somehow did ok, since I did what you're supposed to do in such a situation: show that you're a good communicator and problem solver even when you don't know the answer.
I was dissapointed in all these interviews since I was hoping for interesting questions specific to me (how did you implement this type inference algorithm?) which never came.
Of all the interviews I've conducted for Google since, I've only had a 1:40 ratio of seeing people being accepted, even though plenty seemed highly capable to me. Usually some other interviewer didn't have quite as good a time with them as I did. You really need to make all of them happy to pass.
To other answers that joke that these interviews are the hardest thing you'll do at Google, I'd like to disagree. At least in the teams I've worked, I've done things that thoroughly stretched my abilities, way beyond the level of interview questions. Of course they're of a very different nature, but that is the point: interview questions are very distilled, idealized, and problem solving in the real world is very messy, and to my mind at least, much more interesting.
edit: also worked for google, same story
edit2: I believe most people can learn to solve these problems because a lot of it is mixing and matching algorithms/techniques that you've practiced. It just takes time and practice and exposure to a wide variety of problems and crucially, confidence. I've seen people who somehow strongly believe that they're not the "algorithmic type" and will never be able to solve these even if they spend months working on it. :( I've tried and failed multiple times to convince those ppl that this is a very learnable skill.
I'd recommend that you only solve problems that are extremely easy, on websites like https://www.spoj.com or https://www.topcoder.com or old google code jam questions. Pick a single website (I recommend codejam) and do only the easy ones for a few months. It's hard to argue against the happiness that comes when your program passes the tests. The point is not to sharpen your skill but to get used to the feeling that your program passes ALL the tests cases.
If you get to a stage where you're completely sick and bored of easy problems, pick a slightly more difficult problem with basic algorithms like plain BFS or DFS. Try it for just a day or two and when you can't solve it, read the published solution. Try to understand it, apply it manually to the test cases and once you're sure that you've completely grasped the solution, implement it and see if it passes all the tests cases. Take it slowly, and return to easy problems often.
This could take you pretty far in terms of enjoying the process. :) At least that's how it worked with me -- I liked the high of getting a program "accepted".
Re-visit the ones you got wrong first. Try them again, repeat until you've gotten them all right (this might just be because you remember the solution from looking it up, that's fine, you'll have plenty of time to forget by the time we get back to it :).
Now, revisit the ones where you had the right data structure on the first go. HOW would that data structure help? Go a level deeper on actually trying to solve it.
I can't guarantee this will be fun, but it should be fast. A few minutes here on there on any given problem, going one level deeper each time you visit it.
Eventually you'll have the whole algorithm for one of the problems, likely using some common data structure like a hash map, tree, or heap.
Code it in a language with a good set of algorithmic primitives, use every tool the library gives you (don't worry about remembering how the data structures work on this pass). Hopefully with the whole algorithm in mind and all of the tools at your disposal, this is "just plumbing".
Rinse, repeat.
Somewhere in there, do the same with the complexity analysis (time and space!).
Next time, try it where you have to build the data structure by hand.
Then one day you'll see a problem not on your original list, and you'll immediately think "red-black tree with a hash table lookaside buffer, but I wouldn't want to have to build the RB tree by hand if they asked me to, so AVL tree because the complexity is the same and I can bang out the code like it's what I do every morning before breakfast".
Like I said, it might not be fun (at least at first), but it is a way to break up the practice into digestible chunks. Also it builds on the strategy that I've seen work best in interviews -- if you treat each step of iterative deepening of the solution as a point where you'd talk with the interviewer about what you're thinking and why, you give them a lot to go on about your thought process and a chance to course correct if you misunderstood the question or your heuristic for how to approach it simply came up wrong.
My approach is to keep writing the basic algorithm, data structure, common questions again and again. Do it once every 2-3 weeks. When I know every part of them, then I can start twisting or go deeper.
I am not that top talent. Sometimes even a 0-based or 1-based array can bug me a while.
They often don't which is why they shouldn't be used.
I know HN hates whiteboard problems, but just like anything, you get good with it if you're having fun solving them.
I ran into this too when I was preparing for a loop, especially for more complicated DP and recursion problems.
I found a website called gorecursion [0] on Reddit and he is very good at describing these solutions from the naive case to the optimized case very well. This helped me quite a bit, but I still didn't get the offer.
Disclaimer: I'm myself not very good at algorithmic puzzles. For a job application I took a vacation to train solving coding tasks, and was getting better every day. I got that job, but guess that for a Google application I'd rather have to train for 3 months.
We hate them for interviews because they're a terrible signal for hiring, they're often poorly administered, they're humiliating, they discriminate against introverts, and they've become frustratingly common.
They unfairly mess with people's livelihoods. It is a really big, life-altering issue for some people.
It was good of him to still post it but it showed that someone currently employed at Facebook would have been screened out at the phone call stage had he applied again without any preparation.
I'm consistently surprised by the fact that, despite hiring programmers who are the world's most elite, Google's products and services are just kind of ... plain/average/boring. The products and services are far less amazing than Google's engineers.
It's like Google takes in geniuses but outputs kind of boring, standard, average quality products and services with a surprising number of problems and deficiencies.
I worked with a guy, Bob, in our college computer room. Bob had returned to get his BS after many years in industry. He had great stories. He also had great advice. He taught me that you can learn a lot about how a company will treat their employees by paying attention to the way they treat you during the interview. He suggested several sign that indicated it was best to just "walk away".
If you go into a restaurant for a professional lunch meeting and they have a ball-pit / swing set /etc. it might not be the most professional place to hold the meeting. Just walk away.
If you go to a 5 star restaurant and they want you to wear a clown nose (Everybody Does It!) Just walk away.
The big scam is "We hire the best and the brightest". "We mandate a whiteboard test (Everybody Does It)". It is my opinion (based on experience) that companies that insist on a whiteboard test, despite years of programming on your resume and open source code, are either Ball-Pit companies (who don't know what it means to be a professional) or Clown-Nose companies (who know what it means to be a professional but still treat you like a commodity). Just walk away.
When you object, please reference one study in a journal that shows that whiteboard tests are effective in any measure when used during interviews.
I understand why Google does it. I've even interviewed there. They get thousands of resumes (which they never read, at least nobody did at my interviews). They have to weed out the "learn coding in 6 weeks" crowd. But you're a professional. You should expect to be treated like one. You don't ask your surgeon to cut up hams in an interview. You don't ask your builder to nail two boards together. Professional accountants are not interviewd by bank tellers and ask to count change.
Google, like Microsoft before it (remember the "why are manholes round? quizes?"), have combined the marketing claim "We hire the best and brightest" with the ball-pit mentality of whiteboarding. Google HR (sorry, People Resource?) SHOULD be embarrassed but apparently they, and upper management, LIKE ball-pits.
A real professional interview involves a discussion about what the company does, what it current problems are (aka why are they hiring), and a discussion of if you, as a professional, have the skills to solve the problem. What do they need? How can you contribute? It is likely that your interviewer has no idea what you are being interviewed for and cannot answer these basic questions.
We, as professionals, should consider whiteboarding as an insult.
Just walk away.
Why would I ever want to hire someone incapable of demonstrating their skills in such a simple, straightforward way? If you can't solve a toy problem and explain your solution, or at least have a conversation about the constraints and tradeoffs as you work on it, how am I to imagine there is any chance you could be a productive teammate?
1) The whiteboard questions are unrelated to the job opening.
The interviewers have no idea why you are there. They don't know what your resume says. They don't know who you might be working for. They don't know what you might be working on. Would you hire someone to work for you without knowing if they were going to clean your house, install new lighting, or rebuild your kitchen? How exactly would you interview a person if you don't know why you need their skills? Or how their skills are related to the task? Asking a carpenter to "whiteboard" the steps to clean a bathtub during an interview is insulting.
2) The interview is being conducted by people who have almost no job experience.
My experience is that the interviewers are recent college graduates. And that the whiteboard questions are related to their data structures class. They are focused on details like worst-case behavior of the algorithm and whether you can quote the log-log-n asymtotic performance. This entirely ignores the fact that the actual behavior depends a lot on the actual measured performance. Take, for example, my paper on garbage collection (http://daly.axiom-developer.org/TimothyDaly_files/Bozm84.pdf) where the actual data access pattern matters. Theoretically strong algorithms usually exhibit bad behavior because of data access patterns, CPU caches, look-aside buffering, and/or branch prediction failures.
3) There is no known relation between being effective and being able to present information.
I know people who are strongly autistic, to the point of not making actual eye contact or giving any verbal feedback at all, appearing to be "not paying attention"... and then create beautifully crafted excellent code. I also know people who "talk a good game" and couldn't write a "hello world" page in html. Please point me to any study that shows that whiteboarding is an effective way to judge candidates. Even Google's HR head claims it is ineffective.
4) There is a ball-pit / clown nose aspect to the interview.
"Everybody does it" so wear the clown nose. I've had a fair number of interviews in my 48 year career. Most of them were with people who needed something done and I could demonstrate my ability to do that. Interviews exist for a reason. Asking me to whiteboard Knuth-Bendix because you're writing an editor is reasonable. But the same question for a customer service job would be nonsense.
These "clown-nose" interviews are simply insulting and a waste of time. Walk away.
With regard to your point #1, it's not that the questions themselves must necessarily be related to the specific job one is interviewing for; it is that the process of communicating about problems and collaborating in the investigation of potential solutions represents the core of the profession. I have no idea what you mean by "no known relation" in point #3; there certainly are niches in which someone capable of nothing more than writing code might be able to eke out a living, but for the most part software engineering consists of interpreting user needs and definitions of problems, investigating those problems sufficiently to derive specifics, designing solutions which make appropriately balanced trade-offs, and communicating plans and progress in order to ensure that the proposed solutions satisfy customer needs. Sure, there's also a little typing of code every now and then, but if that's all someone brings to the table their potential contribution is very limited.
I am not aware of any studies which provide any meaningful data about software interviewing practices; we are all guessing. I would take the complaints about the use of whiteboards and toy problems in technical interviews more seriously if the people making such arguments were able to present a superior alternative, but the proposals I've heard sound even more like your "clown-nose" concept than the system we're used to.
About your reply for point #1, I agree that communication and collaboration are important. I have picked up chalk (I'm old) during an interview in order to draw diagrams related to robot paths. But you'll note that I decided that the chalk-talk was an effective way to communicate essentially visual information. A "whiteboard" interview is one where the interviewer decides that I need to use a whiteboard to communicate. Coding is not a whiteboard activity and the medium choice is inappropriate. I rarely choose to communicate algorithms with an interpretive dance for that very reason.
About your reply to point #3, in any large company it is highly unlikely that a single, new-hire person would have such a broad scope of activity. Hiring a person of that scope would cause me to invest in background checks and presentations by the person showing their prior projects, designs, and outcomes. I certainly would learn nothing by asking them to reverse a tree on a whiteboard in 20 minutes.
As to your final point, I did present a superior alternative. Have the hiring manager talk to the person about the job opening and the skills expected. Ask the person to provide related background information from their prior experience. Ask them about how they might appoach a current or previous problem related to the job opening. If THEY want to use the chalkboard to communicate that's fine.
An interview tells you a lot about a company and how it treats employees. If you see a "sea of desks" in a supermarket-sized open-plan floor you can assume you're "just another ball in the ball-pit". If they hold meetings in a fisherman's net strung from the ceiling (I wish I made that up, but no...) then you can assume they have a playground mentality. If they are proud of their "80 hour weeks" you can assume your pay rate is only half what it claims. If "free food" is given as the best reason to work there, you can assume the work is painful and boring. And, to the original point, if the interview process resembles a frat-house hazing-style "paddle line" of unrelated interviews, you can assume a frat-house "good culture fit" mentality. Every frat house strives for a monoculture (as in, "we only hire the best and the brightest").
But if you're a professional, working every day to improve your skills and breadth of knowledge and experience, then respect yourself. Walk away.
Walk away.
Also, solving them in an interview is radically different from solving them for fun.
... sure
I don't like large corps, period.
Even if there were, algorithm tests on whiteboards would be a poor test, because they also involve prior knowledge of the task and a very specific type of intelligence.
In my experience, social intelligence is a better predictor of success in any workplace, anyway.
and then you type:
"In my experience, social intelligence is a better predictor of success"
Something tells me you don't work at google :D