Three Treats for Keke
Posted on 14/05/2019, in Career.Question Description
Keke is a very smart dog that just finished the CS2XX (Machine learning, algorithm and data structure, etc.) series at Stanford and try to find some real problem to solve. Here is one big challenge Keke is facing everyday: His master will play a couple of rounds of gofetchandeat game where he draws a milkbone treat from the jar and throw it away and let him fetch. Keke can decide to fetch it or not but whenever Keke eat $k$ treats or they play $n$ rounds, his master will pick up the leftover and put them back to the jar (how stingy is he!). Keke is thinking of optimizing the expected weight sum of the treats he get.
Assumptions
The first step of solving this is to make some assumptions and simplify the problem. After playing for so many times, Keke feels he is confident enough to assume:
 Assumption 1: Each treat’s weight $X_i$ follows a uniform distribution from 0 to 1 independently. Or mathematical barking, $X_i \sim U(0,1), i.i.d.$
 Assumption 2: $k$ is much smaller than $n$, i.e. $k \ll n$
Two steps (subquestions)
And to simplify, Keke decide to solve the problems in two steps:
 Base case: $n=4$ and $k=1$.
 A more general case: $n=15$ and $k=3$.
Testing Scheme
You should implement your strategy as a class method in fetchAndEat
:
, where $t$ is the weight of the the treat uniformly distributed from 0 to 1 and the return is the if Keke decide to fetch and eat.
Notice you can have status in the class keep track of the decision you made.
In the test time your strategy will be run for a lot of times and the average result is reported. Here is one example of the test:
Here $T$ is a list of treat weights that will potentially be threw away (but Keke doesn’t know).
You should submit one solution and we will test over Base case and A more general case at the same time.

face Hint 1
This problem can be solved in either ML or nonML way.

face Hint 2
For the Base case, you might want to think in a backward way.

face Followup
What would be your strategy if we don’t know the distribution of the treat?