views:

1039

answers:

14

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)

+10  A: 

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.

Parappa
Really? The matrix example he pointed to is obviously equivalent to calculating a traveling salesman tour so it must be NP-complete :P
Ben S
@Ben S, between you *feel* the problem is NPc and you *prove* it is one ten to infinity minutes may pass.
Pavel Shved
@Ben S: If it is obviously equivalent to TSP, then I'm more sluggish from lunch than I thought. I don't even see an obvious mapping from the matrix problem solution to a TSP solution. If you were being humorous in that remark, well, it didn't translate well into the Internet.
David Thornley
I believe it's obviously equivalent to the lazy, opportunistic traveling salesman problem. Where the salesman can skip cities, and the costs of travel can be negative (perhaps because Vegas is on route? Or visiting illegitimate children?) Of course, I just made that problem up. But, it's clearly NP-hard - I'm just too lazy and opportunistic to type up the proof right now.
RD1
+1  A: 

No, it's rude and a sign that the interviewer just likes being in a position of power. Haha, peon! I know the answer, and you don't! And boy, do I love to make you squirm trying to come up with it!

About the only way it could be even slightly valid as a useful interview question is if it were a well-known question or one that was somehow obviously NP-complete, and asked in a way that encouraged discussion of feasibility.

Brian Schroth
Or I suppose it could be viable if an extremely important qualification for the job at hand was "how well does the applicant put up with unreasonable requests while under pressure".
Brian Schroth
I don't think so. This kind of question lets you see how the interviewee reacts to problems he isn't used to solving. It also lets you see if they're comfortable asking for more information if they need it.
Ben S
You can do both of these things without asking to solve an NP-complete problem. Asking them to do so is great, however, if you want to see how they react to problems they're not used to, to see if they're comfortable asking for more information, *and to be a jackass*.
Brian Schroth
Er, so according to you, the interviewer should not ask questions that he knows the answers to and the interviewee doesn't? (NP-hard problems do sometimes/often turn up in practice in non-obvious forms.)
ShreevatsaR
It's not rude. The interviewer gets to see how the candidate analyzes the question, what approaches he tries (dynamic programming etc.) and how he finds that they won't work in this case. Also, there are always approximate solutions using sampling etc.
Brian -- Many NP-complete problems are *not*hard*to*solve*. The clique problem (Given a graph and an integer k, are there k vertices in the graph which are all adjacent to each other?) is very easy to solve; I'd have no problems asking it as a ten-minute algorithm interview question. The difficulty is not in creating an algorithm for them; the difficulty is finding an algorithm that runs in polynomial time.
Chip Uni
But any decent programmer isn't going to consider a polynomial time solution to be much of a solution at all. So they can come up with a solution, then discount it because it's too slow. Then struggle to come up with the non-existent fast solution. All the while the interviewer can cackle because he knows it's impossible to solve with a solution that isn't slow. Interviews should be about evaluating the applicant, not satisfying the interviewers intellectual sadism.
Brian Schroth
A: 

If such a question was given before an interview(to be answered at an interview) I would say it's ok.. but to just solve such a difficult problem as that on the spot is definitely not going to be done well by any programmer, and if the programmer does do it well that just means they can act on the spot(which isn't always the best thing for programming as designing things needs to take time and check every possible flaw) or that they have seen a similar problem before.

Edit: Or possibly discussion about the problem would be good, like say laying down a plan of action whether or not you completely solve it.. and discussing how feasible and if there is a fast(but difficult) way to do it and such. I would not say that the interviewee should have to write down over 50 lines of C code in an interview to solve it though

Earlz
+8  A: 

Sure, why not? NP-complete doesn't mean unsolvable, it just means your solution will be slow. You may be looking to see if the candidate will choose the brute-force solution, or try a dynamic programming solution. And this type of question can lead into questions about runtime and other useful theory.

tloach
+3  A: 

I don't see a problem with this, but I do somewhat question the usefulness of these sorts of questions in interviews in general.

The benefit of asking questions like this, as an interviewer, is see how the person approaches a problem, and how they think. If you tell them to talk it out, you can find out quite a bit about how they will approach a difficult problem.

That being said, during an interview, most people aren't at their best - so throwing something that's somewhat "tricky" like this is often overkill, IMO.

Reed Copsey
+11  A: 

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.

antti.huima
"provide a sketch of reduction to a known NP-hard problem" — note that you need a reduction *from* an NP-hard problem, not *to* an NP-hard problem (which is usually all too easy).
ShreevatsaR
Providing a sketch of a reduction to a known NP-complete problem is frequently difficult. How much time do you want to spend on one question, and how much weight do you want to put on whether somebody has a batch of NP-complete questions in ready memory and can come up with a proof sketch during an interview?
David Thornley
@David ShreevatsaR You are right, I'll edit and fix
antti.huima
+3  A: 

I think it's valid to ask a question you know the interviewee won't know the answer to.

Everyone encounters problems they don't know the answer to. This type of question will give you insight as to what the interviewee's internal process is. If they logically conclude things and start to formulate a correct answer, even if it's not the best dynamic programming algorithm for it, it shows that they can reason well and discover an answer.

Also, since they likely don't know everything about the problem, this sort of question lets you see how comfortable the interviewee is with asking for help or clarification.

I think the best way to answer this type of question is to ask for any clarifications if something is missing or not well known, and then postulate an answer, pointing out why you think it is correct, and why it likely isn't the best solution.

Ben S
Not quite the same, but a colleague who tried for her B.Sc. in Computer Science was asked in her freshman intro course to compute the 4th Ackermann Number (<http://en.wikipedia.org/wiki/Ackermann_function>). It's beyond current hardware, so she failed and not long after gave up CompSci in frustration. That may have been intended, and depending on how you look at it, that may have been a good outcome.
Carl Smotricz
@Carl: I think this illustrates the difference between asking for the impossible ("compute the fourth Ackermann number"), and merely asking a problem with no solution that scales well, ("give an algorithm for computing the Ackermann numbers"). Solving an NP-complete problem might be very easy (by exhaustive search, for instance). It's when the input size changes or isn't specified, that you hit panic stations.
Steve Jessop
Everyone keeps talking about a dynamic-programming solution to this matrix problem, but nobody gives the solution. It doesn't seem like a DP problem to me.
PeterAllenWebb
@Peter: This answer: http://stackoverflow.com/questions/1720737/from-an-interview-removing-rows-and-columns-in-an-nn-matrix-to-maximize-the-sum/1721084#1721084 is a dynamic programming solution.
Ben S
+6  A: 

There's a category of interview questions that are illegal in some countries, usually pertaining to personal details that are none of the employer's business. That aside, any question is fair game if the interviewer feels it'll help get an idea of the interviewee's capabilities!

If you're hiring for a position that calls for a thinker rather than just a code monkey, it may be useful to throw this kind of problem at the applicant. Who cares if a problem is "well known" to be NP? If the guy is good he'll come to that understanding in analyzing the problem. That may well be the result the interviewer wants to see, or the applicant can go on to do some more pre-analysis and describe how he'd brute-force the problem, or what optimizations he can think to apply to make it more manageable.

Carl Smotricz
There is a problem with NPc problems: their NP-completeness takes much time to be proven. How long should the interview be then?
Pavel Shved
@Pavel: I completely agree, I for one have worked on proving several NP-complete problems and most of them take me a couple hours at best to reduce, some take days of pondering. I think most people that answer "yes its fine to ask any question" probably haven't had to do difficult reductions before.
ldog
But then it would only be a problem if the proof was necessary, the employer may simply expect a 'this seems to be NP' and then have a discussion with you.
Matthieu M.
This depends on where the interview is. For top labs or universities, I'd expect to gain points by going to the whiteboard and trying to sketch a proof if that seemed the most interesting aspect of the question. I would first outline heuristic solutions though and make sure I asked them to stop me - but usually that's not an issue.I agree sometimes these can take a long time (or forever), but I've certainly sketched promising reductions in a few minutes that worked out (from 3SAT often).Employers ask these questions to see your mind in action. Of course they want to do this!
RD1
@ Pavel, gmatt: I think you're demolishing a strawman. Nobody will expect you to provide a complete and polished proof of NPc-ness. Thus, talking about the hours this should take is pointless. However, for a qualified job, your interviewer can well expect you to consider and at least intuitively recognize such a case. There are entire classes of jobs where this ability is essential, even though many of those jobs will never (not just not in the interview) expect a formal proof.
Carl Smotricz
+2  A: 

It's sort of mean to ask nigh-impossible questions without informing the interviewee of it, but in observed problem solving, the question is often asked so that you may demonstrate critical thinking skills, how you approach problem solving, and how you handle pressure or failure.

I've been asked interview questions I couldn't solve, and I don't think I've ever "failed" an interview because of it.

Matt Garrison
Good comment, but I'd note that NP-complete does *not* equal nigh-impossible. It's absolutely possible to come up with solutions to NP-complete problems; it's just that they won't *scale*. If the interviewer specifically asks for an algorithm that will handle large instances of the problem, though, well, yeah, that *is* mean...
itowlson
Yeah, I should have phrased that better. In the scope of a typical software developer interview, they're nigh-impossible. Time constraints and pressure to perform would prevent most people from solving it. Even in interviews, I usually got the vibe that the questions were more about revealing character and spurring computer science discussion than getting an answer. Or maybe I just compensated for failure with charisma :)
Matt Garrison
A: 

That is evil!

If the interviewer asks an NP-complete question in an interviewer the only response they can reasonably expect is that the interviewee respond with a proof that the problem is NP-complete. In a low-stress environment like a university homework question, this usually takes a bright student 2-3 or more hours to prove. The proof itself can take several pages to write out completely, perhaps several hours of work itself. In a high-stress environment like an interview you can expect that the interviewee may not even recognize that this is np-complete.

The only reasonable alternative is that the interviewee produce an approximation algorithm; however, in this case the interviewer should make it explicitly clear that they are fine with approximations.

Even so, most approximations only come with an order of 2 of the correct answer.

I guess there is 1 more alternative: the interviewee suggests that a search-type algorithm maybe the most suitable (take for example the integer-domain optimization problem which is NP-complete, most approximation algorithms use a branch and bound search spin on the simplex algorithm to produce decent results.)

ldog
Or the interviewee could just, you know, solve the problem with a slow algorithm. A lot of NP-complete problems have fairly simple solutions, they just have horrible run-time.
tloach
I think in the case where the interviewer would be willing to accept a trivial algorithm they should specify so. "Horrible runtime" is an understatement at best, most trivial algorithms would require roughly about the same time as it takes for the universe to be created and destroyed before they complete for even reasonably small input sizes.
ldog
"A lot of NP-complete problems have fairly simple solutions". All NP problems have a very simple solution (assuming that the polynomial verification algorithm is given): brute force. The question wasn't, "is it OK for an interviewer to give you an NP-C problem and then complain that the solution is slow", the question was, "is it OK for an interviewer to give you an NP-C problem".
Steve Jessop
+2  A: 

Is it fair to ask in an interview how to factorise numbers?

That's not known to be NP-C, but no polynomial-time solution[*] is known, so it is certainly not known to be in P.

I think the answer to both my question, and the original question, is "yes", and for the same reasons. Some problems have no solution which scales well, but do need to be solved anyway for certain inputs. If you need programmers who can handle such problems, there's a good way to let them prove it in interview, and that's to pitch them one and see whether they freak out.

If someone claims a CompSci background, then they should even be able to provide good solutions to certain NP-C problems on demand, such as solving the knapsack problem with dynamic programming. I would consider it pointless asking an applicant for a programming job to take a problem they've never seen before, and actually prove it NP-complete (for example by reducing knapsack to the specified problem). You don't need very many programmers per company who can do that (usually 0), and all you'll likely discover is how long the candidate keeps at it before attempting to change the subject and do something more valuable with the interview time...

[*] polynomial in the size of the input in bits, that is. You often see people discussing algorithmic complexity of integer problems like factorisation in terms of the size of the number represented by the input, e.g. "sqrt(N) trial divisions". But that's not how NP and NP-C are defined.

Steve Jessop
Having a CompSci background, I don't offhand remember how to solve the knapsack problem with dynamic programming. I know where I could look it up fast, and that's normally enough for all practical purposes except answering interview questions.
David Thornley
Yes, I should perhaps have said a *recent* CompSci background. I solved knapsack at Uni, c.10 years ago, in a maths degree. I'm pretty sure I could describe the algorithm from memory, with a few errors, but I sure couldn't rattle off the code. For almost any particular algorithm one could say, "I don't remember the details, but it's in Knuth". But an interviewer is going to want to see evidence that I do *know* at least one algorithm. So: is dynamic programming something I ought to be able to reproduce it on demand, like I can reproduce a binary search on demand? Depends on the job and my CV.
Steve Jessop
Similarly, I suck at whiteboard code, because I never write it in real life. I usually program with a reference open for all but the most routine tasks. I still acknowledge the need to write code in interviews, I've just never had the guts to take my books with me ;-). If this means I end up saying, "um, at this point I'd look up the arguments to mmap" then, OK, I have to fall on the interviewer's mercy. Similarly, I'd expect someone who's studied the knapsack problem to give an outline how to solve it, if not all the details.
Steve Jessop
"I solved knapsack". btw that's brevity, not arrogance. I was taught to solve...
Steve Jessop
+3  A: 

It's good to ask a question that is hard to answer, to see how a programmer reasons through a problem.

But it all depends on how the interviewer asks the question, and prompts the programmer towards a solution if they aren't a mathematical genius (i.e. to see how they reason, and how they react to questions like "that's a good start, but what if...") rather than to detect if they are autistic and can provide an optimal solution in 4.3 seconds).

It's worth remembering that interviews are highly stressful affairs in which many people find such questions very difficult to answer well - a much simpler question will usually suffice without putting the interviewee under undue stress/pressure.

If you do it to deliberately try to see how they deal with stress is just stupid - that isn't the sort of stress a programmer has to deal with in their job, so you're not testing anything worthwhile.

Jason Williams
A: 

I prefer asking them to prove that P != NP or P == NP. Someday a candidate will answer it, I'll steal their answer and be famous!

On a more serious note, though, I think it's completely fair. Most NP complete problems are easy to solve, they just run very slowly. Unless the job requires them to know a lot about complexity theory, though, all they need to demonstrate is that they understand the solution will be slow. Bonus points if they know it's non-polynomial time, gold star if they know it's NP complete.

patros
It will take a complexity-theory-aware person several minutes to provide an easy solution to an NP-c problem, because brute-forcing will be the last he thinks about. Personally, under an interview stress I would even say that "I can't solve it", because a brute-force approach is too dumb to be a "solution".
Pavel Shved
Don’t forget the price you’ll get! http://www.claymath.org/millennium/
Gumbo
I've read first that you prefer to ask them to prove that P==NP :)
psihodelia
@psihodelia hah, that's actually what I meant. Brain fart.
patros
+1  A: 

There is nothing wrong with giving an NP-complete problem as a programming challenge during an interview. I only see something wrong with expecting to find a polynomial-time solution to the problem during the interview.

An interviewer should want to see how a candidate deals with a variety of situations -- including situations that the candidate can't find an easy solution to. "Impossible" questions show how the candidate reacts when there's no simple solution. Does the candidate just give up? How many different attempts does the candidate search? How far-reaching are the solutions tried? When does the candidate ask for help -- and how? Does the candidate complain that the problem "isn't fair"?

In short, such an interview question isn't about solving P=NP... it's a psychological answer.

Chip Uni