In an interview, is it better to code a brute-force solution to a tough question, or to spend the interview examining the question carefully? [closed]

Want to improve this question? Update the question so it can be answered with facts and citations by editing this post.

Sometimes interview questions are hard, whether the interviewer intends them to be, or not. It can come down to a choice of whether to use the limited interview time to code up an ugly, inefficient, brute-force solution, or spend the time understanding every aspect of the problem with the interviewer. For example, Problem 91 at Project Euler can be solved by a not-so difficult brute-force solution of calculating every possible triangle, writing an isRightTriangle() test, and popping all triangles that pass the test into a set. But the two pair of X/Y coordinates make that an O(x^4) solution with a high constant value. A friend and I just came up with a solution that is much more elegant and efficient, but the two of us spent 3 hours on it and drew dozens of diagrams, tested multiple formulae, examined multiple approaches, etc. Not every interview question is fair. Also what's easy for one person may be hard for another. If someone struggles with a question, would you be more impressed by a brute force ugly solution that works? Or excellent problem comprehension and in-roads toward an elegant solution, but no coded solution? Is there a rule like after 20 minutes you should just start coding no matter what?

If they had wanted a non brute force solution they would have given a question that can't be solved by brute force in the first place .

8 Answers 8

First of all, a question that takes two experienced developers three hours to elegantly optimize is a poor choice for an interview question. If you ask it, you shouldn't expect perfect answers.

On the other hand, sometimes you learn the most about someone when you make them hit their limits. That's why a lot of college courses ramp up the difficulty then grade on the curve. If everyone scores 100% on each exam, you're leaving a lot of potential learning out.

My ideal candidate would probably do the complexity calculation first, say "Oh, that's only 6 million iterations, which won't take very long," then quickly write the brute force solution. Then they would discuss approaches they could take to optimize it, without necessarily implementing them unless the interviewer asked them to.

Partly, this is because a lot of the project euler type problems that come up in the real world are one-shot problems that you need to solve once then forget about it. I want to know that someone I hire will be able to recognize a brute force algorithm that takes 2 minutes to write and 10 minutes to run is more efficient than an algorithm that takes 3 hours to write and 10 seconds to run, if you only need to run it that one time.

Great answer. Caleb brought up the brute-force-first-then-optimize concept, but yours is the only answer that suggests providing the reason why a brute-force solution is acceptable in this case, "That's only 6 million iterations, which won't take very long." That's just gold. Thanks so much!

As a hiring manager, if I'm asking you to solve a problem with code right there in front of me, I'm not doing it so much to see the code itself (although it's important) but rather to ascertain the how and why you did what you did. One of those things that you might do is not code, and instead interrogate me as to the aspects of the problem itself, to better solve it. That's meaningful to me, and usually more meaningful than the solution laid out there in code. However, that is not how everyone does it, nor is what everyone wants to see (and in fact, I rarely do ask people to code in an interview setting but I do put problems on the table and we talk through them and sometimes pseudocode emerges, which is just as good for me).

You're right that not every interview question is fair, and what is easy for someone is difficult for another, in that setting and with those constraints, and that is why those interviews who understand that are typically not looking for the code solution (although, again, that does play an important role) but rather the solution process.

"Is there a rule like after 20 minutes you should just start coding no matter what?" I'd answer this by saying that within a very short time of thinking about the problem, you should at least be doing something -- asking more questions, sketching out a framework for a solution, or saying you just can't do it/don't know where to start.

If I put a hard problem in front of you and the solution you provided -- given constraints of time and what have you -- was brute force and ugly, I would then ask you a series of questions as to why that was the case, and what would change it to something more elegant: more information? more time? a different environment? Being self-aware and in touch with the why of what you've done, and what you've not done, and being able to rationally explain it, is a big gold star in my book, but those are the sorts of developers I look for. So, "excellent problem comprehension and in-roads toward an elegant solution" would work for me, too, but not everyone.

Plus a million for "Being self-aware and in touch with the why of what you've done, and what you've not done, and being able to rationally explain it, is a big gold star in my book". The amount of people who, when asked "Why?", just founder and can't answer is unbelievable. When hiring, I'd almost always prefer to teach someone to code who can think for themselves than hire someone who can code but can't think.

Thanks. This is insightful. My tendency at my job is to analyze before touching the keyboard. But under the pressure of an interview, I want desperately to show a solution programmers.stackexchange.com/questions/178075/… Your answer provides a nice counter-example to remember.

I'd want both, but they may display a "code that just works" in one solution and then possibly discuss potential solutions for improvement in that one or another problem.

If you ask someone to write code and they just want to talk about possible solutions with zero code, that would be a concern.

Like you said, someone may struggle with the particular problem for whatever reason, but you have to learn how they go about solving them. They could get lucky and have already heard about a solution to a similar problem. It happens.

Watch someone go about writing enough code and discussing it and you can figure-out if they're right for the job.

I guess I'd also want to hear why the brute force solution may be a problem, as in the question above.

@ChristopherCreutzig - I assumed it would be difficult to offer improvements without at least suggesting the problems with the current solution.

Is there a rule like after 20 minutes you should just start coding no matter what?

No, but if you spend 20 minutes analyzing the problem before you get down to business, you're probably in trouble already. An employer who asks you a question like the one you cited is mostly interested in how you approach a problem, but if they ask it as a coding problem they'll want to see some code too. Talk them through your thought process.

Well, the obvious approach here is brute force. If I had a way to recognize a right triangle given the three vertices, I could run through all the combinations of two points and the origin looking for right triangles. That shouldn't be hard -- I can write a function that uses the Pythagorean Theorem to identify right triangles. To make that easier, I'll also write a function that determines the distance between two points using the distance formula.

Writing those functions should take about three minutes. Now, just a few minutes into the question, you've already shown that you remember basic geometry and that you really do know how to write code. It also gives you something to talk about:

So, we could obviously put the isRightTriangle(p1, p2, p3) function in the middle of four for loops and iterate over all the possible choices for each of the two variable points. Let's see. the problem asks for the number of right triangles including the origin on a 50x50 grid, so using the brute force method makes us check 50 possibilities for each coordinate of each point. That's 50^4 checks. I'm sure we can do better, but the code is obvious, so let me write that down.

So now you write a function that uses nested for loops and the isRightTriangle() function that you just wrote. You've solved the problem, but you've also let the interviewer see where you're going. If their goal was just to see that you can write code, they might tell you to stop. More likely, they're happy to be talking to someone who knows what they're doing and they'll want to see how far you take this. So you go on.

It occurred to me while I was writing that that we can take advantage of symmetry. We can reflect any given right triangle around the 45° line, so if we choose to check one of the points only on one side of that line, we can just count any right triangles we find twice. once for the triangle and once for its reflection. That cuts the number of checks by half. Also, looking at it now, we're taking a square root to find the distance between two points, but then we just square that again in isRightTriangle() .

And so on. Again, they don't usually want to see a perfect solution, they want to see how you get to a solution. Your thought process doesn't have to be anything like the one above -- just having the confidence to think out loud will count for a lot. Don't sweat it if you make a mistake -- just say "hmmm, I think I've gone off the rails here -- let me go back a step. "