3 ms·
Maybe it was a trick question. Maybe he was just supposed to respond that polynomial solution doesn't exist because this problem is np-complete. That's what th
by scotty79 10y ago
Maybe it was a trick question. Maybe he was just supposed to respond that polynomial solution doesn't exist because this problem is np-complete.
That's what the page he linked says about this problem. Solution he linked doesn't cover case with negative numbers and is at best pseudo-polynomial.
Or is the whole post just satiric bit about the state of recruitment?
- dekhn 10y agoIt'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.