Of course it depends. Getting the ball rolling is probably not best done by giving an NP-complete problem (subset sum) as a first exercise.
When presented with an interview question, I usually say "well, it can be solved by doing $NAIVE_SOLUTION, just to get that out there, and I know you're looking for a better one." By doing this, I've established that there is a naive solution and that I'm going to spend time thinking of a better way. Unfortunately, with these kinds of algorithmic puzzle problems, it's usually a waste of time to give the naive solution in full detail, because no incremental development will ever make it monumentally better unless some cheap trick, like memoization, can be done.
> The interviewer most likely has allotted time for 2-5 of these questions in
> his interview
This is usually the case when the problems are easier. For example, "compute the square root of a number" where the solution is, for the most part, cut-and-dry. (Though I would never blame someone for taking longer if they have to re-do the calculus by hand to rediscover the solution.) FizzBuzz is another. Simple binary tree exercises are another.
As said, it entirely depends on the questions. To some interviewers, asking "how do you traverse a binary tree" on-site probably would be a waste of time; that is expected by a first-year CS student.
> It says that they want to make sure they hire somebody who's "a good fit" and
> the hiring pool is high enough that they can get away with false negatives.
This is the easy way to explain it, but I don't think it's a very good answer. I don't think someone is a good fit if 7 people across 8 hours couldn't come to a consensus. If there's that much controversy, what is another coding question going to tell?
> The fact that they talk about the business [...]
This isn't an issue. In fact, it's good to talk about the business and mechanics thereof. But spending half an hour preaching to an interviewee about why the product is so good from a consumer standpoint isn't the best way to capitalize on either person's time. I think, aside from a brief introduction, that propaganda should be disseminated when the interviewee asks questions about the product.
In addition to the above, I think it's a problem when the scales tip way in favor of talking about the product instead of the engineering. If the product gets a 30 minute talk and engineering gets a 5-10 minute talk, I think it's indicative about the priorities of the company toward its employees.
> "well, it can be solved by doing $NAIVE_SOLUTION, just to get that out there, and I know you're looking for a better one."
I'm at the very beginning of my career, having just accepted a new grad position, but I thought I'd offer my opinion on this: just implement the naive solution. If you're really unsure, ask them if they're OK with you doing that. In my very first interview I took the approach you just described and the interviewer actually stopped me as I was brainstorming other ideas and said, "Just work on the basic solution and we can talk about ways of improving it later." In subsequent interviews I've implemented the basic solution first then talked about the drawbacks of that approach with the interviewer, possible improvements that could be made, etc.
Now, most of the problems I was given were far simpler than what was described in the OP. I do think I was very fortunate to get interviewers who weren't just looking for an outside-the-box solution to some brainteaser they'd concocted. Nonetheless, I think it might be worth considering just taking the naive approach (and telling them what you're doing any why) rather than spending a lot of time trying to come up with a perfect solution.
I absolutely agree. As both an interviewee and interviewer I prefer this approach. There's nothing worse than having someone spend 5 minutes waffling or doing very little, then tell you they're going for the complex solution without having shown you the simple one.
Honestly, when I interview and ask a question like this, it's a leading question. I want the simple solution as a FizzBuzz style test of your abilities, then I'm going to ask "and what problems can you see with this solution?" and we'll go from there.
If they request I spell out the naive solution, I certainly oblige. But if it's clear to both the interviewer and me that they are looking for that particular solution, then I won't spend time writing it out. So far, this approach of assuming they want the best solution—while acknowledging the simple solution exists along with a brief sketch of it—seems to be agreeable.
Why's that? I've used that technique in places from which I've received offers (from small non-profits to large multi-billion corps). I think it's a realistic thing to do. If they want me to code the naive way, they can just say so. If they want a better solution, and I sketch out verbally the naive solution and they're happy, why magnify into it?
The non-agreeable part is the difficulty with finding a better solution, and spending inordinate amounts of time searching for one.
> Of course it depends. Getting the ball rolling is probably not best done by giving an NP-complete problem (subset sum) as a first exercise.
2 things:
1) Being asked to solve an NP-complete problem would actually be very simple for a person with CS knowledge - just brute force it! Your solution will be reasonably close to the best-known algorithm for arbitrary input.
2) That isn't actually the subset-sum problem since they are specifying that the subset must be of size n.
When presented with an interview question, I usually say "well, it can be solved by doing $NAIVE_SOLUTION, just to get that out there, and I know you're looking for a better one." By doing this, I've established that there is a naive solution and that I'm going to spend time thinking of a better way. Unfortunately, with these kinds of algorithmic puzzle problems, it's usually a waste of time to give the naive solution in full detail, because no incremental development will ever make it monumentally better unless some cheap trick, like memoization, can be done.
This is usually the case when the problems are easier. For example, "compute the square root of a number" where the solution is, for the most part, cut-and-dry. (Though I would never blame someone for taking longer if they have to re-do the calculus by hand to rediscover the solution.) FizzBuzz is another. Simple binary tree exercises are another.As said, it entirely depends on the questions. To some interviewers, asking "how do you traverse a binary tree" on-site probably would be a waste of time; that is expected by a first-year CS student.
This is the easy way to explain it, but I don't think it's a very good answer. I don't think someone is a good fit if 7 people across 8 hours couldn't come to a consensus. If there's that much controversy, what is another coding question going to tell? This isn't an issue. In fact, it's good to talk about the business and mechanics thereof. But spending half an hour preaching to an interviewee about why the product is so good from a consumer standpoint isn't the best way to capitalize on either person's time. I think, aside from a brief introduction, that propaganda should be disseminated when the interviewee asks questions about the product.In addition to the above, I think it's a problem when the scales tip way in favor of talking about the product instead of the engineering. If the product gets a 30 minute talk and engineering gets a 5-10 minute talk, I think it's indicative about the priorities of the company toward its employees.