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