13
\$\begingroup\$

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ What e should be used? \$\endgroup\$ – afuous Mar 22 '16 at 16:52
  • 2
    \$\begingroup\$ @voidpigeon I presume it's en.wikipedia.org/wiki/E_(mathematical_constant) \$\endgroup\$ – Doorknob Mar 22 '16 at 16:53
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Doorknob Mar 22 '16 at 17:10
  • 1
    \$\begingroup\$ 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) \$\endgroup\$ – Mego Mar 22 '16 at 18:19
  • 1
    \$\begingroup\$ Note: ` 1/e percent of the time.` would be really bad. It's a probabilty of 1/e, that is roughly 37% of times \$\endgroup\$ – edc65 Mar 23 '16 at 11:28

11 Answers 11

4
\$\begingroup\$

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).
\$\endgroup\$
3
\$\begingroup\$

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

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
};
\$\endgroup\$
2
\$\begingroup\$

MATL, 27 25 23 bytes

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

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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>

\$\endgroup\$
1
\$\begingroup\$

Ruby, 64 bytes

->a{m=a[0...c=a.size/Math::E].max
a[c..-1].find{|n|n>m}||a[-1]}
\$\endgroup\$
  • 2
    \$\begingroup\$ @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. \$\endgroup\$ – afuous Mar 22 '16 at 17:05
  • \$\begingroup\$ Ah, that's right. I misread and thought you were finding the max in each iteration. \$\endgroup\$ – Doorknob Mar 22 '16 at 17:07
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – histocrat Mar 22 '16 at 17:09
  • 1
    \$\begingroup\$ You can use (0...c) for a range that excludes c. \$\endgroup\$ – histocrat Mar 22 '16 at 17:12
  • \$\begingroup\$ @histocrat Yes, it should be O(2n) which is O(n) \$\endgroup\$ – Not that Charles Mar 22 '16 at 17:14
1
\$\begingroup\$

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]
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Perl 6, 43 bytes

I think this is O(n)

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

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))
\$\endgroup\$
  • \$\begingroup\$ 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) \$\endgroup\$ – Nathan Merrill Mar 23 '16 at 21:11
  • \$\begingroup\$ @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! \$\endgroup\$ – R. Kap Mar 23 '16 at 21:19
  • \$\begingroup\$ Other tips: You have lots of unneeded whitespace (after commas, between equals signs. You don't need a print statement at the end either. \$\endgroup\$ – Nathan Merrill Mar 23 '16 at 21:23
  • \$\begingroup\$ @NathanMerrill Thanks for the tips! I will keep those in mind as I do more code-golfing! :) \$\endgroup\$ – R. Kap Mar 23 '16 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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