Google’s Colab is a powerful tool, just as many of you have gotten used to Google Drive, Docs, Sheets. You’re able to run python code on a remote machine and even have access to GPU / TPUs.
Recently I became very interested in Brian Christian and Tom Griffiths book ‘Algorithms to Live By’ and they discuss the optimal stopping algorithm (also known as the secretary problem). There are many great resources online (links below) that describe this problem but here is a summary:
Problem Summary
Say you wanted to hire an assistant out of N assistants. These candidates are interviewed in random order and you have to make a decision right after you interview them – accept or reject. Once you reject a candidate, they cannot be recalled.
Of course you are aware of how good this candidate is as you are interviewing them and are able to compare them to the previous candidates (which you rejected and are unable to recall). The difficulty is two fold – you are unable to recall past candidates AND you have no information about future candidates. All you can do is compare the candidate in front of you to past candidates.
When do you stop and accept a candidate?
When you do stop, what is the probability that you obtained the best candidate?
Test Cases
Let’s do a couple of test cases.
N = 1 (Only one candidate applied.)
In this case your best candidate is also your worst candidate so your probability of getting the best candidate is 100% (or 1.0)
N = 2 (Two candidates applied.)
This is like a coin toss. Whether you stop at the first or second candidate, your probability of getting the best candidate is 50% (0.5)
N = 3 (Three candidates applied.)
This is the first real example, where a strategy has to be applied. There are 6 different ways the ranked candidates can present themselves:
If you stop with the first candidate, your chance of getting the best candidate is 1/3 (see the last two permutations).
If you stop at the second candidate and select the candidate only if this candidate is better than the first one you interviewed, then your chance of getting the best candidate is 3/6 (see below).
If you stop at the third candidate, your options are limited and only 2/6 times do you get the best candidate.
Let’s say you keep going for N candidates, this is what you should ultimately converge on (and the code below will summarize how many you should pick, and the ‘chance of getting the best’)

Google Colab
We can represent this algorithm in Google’s Colab:
First import required packages and set the style. I have used seaborn-whitegrid here.
Set the number of applicants and create an empty array:
Cycle through multiple repeats (I have done 10,000 repeats here of each N number and averaged the results). You will achieve numbers closer to the true probability and best selection index with higher repeats:
Finally, create the plot:
I encourage you to read through these references about the optimal stopping problem and you will notice this probability converges to around 37%.

Please do not torture yourself trying to copy the script above, use mine:
Google Colab Script
References:
[1] Hill, T. Knowing When To Stop. (2009), American Scientist
[2] Wikipedia: Optimal Stopping Accessed: October 2020
[3] Swanson, A. When to stop dating and settle down according to math (2016), Washington Post