Hacker News Reader

Comment by mindslight | Hacker News Reader

What's the easy answer to the first one? It seems that you need to analytically prove a bound for the remaining terms, no?

View on HN

I would just write the code to compute it to arbitrary precision and then tell the interviewer that I would test how many iterations are required and hard-code it.

If they insist that it must be solved at runtime, I would check the size of the computed term (1/(1+2x)) and repeat 'til it's less than 10E-6.

If you're hardcoding it, n will be around 400,000.

That's a lot of iterations.

Besides the slowness of such a solution, that condition is not enough to ensure the first five decimal places are correct.

If you are told the formula to use, you use it. No, it's not the bestest way ever of finding pi. It's to make sure the guy sitting across from you can actually write code, which a scary number of people actually cannot do.

The formula is

  p(n) = p(n-1) + 4*((-1)^(n-1))/(2n-1)
  n = {1,2,3...} and p(0)=0

I think that p(n)-p(n-1) must be less than the precision you want (0.00001).

*Mental note: never start reply math on iPad ;)

It's an alternating decreasing series so the sum of the remaining terms is always less than the current term. Also, each pair is 1/n - 1/(n+2) = 2/(n*(n+2)) which converges like 1/n^2 (all successive terms sum to the same order as the current term). That this pairing converges much faster than the original series is part of what makes the question good: a good solution will exploit this pairing for numerical stability and to converge in much fewer steps (square root of the number needed by the naive algorithm).

I was thinking that you'd want to pair the terms, but going further didn't happen to tickle my curiosity. Of course after seeing your answer, it looks quite obvious.

My larger conclusion is that either the OP didn't intend to require this analysis or he's surprised that people in an interview+coding mindset are going to get stuck thinking there is a straightforward algorithm. Since he refers to the question as simple for any "seasoned developer" (read: has forgotten algebra ;), I presume he actually misstated the problem and really expected one of the simplifications people have come up with. Either way, I think it says more about the interviewer than the interviewees.

The interviewer can ask leading questions if the interviewee gets stuck or doesn't consider certain attributes. Seemingly simple questions that actually have depth are good for an interview because it stimulates discussion and can be carried further for more advanced/competent people. Quizzing someone on "trivia" is a terrible test of competence.

Yeah, it's true that good technical questions are an interactive process. But I'm not too confident that the OP actually saw the complexity in that question, and the many naive responses certainly did not. Also in the context of trying to come up with code on the spot, knowing how that infinite sum is going to converge strikes me as a quite helpful piece of trivia.

... although maybe my gripe only came about from knowing enough to immediately see that there had to be some kind of convergence bound, but not knowing/figuring exactly what it was.

I think the interviewer was asking for something really easy and un-optimized. Something like:

iterate and alternately subtract and add 1/i, (then i=i+2) to get your multiplier.

Each iteration multiply 4 times the resulting multiplier. Break when the answer rounded to 5 decimal places == 3.14159

I wonder if they really do mean to break when the answer hits the known value. If so that's kind of a pathetically useless thing to do. While I know most whiteboard coding problems aren't things you ever need to write in production code, the change to make it break when five decimal places stabilise is not much more difficult and provides an actual nontrivial output.

given that his next step down in difficulty was

>Given the area of a circle is given by Pi times the radius squared, write a function to calculate the area of a circle.

I think we can assume he was just looking for something trivial.

I'm sure it would be fine as a first pass but there's no way anyone would end it there. Two obvious immediate objections being that the point where it first rounds to the correct value does not imply the point where it stabilises there and the second being that you're using the value you're trying to calculate in calculating said value. At that point, a good interviewer leads them toward fixing these issues rather than just saying "wrong", of course, but I'm sure the end result is not to use pi in the algorithm.

Also, his next step down isn't really one jump down in difficulty; it's presented as "if you don't even know how to begin to approach that problem I need to make sure that you can code something trivial." That is to say, it's an arbitrary number of steps down that implies little about the initial question's intended difficulty.

Reply on news.ycombinator.com