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...
I guess that would be a trick-question then, as nobody ever solved an NP-hard problem in linearithmic time.
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.
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.
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
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.
https://www.nctm.org/Publications/Teaching-Children-Mathemat...
https://en.wikipedia.org/wiki/H._Christopher_Longuet-Higgins
What is a good way to learn more about these?
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!
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.
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?
[1] https://lintool.github.io/bigdata-2018w/slides/didp-part02b....
[2] https://lintool.github.io/bigdata-2018w/slides/didp-part09b....
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.
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.
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.
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.
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.
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.