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]

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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..."

Answer 5

As a manager, If I ask you to code as a test, I am most interested in:

• Whether you can write code
• Your coding style
• The algorithm you selected
• Does the attempt indicate that you understood the problem
• If I'm really hot about a specific technology, did you demonstrate that you more or less know it.

The first item may seem crazy, but you would be surprised...

Coding style -- by that I don't just mean where you put your braces, but things like:

• Did you choose composition or inheritance to solve that problem? Why?
• For that value, why did you choose to use an enum vs. a string vs. an int (or whatever permutation applies)
• Did you use properties, fields or get/set methods for that value? Why?
• How did you handle state in your classes?
• Do you understand how inheritance, interfaces, and lambdas work?
• Do you understand the parameter conventions of the language (what is by ref vs by value?)
• Do you know how to write unit tests?

Here's what I really don't care about:

• That it compiles (assuming that I just gave you notepad and no compiler)
• That you knew by memory the order of those 2 parameters in that one function
• That you can recite a SQL Server or Oracle connection string by heart
• That you can code perfectly while I am standing over your shoulder watching every mistake.

In all honesty, I was never much of a fan of coding tests -- except as a tool to analyze style.

Answer 6

In that case inroads towards an elegant solution is better than a worse but complete solution. Both cases are good though. Its absolutely fine to have written down pusdocode demonstrating you understand the problem and how you intend to solve it even if you didn't have any time to actually code the program.

Answer 7

Interviewers will ask you to improve your solution anyway.

And the "brute force solution first" approach has one indisputable advantage: if you don't manage to find an ideal solution, you still have something completed to show them.

Answer 8

I think that you're asking a question for which there is actually no answer, much less a 'right' answer. The reason I say this is that it depends entirely on what the person asking the question values.

It's possible the interviewer is a hardcore pragmatist really looking to see that you'll get something working quickly and then optimize as a lower priority activity if you have remaining time. It's equally possible that the interviewer is doing his best impression of google's hiring practices and isn't interested in anything but the sexiest, most elegant algorithm and takes it as a sign of weakness that you'd ever put the words "brute" and "force" within 5 words of one another. It's also just as possible that the interviewer googled "interview questions" and found this problem on the internet 5 minutes before you came in and has no idea what he wants.

In all cases, your best bet is probably to ask for clarification, if you can't infer based on context information what the interviewer wants. You're right that not all interview questions are fair, and, in fact, not all of them are good questions or even questions that make sense. An interview is an inherently reductionist activity, much like "speed dating" where you're spending an hour or two with someone and the two of you are trying to guess, based on that hour, whether you'll work well together for the next 5 years or not. Examined from that perspective, I hope it's clearer why I say there's really no answer to your question about a 'rule'.

Someone is asking you a question they think will give you insight into your competence and fit with their team. You have to look at their team, what you know about them, the interviewer's personality, and dozens of other factors, and make a best guess as to what answers, approach, and process they would be likely to value. Personally, I'd say that you should approach it in the way that you think is the best idea. If they don't agree with you, it might not have wound up being a good fit anyway -- easier to figure that out earlier than later.