Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 , so the make the shortest answer in your favorite language!

share|improve this question
1  
What e should be used? – afuous Mar 22 at 16:52
2  
@voidpigeon I presume it's en.wikipedia.org/wiki/E_(mathematical_constant) – Doorknob Mar 22 at 16:53
1  
Ah, now I understand how the algorithm works. I thought your second paragraph meant that you never interview the candidates after floor(n/e) at all. – Doorknob Mar 22 at 17:10
1  
I asked specifically because in some languages, it's shorter to define a variable with 5 decimal points of precision than it is to actually use the builtin e (e.g. Python, where e=2.71828 is shorter than import math;math.E) – Mego Mar 22 at 18:19
1  
Note: ` 1/e percent of the time.` would be really bad. It's a probabilty of 1/e, that is roughly 37% of times – edc65 Mar 23 at 11:28

11 Answers 11

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).
share|improve this answer

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
share|improve this answer
    
$W= doesn't run in linear time. – Dennis Mar 22 at 18:32
    
Urgh, you're right. Is there any better way of finding the maximum in CJam that you know of that does? – A Simmons Mar 22 at 18:33
1  
:e> (reduce by maximum) – Dennis Mar 22 at 18:33
    
@Dennis Thanks! – A Simmons Mar 22 at 19:43

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
};
share|improve this answer

MATL, 27 25 23 bytes

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

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

Try it online!

share|improve this answer

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>

share|improve this answer

Ruby, 64 bytes

->a{m=a[0...c=a.size/Math::E].max
a[c..-1].find{|n|n>m}||a[-1]}
share|improve this answer
2  
@Doorknob It loops through the first floor(N/e) elements once to find the maximum, then loops through the rest of the list in the worst case comparing each element to the maximum. There is only one comparison per element in both parts. – afuous Mar 22 at 17:05
    
Ah, that's right. I misread and thought you were finding the max in each iteration. – Doorknob Mar 22 at 17:07
1  
In fact, I think it's still O(n) if you just do a.find in the second step, although obviously it's a lot less efficient. – histocrat Mar 22 at 17:09
1  
You can use (0...c) for a range that excludes c. – histocrat Mar 22 at 17:12
    
@histocrat Yes, it should be O(2n) which is O(n) – Not that Charles Mar 22 at 17:14

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]
share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Perl 6, 43 bytes

I think this is O(n)

{@^a.first(*>max @a[^floor @a/e])//@a[*-1]}
share|improve this answer

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))
share|improve this answer
    
Welcome to PPCG! You can comma separate your imports. Also, you don't need to generate the array yourself, so you can remove that portion of the code (simply have the array as a parameter to the function) – Nathan Merrill Mar 23 at 21:11
    
@NathanMerrill Yeah, I was thinking of doing that, but then I thought that you wouldn't really like it, but now that I know that really does not matter, I will edit my answer. Also, thanks for the tip about comma separating my imports. I had totally forgotten about that! – R. Kap Mar 23 at 21:19
    
Other tips: You have lots of unneeded whitespace (after commas, between equals signs. You don't need a print statement at the end either. – Nathan Merrill Mar 23 at 21:23
    
@NathanMerrill Thanks for the tips! I will keep those in mind as I do more code-golfing! :) – R. Kap Mar 23 at 21:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.