> Here's an NP-hard problem you haven't heard of, write correct code for nlogn solution on whiteboard in language of choice
I guess that would be a trick-question then, as nobody ever solved an NP-hard problem in linearithmic time.
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.
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.