Решить проблему секретаря

13

Секретарь Проблема известная проблема описана как таким образом:

  1. Вам нужен новый секретарь
  2. У вас есть N кандидатов, с которыми вы можете взять интервью по одному
  3. Вы можете оценить каждого кандидата после собеседования. Ваша система подсчета очков никогда не даст двум претендентам одинаковый балл
  4. После собеседования с заявителем вы должны сразу дать «да» или «нет»
  5. Вы хотите заявителя с наивысшим баллом

Решение состоит в том, чтобы взять интервью у первых floor(N/e)заявителей, а затем принять первого заявителя, который имеет более высокий балл, чем все предыдущие заявители. Если ни один из заявителей не выше, верните последнего заявителя. Интересно, что это дает лучшему заявителю 1/eпроцент времени. eотносится к числу Эйлера . Чтобы получить значение e, вы можете использовать встроенный код logили жестко закодировать его как минимум до 5 десятичных знаков.

Входные данные:

Непустой массив уникальных целых неотрицательных чисел не больше 2^31-1.

Выход:

Целое число, представляющее выбранного кандидата. Чтобы быть понятным, алгоритм:

  1. Найдите максимальный элемент в первых floor(N/e)элементах массива.
  2. Выполните итерацию по оставшимся элементам и верните первый элемент, который превышает максимум, найденный на шаге 1.
  3. Если ни один из элементов не выше, чем вернуть последний элемент.

Например, скажем, ваш массив был [2,7,4,3,9,20], так N = 6и floor(N/e) = 2. Первые 2 элемента массива есть [2,7]. Макс [2,7]IS 7. Остальные элементы есть [4,3,9,20]. Первый элемент, который больше, чем 7есть 9, поэтому мы возвращаемся 9.

Тестовые случаи:

[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

Ваше решение должно быть O(n), где nдлина массива. Если у вашего языка есть встроенная функция, которая находит максимум массива, вы можете предположить, что функция принимает O(n)(и, надеюсь, это так).

Применяются стандартные лазейки, и это , поэтому сделайте кратчайший ответ на своем любимом языке!

Натан Меррилл
источник
1
Что eследует использовать?
afous
2
@voidpigeon Я предполагаю, что это en.wikipedia.org/wiki/E_(matumatic_constant)
Ручка двери
1
Ах, теперь я понимаю, как работает алгоритм. Я думал, что ваш второй абзац означает, что вы никогда не проводите собеседование с кандидатами после выступления (н / д) вообще.
Ручка двери
1
Я специально спросил, потому что в некоторых языках определить переменную с 5 десятичными точками точности короче, чем фактически использовать встроенную функцию e(например, Python, где e=2.71828короче import math;math.E)
Mego
1
Примечание: «1 / е процентов времени» было бы действительно плохо. Вероятность 1 / е, примерно в 37% случаев
edc65

Ответы:

4

Желе, 13 байт

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

Определенно алгоритм O (n) , надеюсь, реализация O (n) . Попробуйте онлайн!

Как это устроено

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).
Деннис
источник
3

CJam, 20 байт

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

Работает аналогично предложению Денниса.

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
Симмонс
источник
$W=не работает в линейном времени.
Деннис
Ух ты, ты прав. Есть ли лучший способ найти максимум в CJam, который, как вы знаете, делает?
Симмонс
1
:e>(уменьшите по максимуму)
Деннис
@ Деннис Спасибо!
Симмонс
2

Джава, 128 118 байт

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;}

Отступ:

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
};
CAD97
источник
2

JavaScript (ES6) 64

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

Меньше гольфа

(
 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
)

Тестовое задание

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>

edc65
источник
1

Рубин, 64 байта

->a{m=a[0...c=a.size/Math::E].max
a[c..-1].find{|n|n>m}||a[-1]}
afuous
источник
2
@Doorknob Обходит элементы первого этажа (N / e) один раз, чтобы найти максимум, а затем перебирает остальную часть списка в худшем случае, сравнивая каждый элемент с максимумом. Существует только одно сравнение на элемент в обеих частях.
Афо
Ах, это правильно. Я неправильно прочитал и подумал, что вы находите максимум в каждой итерации.
Дверная ручка
1
На самом деле, я думаю, что все равно O (n), если вы просто делаете a.findна втором шаге, хотя, очевидно, это намного менее эффективно.
гистократ
1
Вы можете использовать (0...c)для диапазона, который исключает c.
гистократ
@histocrat Да, это должен быть O (2n), то есть O (n)
не то, чтобы Charles
1

PARI / GP , 70 байт

Это может иметь проблемы с более старыми версиями gp при наличии синглтона, но это работает по крайней мере с версии 18487.

v->m=vecmax(v[1..t=#v\exp(1)]);for(i=t+1,#v,v[i]>m&&return(v[i]));v[#v]
Чарльз
источник
1

JavaScript (ES6), 79 байт

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

Работает, потому что findIndexвозвращает -1при ошибке, но a.slice(-1)[0]возвращает последний элемент массива по желанию.

Нил
источник
1

Python 2, 87 байт

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

Пользователь вводит массив в виде списка с квадратными скобками и запятыми. Python 2input()Команда здесь удобна.

Независимо от того, прекращаем ли мы процесс раньше или нет, мы нанимаем последнего человека, который получил интервью.

mathmandan
источник
1

Perl 6, 43 байта

Я думаю, что это O (N)

{@^a.first(*>max @a[^floor @a/e])//@a[*-1]}
Клавиатурный
источник
1

Python 3.5; 110 байт:

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])

По сути, вышеприведенное делает то, что в первую очередь он принимает предоставленный массив «h», если он включает более 5 элементов (на данный момент ...), находит максимальное значение в первом (длина массива (len (h) )) / Число Эйлера (до 5 десятичных знаков)) элементов этого массива, а затем возвращает это значение как «k». Кроме того, «n» является максимальным значением в остальной части массива. Наконец, значение, возвращаемое функцией, является максимальным значением в массиве, содержащем как «k», так и «n».

Примечание: max()функция Python - O (n) сложность.

Ниже приведена более читаемая версия кода, не относящаяся к коду для гольфа , с произвольным уникальным массивом из 10 элементов, подтверждающим его работоспособность:

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))
Р. Кап
источник
Добро пожаловать в PPCG! Вы можете разделить ваш импорт запятыми. Кроме того, вам не нужно генерировать массив самостоятельно, поэтому вы можете удалить эту часть кода (просто используйте массив в качестве параметра для функции)
Nathan Merrill
@NathanMerrill Да, я думал об этом, но потом подумал, что тебе это не понравится, но теперь, когда я знаю, что это действительно не имеет значения, я отредактирую свой ответ. Кроме того, спасибо за подсказку о запятой, разделяющей мой импорт. Я полностью забыл об этом!
Р. Кап
Другие советы: у вас есть много ненужных пробелов (после запятых, между знаками равенства. В конце вам также не нужно печатать заявление.
Натан Меррилл
@NathanMerrill Спасибо за советы! Я буду помнить это, поскольку я делаю больше игры в гольф кода! :)
Р. Кап