---
# System prepended metadata

title: 1. Secretary problem by simulation

---

# 1. Secretary problem by simulation

## Problem Description:

We will see N=100 job candidates whose levels are random between 0 and 10. We see the candidates one-by-one, and after seeing each candidate, we have to make a decision on the spot whether to hire this candidate or not. This decision is irrevocable and we cannot change our mind later! We want to _maximize the probability to hire the best out of the N candidates_.

To do so, we will implement the following policy:

* Reject the first R candidates.
* Then hire the first one we see that is better than the best among the first R.

Write a program that decides the optimal threshold R using simulations.


```python=
 s = 1/10 
   
P(S>s) = 1 - P(s<S) 
       = 1 - int(1/10)_0^S

def score(candidates):
...

R

for R: # R 
    for simulations: # S
    
        candidates = [....]

        rejected = [:R]

        score_best_seen, _ = score(rejected) # R 

        remaining = [R:]

        score_hired, idx = score(remaining)

        hired_candidate = remaining[idx]

        def check_best(score_hired, candidates): # True or false
            return score_hired == max(scored_hired, max(candidates.score))
# Complexity = R*S*N
```

