2 ms·
It's quite common at the major companies to ask a question where the true solution is NP-whatever, but for which a "trick approximation" can get you nlogn solut
by dekhn 10y ago
It's quite common at the major companies to ask a question where the true solution is NP-whatever, but for which a "trick approximation" can get you nlogn solution. If you know the trick, it's easy. If you don't know the trick and figure it out in 30 minutes, you're a genius. If you don't know the trick and don't figure it out in 30 minutes, the interviewer knows nothing at all abiout your ability to contribute to the company.