Problem: Write a function that calculates π.
double calculatePi(void) {
...
}
Solution: The core of the problem is straight forward -- output a numerical value for π . And yes, you can't simply return a constant like many languages allow (that would be too easy, though it's worth mentioning this to the interviewer). Also, as π is irrational, we can only approximate it with a numerical value.
Instead, the interviewer will explain a way to do this using a Gregory-Leibniz series. This is a mathematical sum that calculates pi at infinity. The proof behind this is quite complicated (and truthfully, I don't understand it, but it works). This series is shown below which sums up to pi.
Also, this is a very slow converging function. At k=150, we only have two decimal points of precision, but well, we can go much further than this!
So, coding this up should be fairly straight-forward. If we choose a big k (say 20,000), we can get a nice value for π.
Let's also put the constraint on that we can't use a power. This is also not too bad, as the (-1)^k only determines parity, so we can use an if statement letting us know that if k is even, we should pe positive, else negative.
Putting this all together, we can code it up:
double calculatePi(void) {
int i;
double pi = 0;
for (i = 0; i < 20,000; i++){
/* determine parity */
if (i%2 == 0) /* even and positive */
pi += 4 / (2*i + 1);
else
pi -= 4 / (2*i +1);
}
return pi;
}
It's worth doing a few examples here (0, 1, 2) which yield (4/1) - (4/3) + (4/5) . . .
Pretty neat. Try this, and you'll notice that you can very nice value for pi.
Also, the run-time of this function is O(20,000), which is constant, and actually quite fast as the multiply by 2 is a very fast function.
There are some optimizations possible, but this is good.
This was written on pi day (3/14). So, happy pi day!
/* Please let me know if you find errors or alternate solutions. Thank you. Noah */
Code WorkOut of the Day -- Daily exercises for programmers looking for jobs, or just to keep sharp with skills and have fun. I give talks, like this: https://youtu.be/NpvTE7GlXSM for people looking for jobs, or groups of programmers preparing for M&A tech HR due diligence. Follow us on twitter: @codewod
How to
When solving these problems, learning by doing is much better than learning by reading. I encourage to you read only as far in the solution as you need, then trying to solve the problem. If you get stuck, try reading a little further. And of course, let me know if you find a better solution!
No comments:
Post a Comment