menu

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 go-fetch-and-eat game where he draws a milk-bone 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 (sub-questions)

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:

class Solution:
    def __init__(self, ...):
        pass
    
    def fetchAndEat(self, t):
        # some calculation 
        # ...
         
        # make the call!
        return False

, 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:

s = Solution()
ate = []
for i in range(n):
    if s.fetchAndEat(T[i]):
        ate.append(T[i])
    if len(ate) == k:
        break 
print("Your final treat weight sum: {}".format(sum(ate)))

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 non-ML way.

  • face Hint 2

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

  • face Follow-up

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

encrypt
Top