Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: