3 ms·
I should have said "n log n heuristic approximate solution" (my defense: I'm actually a biologist pretending to be a computer scientist). Many problem solution
by dekhn 8y ago
I should have said "n log n heuristic approximate solution" (my defense: I'm actually a biologist pretending to be a computer scientist).
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.
- amelius 8y agoBut I suppose appropriate heuristic solutions are typically only "pondered about" and not "found" at the whiteboard, because they require extensive testing with real-world data to see if they are actually efficient in practice.
- dekhn 8y agoUsually in situations like this the person asking the interview question already has already built the system in production that uses that heuristic and saw that it worked. with a good set of rules of thumb a smart person should be able to propose reasonable heuristic solutions that have a chance of working
- edanm 8y agoNo, that's not necessarily how it works. 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.
- deleted 8y ago[deleted]
- amelius 8y agoYes, that's simplifying the problem by making assumptions about the data. Except you often don't know what assumptions you can make. Better to check the assumptions using the data before devising an algorithm for the given type of data.
- edanm 8y agoI agree in principle. But imo in reality, what actually happens is: 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.