6 ms·

When I was conducting quantitative interviews I ended up doing the same thing. One of my favorite problems to give was 267 (http://projecteuler.net/problem=267

When I was conducting quantitative interviews I ended up doing the same thing. One of my favorite problems to give was 267 (http://projecteuler.net/problem=267 http://projecteuler.net/problem=267). It has a few "aha" moments but also requires coding to get it done.

Nicholas_C 13y ago
As a finance person I really like this one. I'll have to check it out when I get home from work. Thanks!
- dangoldin 13y ago
  Glad to help! If you run into any trouble let me know (email in profile) and I'll provide some hints.
jkscm 13y ago
Is there a list with Project Euler problems that focus less on number theory like this one?
- a_bonobo 13y ago
  A lot of Project Euler is very "mathy", requiring you to read up on some mathematical shortcuts - I think https://www.hackerrank.com/ https://www.hackerrank.com/ is a bit more CS-focused, i.e., there's always a specific data-structure or algorithm that solves the problem.
- TylerE 13y ago
  You might like Rosalind (http://rosalind.info/ http://rosalind.info/). It's like Project Euler, but with a strong bioinformatics (espeically) genetics slant. There is certainly math, especially combinatrics (for obvious reasons), but much more so that Euler there is background given in the problems, so it's often much more about coding a reasonable implementation than about knowing some obscure corner of number theory.
- GyrosOfWar 13y ago
  I like Programming Praxis (http://programmingpraxis.com/ http://programmingpraxis.com/), it has mostly algorithmic problems and the questions also include solutions.
- goostavos 13y ago
  I really enjoy the types of problems on PuzzleNode[1]. My local coder meetup does one each month for code reviews. Their puzzles are just deep enough to where you need to think through how you'll design the system. They're really fun for exploring different programming techniques. [1]http://www.puzzlenode.com/ http://www.puzzlenode.com/
gajomi 13y ago
Hey, thanks. This was a fun problem. I got a little bit obsessed though, and I wonder if it might be possible to finish the problem on pencil and paper. I am sure I can finish an approximate version, but I am not sure I can get 12 digits. Did you try something like this? P.S. I must apologize for abstractly referring to a solution approach as "this", but I didn't want to create a spoiler in case anyone else had felt inspired.
- dangoldin 13y ago
  I wasn't able to do it with pen and paper and suspect it's not possible. The 1000 flips and the 1 billion is arbitrary so it seems you'd always have to work with real numbers. I may be completely wrong though.
- dsil 13y ago
  This thread is about solving them using pen and paper: http://forum.projecteuler.net/viewtopic.php?f=50&t=1982 http://forum.projecteuler.net/viewtopic.php?f=50&t=1982 I don't see this problem listed, but I didn't look through the whole thread.
- ipince 13y ago
  I actually don't know how to solve it programmatically without doing things that feel nasty. Solved it with pencil and paper, if "pencil and paper" includes asking Wolfram Alpha a few questions :)
alasdair_ 13y ago
Did you use the Kelly Criterion or did you do something else?
- dangoldin 13y ago
  I used something else - don't want to give too much away but the general idea is to try it on a smaller problem (4 flips, $5, etc) and seeing if any patterns develop.
- sbi 13y ago
  The Kelly criterion doesn't quite apply in this problem, since you are asked to optimize a more conservative strategy, namely to guarantee (with high probability) a certain amount of winnings rather than maximize log(winnings). In fact the Kelly value for f (in the problem's notation) is 0.25.
lafar6502 13y ago
Hey, who did you interview and for what position? And how many of these people succeeded? I've solved about 50 project Euler problems, but only 1 or 2 with number above 200. I'm not a genius, didn't study maths, but it's imho quite hard to solve any Euler problem at an interview, even if you're a decent thinker. Ok, there are few easy ones, but none of these with 3 digit numbers.
- dangoldin 13y ago
  It was for quantitative engineer roles at Yodle (adtech startup). The goal wasn't really to get to a solution since it's not possible without sitting down to code but more to get them thinking about it and how they'd structure the problem. I don't remember offhand how many people got it but the ones with a statistics/data background ended up having the right approach and the ones that didn't got it with a few hints.
nimble 13y ago
It surprises me that there's a unique 12 digit answer to this. If you bet proportion f of your income every round, then if you win n coin flips, shouldn't you have (1+2f)^n (1-f)^(1000-n) £? For a given f, it takes a certain number of heads for this value to exceed 1B£, but I'd expect a range of f values that all require the same minimal number of heads results to break 1B£. Unless there's a value of f that produces exactly 1B£ for the minimal needed number of heads (or the set of such f differ only after 12 digits). That seems unlikely... EDIT: Just realized that the problem asks for the odds of being a billionaire, not f. So there are probably a good number of f that work, but they all produce the same odds.
pedrosorio 13y ago
Nice problem, made me come back to projecteuler! I hadn't solved anything for 3 years.
BenoitP 13y ago
My solution would be: For one coint toss, I get: (previous winnings) x (1+f) if I win (previous winnings) x (1-f) if I lose Thus, w being the number of times I win, I get the total $$ we would have: (1+f)^w x (1-f)^(1000-w) But those cases are not equally likely, so we have to ponderate them with a normal law centered at 1000/2, variance at sqrt(1000/4): (1/(sqrt(2xPi)xsqrt(250))) x exp(-(500-w)^2/500) So, now we can take an f, calculate the number of w's that put us above 1B$, and sum up the ponderation for each case. Then find the right f that optimized the chance of being a billionaire. This chance is the solution.
- gjm11 13y ago
  It's actually 1+2f versus 1-f. (I agree that the wording is not very clear. I misinterpreted it too at first and was very confused at how my solution was being rejected. If you look at the short worked example they give, though, it's unambiguous.) You're using the normal approximation to the binomial distribution. It may or may not be a good enough approximation. Better to do the binomial thing exactly. This requires arbitrary-precision integer arithmetic, but that's pretty easily available.
- opk 13y ago
  I get 1/4 as the optimal value for f. Given a 500/500 win lose, then final money = (1-f)^500*(1+2f)^500 = (-2f^2+f+1)^500. To find the maximum, the ^500 is irrelevant. Differentiating and finding a gradient of 0 gives: -4f+1=0 or f=1/4. Just by checking values, it seems I need to lose more than 555 times before I finish with less then 1 billion. I'm not sure how to calculate the probability of that, your formula doesn't seem to work. In any case, the problem seems to be purely mathematical rather than requiring code to be written.
  - anonymoushn 13y ago
    I have a different f that can win with only 433 heads.
mathattack 13y ago
Is there any danger that someone has seen the problem?
- dangoldin 13y ago
  Yea - then we just walk through their answer to make sure they get the reason it works and ways to improve it. It's usually quicker and leaves time for another question that they hopefully haven't heard.

Nicholas_C 13y ago

As a finance person I really like this one. I'll have to check it out when I get home from work. Thanks!

dangoldin 13y ago
Glad to help! If you run into any trouble let me know (email in profile) and I'll provide some hints.

jkscm 13y ago

Is there a list with Project Euler problems that focus less on number theory like this one?

a_bonobo 13y ago
A lot of Project Euler is very "mathy", requiring you to read up on some mathematical shortcuts - I think https://www.hackerrank.com/ https://www.hackerrank.com/ is a bit more CS-focused, i.e., there's always a specific data-structure or algorithm that solves the problem.
TylerE 13y ago
You might like Rosalind (http://rosalind.info/ http://rosalind.info/). It's like Project Euler, but with a strong bioinformatics (espeically) genetics slant. There is certainly math, especially combinatrics (for obvious reasons), but much more so that Euler there is background given in the problems, so it's often much more about coding a reasonable implementation than about knowing some obscure corner of number theory.
GyrosOfWar 13y ago
I like Programming Praxis (http://programmingpraxis.com/ http://programmingpraxis.com/), it has mostly algorithmic problems and the questions also include solutions.
goostavos 13y ago
I really enjoy the types of problems on PuzzleNode[1]. My local coder meetup does one each month for code reviews. Their puzzles are just deep enough to where you need to think through how you'll design the system. They're really fun for exploring different programming techniques. [1]http://www.puzzlenode.com/ http://www.puzzlenode.com/

gajomi 13y ago

Hey, thanks. This was a fun problem. I got a little bit obsessed though, and I wonder if it might be possible to finish the problem on pencil and paper. I am sure I can finish an approximate version, but I am not sure I can get 12 digits. Did you try something like this? P.S. I must apologize for abstractly referring to a solution approach as "this", but I didn't want to create a spoiler in case anyone else had felt inspired.

dangoldin 13y ago
I wasn't able to do it with pen and paper and suspect it's not possible. The 1000 flips and the 1 billion is arbitrary so it seems you'd always have to work with real numbers. I may be completely wrong though.
dsil 13y ago
This thread is about solving them using pen and paper: http://forum.projecteuler.net/viewtopic.php?f=50&t=1982 http://forum.projecteuler.net/viewtopic.php?f=50&t=1982 I don't see this problem listed, but I didn't look through the whole thread.
ipince 13y ago
I actually don't know how to solve it programmatically without doing things that feel nasty. Solved it with pencil and paper, if "pencil and paper" includes asking Wolfram Alpha a few questions :)

alasdair_ 13y ago

Did you use the Kelly Criterion or did you do something else?

dangoldin 13y ago
I used something else - don't want to give too much away but the general idea is to try it on a smaller problem (4 flips, $5, etc) and seeing if any patterns develop.
sbi 13y ago
The Kelly criterion doesn't quite apply in this problem, since you are asked to optimize a more conservative strategy, namely to guarantee (with high probability) a certain amount of winnings rather than maximize log(winnings). In fact the Kelly value for f (in the problem's notation) is 0.25.

lafar6502 13y ago

Hey, who did you interview and for what position? And how many of these people succeeded? I've solved about 50 project Euler problems, but only 1 or 2 with number above 200. I'm not a genius, didn't study maths, but it's imho quite hard to solve any Euler problem at an interview, even if you're a decent thinker. Ok, there are few easy ones, but none of these with 3 digit numbers.

dangoldin 13y ago
It was for quantitative engineer roles at Yodle (adtech startup). The goal wasn't really to get to a solution since it's not possible without sitting down to code but more to get them thinking about it and how they'd structure the problem. I don't remember offhand how many people got it but the ones with a statistics/data background ended up having the right approach and the ones that didn't got it with a few hints.

nimble 13y ago

It surprises me that there's a unique 12 digit answer to this. If you bet proportion f of your income every round, then if you win n coin flips, shouldn't you have (1+2f)^n (1-f)^(1000-n) £? For a given f, it takes a certain number of heads for this value to exceed 1B£, but I'd expect a range of f values that all require the same minimal number of heads results to break 1B£. Unless there's a value of f that produces exactly 1B£ for the minimal needed number of heads (or the set of such f differ only after 12 digits). That seems unlikely... EDIT: Just realized that the problem asks for the odds of being a billionaire, not f. So there are probably a good number of f that work, but they all produce the same odds.

pedrosorio 13y ago

Nice problem, made me come back to projecteuler! I hadn't solved anything for 3 years.

BenoitP 13y ago

My solution would be: For one coint toss, I get: (previous winnings) x (1+f) if I win (previous winnings) x (1-f) if I lose Thus, w being the number of times I win, I get the total $$ we would have: (1+f)^w x (1-f)^(1000-w) But those cases are not equally likely, so we have to ponderate them with a normal law centered at 1000/2, variance at sqrt(1000/4): (1/(sqrt(2xPi)xsqrt(250))) x exp(-(500-w)^2/500) So, now we can take an f, calculate the number of w's that put us above 1B$, and sum up the ponderation for each case. Then find the right f that optimized the chance of being a billionaire. This chance is the solution.

gjm11 13y ago
It's actually 1+2f versus 1-f. (I agree that the wording is not very clear. I misinterpreted it too at first and was very confused at how my solution was being rejected. If you look at the short worked example they give, though, it's unambiguous.) You're using the normal approximation to the binomial distribution. It may or may not be a good enough approximation. Better to do the binomial thing exactly. This requires arbitrary-precision integer arithmetic, but that's pretty easily available.
opk 13y ago
I get 1/4 as the optimal value for f. Given a 500/500 win lose, then final money = (1-f)^500*(1+2f)^500 = (-2f^2+f+1)^500. To find the maximum, the ^500 is irrelevant. Differentiating and finding a gradient of 0 gives: -4f+1=0 or f=1/4. Just by checking values, it seems I need to lose more than 555 times before I finish with less then 1 billion. I'm not sure how to calculate the probability of that, your formula doesn't seem to work. In any case, the problem seems to be purely mathematical rather than requiring code to be written.
- anonymoushn 13y ago
  I have a different f that can win with only 433 heads.

mathattack 13y ago

Is there any danger that someone has seen the problem?

dangoldin 13y ago
Yea - then we just walk through their answer to make sure they get the reason it works and ways to improve it. It's usually quicker and leaves time for another question that they hopefully haven't heard.