Solve the Secretary Problem

Question

The Secretary Problem is a famous problem described as thus:

1. You need a new secretary
2. You have N applicants that you can interview one at a time
3. You are able to score each applicant after the interview. Your scoring system will never give two applicants the same score
4. After you interview an applicant, you must give an immediate "yes" or "no"
5. You want the applicant with the highest score

The solution is to interview the first floor(N/e) applicants, and then accept the first applicant that has a higher score than all of the previous applicants. If none of the applicants are higher, then return the last applicant. Interestingly enough, this gives the top applicant 1/e percent of the time. e refers to Euler's number. To get the value of e, you can use a builtin, log, or hardcode it to at least 5 decimal points.

Input:

An non-empty array of unique non-negative integers no more than 2^31-1.

Output:

An integer representing the chosen candidate. To be clear the algorithm is:

1. Find the maximum element in the first floor(N/e) elements of the array.
2. Iterate through the remaining elements, and return the first element that is higher than the maximum found on step 1.
3. If none of the elements are higher, than return the last element.

For example, say your array was [2,7,4,3,9,20], so N = 6 and floor(N/e) = 2. The first 2 elements of the array is [2,7]. The max of [2,7] is 7. The remaining elements are [4,3,9,20]. The first element that is greater than 7 is 9, so we return 9.

Test Cases:

[0]         => 0
[100]       => 100
[100, 45]   => 100
[0, 1]      => 0
[45, 100]   => 45
[1, 4, 5]   => 4
[1, 5, 4]   => 5
[5, 4, 1]   => 1
[5, 1, 4]   => 4
[4, 1, 5]   => 5
[56, 7, 37, 73, 90, 59, 65, 61, 29, 16, 47, 77, 60, 8, 1, 76, 36, 68, 34, 17, 23, 26, 12, 82, 52, 88, 45, 89, 94, 81, 3, 24, 43, 55, 38, 33, 15, 92, 79, 87, 14, 75, 41, 98, 31, 58, 53, 72, 39, 30, 2, 0, 49, 99, 28, 50, 80, 91, 83, 27, 64, 71, 93, 95, 11, 21, 6, 66, 51, 85, 48, 62, 22, 74, 69, 63, 86, 57, 97, 32, 84, 4, 18, 46, 20, 42, 25, 35, 9, 10, 19, 40, 54, 67, 70, 5, 44, 13, 78, 96]
=> 98
[10, 68, 52, 48, 81, 39, 85, 54, 3, 21, 31, 59, 28, 64, 42, 90, 79, 12, 63, 41, 58, 57, 13, 43, 74, 76, 94, 51, 99, 67, 49, 14, 6, 96, 18, 17, 32, 73, 56, 7, 16, 60, 61, 26, 86, 72, 20, 62, 4, 83, 15, 55, 70, 29, 23, 35, 77, 98, 92, 22, 38, 5, 50, 82, 1, 84, 93, 97, 65, 37, 45, 71, 25, 11, 19, 75, 78, 44, 46, 2, 53, 36, 0, 47, 88, 24, 80, 66, 87, 40, 69, 27, 9, 8, 91, 89, 34, 33, 95, 30]
=> 30

Your solution must be O(n), where n is the length of the array. If your language has a builtin that finds the maximum of an array, you can assume that the function takes O(n) (and hopefully it does).

Standard loopholes apply, and this is a code-golf, so the make the shortest answer in your favorite language!

Answer 1

Jelly, 13 bytes

L:Øe³ḣȯ-Ṁ<i1ị

Definitely an O(n) algorithm, hopefully an O(n) implementation. Try it online!

How it works

L:Øe³ḣȯ-Ṁ<i1ị  Main link. Argument: A (list of scores)

L              Get the length of A.
 :Øe           Divide the length by e, flooring the result.
    ³ḣ         Retrieve the that many scores from the beginning of A.
      ȯ-       Logical OR; replace an empty list with -1.
        Ṁ      Compute the maximum of those scores.
         <     Compare each score in A with that maximum.
          i1   Find the first index of 1 (0 if not found).
            ị  Retrieve the element of A at that index (the last one if 0).

Answer 2

CJam, 20 Bytes

q~___,1me/i<:e>f>1#=

Works similarly to Dennis's suggestion.

q~___                     Read array, duplicate three times
      ,                   Consume one to find the length
       1me/i              Push e then divide and take floor
            <             Take that many elements from the list
             :e>          Find maximum (Thanks to Dennis)
                f>        Label array elements larger than this as 1
                  1#      Find the first one (won't be in set of elements we've looked in)
                    =     Take that element from the final copy of the array. -1 gives us the last element as required

Answer 3

Java, 128 118 bytes

a->{int c=(int)(a.length/Math.E),i=0,m=-1,t=0;for(;i<a.length;i++){t=a[i];if(i<c)m=t>m?t:m;if(t>m)return t;}return t;}

Indented:

static Function<Integer[], Integer> secretary2 = a -> {
    int c = (int) (a.length/Math.E),     // c = floor(N/E)
        i = 0, m = -1, t = 0;            // declare vars early to save bytes
    for (;i<a.length;i++) {              // for each element of input
        t = a[i];                        // cache element to save bytes
        if (i<c)                         // if before c
            m = t>m ? t : m;             // m = max(m, element)
        if (t>m)                         // if element > m
            return t;                    // return: we've found our best
    }                                    // if never found a good element
    return t;                            // return the last element
};

Answer 4

MATL, 27 25 23 bytes

tttn1Ze/:)-1hX>>T0(f1))

Uses the same approach as A. Simmons' CJam answer.

Try it online!

Answer 5

JavaScript (ES6) 64

(a,l=a.length/Math.E,x)=>(a.every(v=>--l>0?x>v?1:x=v:(z=v)<x),z)

Less golfed

(
 a, 
 l=a.length/Math.E, // limit for stage 1
 x // init at undefined
)=>(
  a.every(v => --l > 0 // checking for >0 no need to floor
          ? x>v?1:x=v // stage 1, find max in x, always return truthy
          : (z=v)<x ) // stage 2, set z to current value and exit early if z>x
  , z // at last z has the last seen value
)

Test

f=(a,l=a.length/Math.E,x)=>(a.every(v=>--l>0?x>v?1:x=v:(z=v)<x),z)

console.log=x=>O.textContent+=x+'\n'

;[ 
 [0], [100], [0,1], [1,2,3],
 [100, 45],
 [45, 100],
 [1, 4, 5],
 [1, 5, 4],
 [5, 4, 1],
 [5, 1, 4],
 [4, 1, 5],   
 [10, 68, 52, 48, 81, 39, 85, 54, 3, 21, 31, 59, 28, 64, 42, 90, 79, 12, 63, 41, 58, 57, 13, 43, 74, 76, 94, 51, 99, 67, 49, 14, 6, 96, 18, 17, 32, 73, 56, 7, 16, 60, 61, 26, 86, 72, 20, 62, 4, 83, 15, 55, 70, 29, 23, 35, 77, 98, 92, 22, 38, 5, 50, 82, 1, 84, 93, 97, 65, 37, 45, 71, 25, 11, 19, 75, 78, 44, 46, 2, 53, 36, 0, 47, 88, 24, 80, 66, 87, 40, 69, 27, 9, 8, 91, 89, 34, 33, 95, 30],
[56, 7, 37, 73, 90, 59, 65, 61, 29, 16, 47, 77, 60, 8, 1, 76, 36, 68, 34, 17, 23, 26, 12, 82, 52, 88, 45, 89, 94, 81, 3, 24, 43, 55, 38, 33, 15, 92, 79, 87, 14, 75, 41, 98, 31, 58, 53, 72, 39, 30, 2, 0, 49, 99, 28, 50, 80, 91, 83, 27, 64, 71, 93, 95, 11, 21, 6, 66, 51, 85, 48, 62, 22, 74, 69, 63, 86, 57, 97, 32, 84, 4, 18, 46, 20, 42, 25, 35, 9, 10, 19, 40, 54, 67, 70, 5, 44, 13, 78, 96]
].forEach(t=>{
  var r=f(t)
  console.log(r+' : '+t)
})

<pre id=O></pre>

Answer 6

Ruby, 64 bytes

->a{m=a[0...c=a.size/Math::E].max
a[c..-1].find{|n|n>m}||a[-1]}

Answer 7

PARI/GP, 70 bytes

This may have trouble on older versions of gp when given a singleton, but it works at least from revision 18487.

v->m=vecmax(v[1..t=#v\exp(1)]);for(i=t+1,#v,v[i]>m&&return(v[i]));v[#v]

Answer 8

JavaScript (ES6), 79 bytes

a=>(m=Math.max(...a.splice(0,a.length/Math.E)),a.slice(a.findIndex(x=>x>m))[0])

Works because findIndex returns -1 on failure, but a.slice(-1)[0] returns the last element of the array as desired.

Answer 9

Python 2, 87 bytes

a=input()
t=int(len(a)/2.71828)
m=max(a[:t]+[-1])
for x in a[t:]:
 if x>m:break
print x

The user enters the array as a list, with square brackets and commas. Python 2's input() command is convenient here.

Whether or not we terminate the process early, we hire the last person who got interviewed.

Answer 10

Perl 6, 43 bytes

I think this is O(n)

{@^a.first(*>max @a[^floor @a/e])//@a[*-1]}

Answer 11

Python 3.5; 110 bytes:

def Interview(h):k=max(h[0:int(len(h)/2.71828)-1]);n=max(h[int(len(h)/2.71828)-1:len(h)-1]);return max([k, n])

Basically, what the above does is that it firstly takes an array provided, "h" as long as it includes more than 5 items (for now...), finds the maximum value in the first (length of array (len(h))/ Euler's number (to 5 decimal places)) items of that array, and then returns that value as "k". Furthermore, "n" is the maximum value in the rest of the array. Finally, the value returned from the function is the maximum value in an array containing both "k" and "n".

Note: The max() function of Python is O(n) complexity.

Below is a more readable, non-code-golf version of the above code that has a random, unique 10-item array provided, to confirm that it works:

import random, math

def Interview():
    k = max(h[0:int(len(h)/math.e)-1])
    n = max(h[int(len(h)/math.e)-1:len(h)-1])
    return max([k, n])

h = random.sample(range((2*31)-1), 10)

print(Interview(h))