Menu
Today there was a question on SO, where the author was given an NP-complete problem during an interview and he obviously hadn't been told that it was one.
What is the purpose of asking such questions? What behavior does the interviewer expect when asking such things? Proof? Useful heuristics? And is it even legitimate to ask one if it's not a well-known NP-complete problem everyone should know about? (there's a plenty of them)
253
Closed-ended interview questions Often, they can be just a "yes" or "no," but you should give candidates an opportunity to explain themselves. These questions can help you quickly gain basic information about the job seeker.
Completely legitimate to me. If you are Computer Science professional there are good chances that you can either argument informally why the problem seems to be hard, or (even better) provide a sketch of reduction from a known NP-hard problem.
Many real world problems eventually turn out to be NP-hard, and stackoverflow also has now and then questions about the complexity of a problem which turns out to be a difficult one (NP-hard, for instance). It is an important part of a CS professionals toolbox to be able to recognize and to argue for problems which are known to be difficult to solve.
176
I don't see any problem with asking something like this. Also, programmers should NOT be expected to recognize NP-complete problems by rote. They should, however, be able to identify that their algorithm is potentially slow regardless of whether a given problem is NP-complete.
38
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
