Secretary Optimal Threshold Rank

Problem

Return the number of applicants to reject that exactly maximizes the secretary problem success probability.

For each threshold k, the success probability is (k - 1) / n times the sum of 1 / (j - 1) for j from k to n; return the smallest k attaining the maximum. Return 0 for n <= 1.

Hint

The exact optimum sits near n / e, but floating-point comparison over all k keeps it precise.

Test cases

case 1

in: [1]

expected: 0

case 2

in: [2]

expected: 2

case 3

in: [3]

expected: 2

case 4

in: [10]

expected: 4

case 5

in: [100]

expected: 38

Starter codePython

def secretary_best_threshold(n):
    # Your code here
    pass

5 test cases · run your code against them in the editor