Вот один из моих интервью. Учитывая массив из N элементов и где элемент выглядит ровно N/2, а остальные элементы N/2 уникальные. Как бы вы нашли элемент с лучшим временем выполнения?
Помните, что элементы не отсортированы, и вы можете предположить, что N четно. Например,
input array [] = { 10, 2, 3, 10, 1, 4, 10, 5, 10, 10 }
Итак, здесь 10 появляется в 5 раз больше, чем N/2.
Я знаю решение с O (n) временем выполнения. Но все еще с нетерпением ожидаем лучшего решения с O (log n).
Существует постоянное временное решение, если вы готовы принять небольшую вероятность ошибки. Произвольно отбирает два значения из массива, если они одинаковы, вы нашли нужное значение. На каждом шаге у вас есть вероятность не заканчивать 0.75. И поскольку для каждого epsilon существует такое n, что (3/4) ^ n < eps, мы можем пробовать не более n раз и возвращать ошибку, если мы не нашли совпадающую пару.
Также отметим, что если мы сохраняем выборку до тех пор, пока не найдем пару, ожидаемое время работы будет постоянным, но наихудшее время работы не ограничено.
Вот моя попытка доказать, почему это невозможно сделать за меньший доступ к массиву O (n) (для худшего случая, который, безусловно, является единственным интересным случаем в этом примере):
Предположим, что существует алгоритм log() наихудшего случая. Этот алгоритм обращается к массиву не более log (n) раз. Поскольку он не может делать никаких предположений о том, какие элементы есть, позвольте мне выбрать, какие элементы log (n) он видит. Я выберу его первый элемент log (n). Он еще не нашел дубликат, и все еще существуют n/2 - log (n) уникальные элементы, чтобы я мог его кормить, если это необходимо. На самом деле, я не могу заставить его подавать дублированное число, пока он не прочитает n/2 элемента. Поэтому такой алгоритм не может существовать.
С чисто интуитивной точки зрения это просто кажется невозможным. Log (4 миллиарда) - 32. Таким образом, с массивом из 4 миллиардов номеров, из которых 2 миллиарда уникальны, в определенном порядке, существует способ найти дублированный элемент, только проверив 32 элемента?
Я думаю, вам просто нужно проанализировать массив, сохраняя отставание от двух элементов. Поскольку N/2 равны, а остальное гарантировано быть различным, должно быть одно место я в вашем массиве, где
a[i] == a[i-1] OR a[i] == a[i-2]
повторяйте один раз через свой массив, и у вас будет сложность примерно 2 * N, которая должна быть хорошо внутри O (N).
Этот ответ несколько похож на ответ Ганеша М и Дуги, но я думаю немного проще.
Вы не можете сделать это в сублинейное время, потому что вам нужно прочитать массив. Для обработки массива из миллиона записей в логарифмическом времени потребуется только чтение элементов ~ 20 (log2) - явно невозможно. В конце концов, если вы предполагаете, что первый найденный дубликат повторяется N/2 раза, он все еще O (n), потому что вам может потребоваться найти 500 001 элемент, чтобы найти дубликат.
Вы можете сделать это в O (n), если вы считаете, что целые числа неотрицательны. Это происходит так (псевдо-Java):
int repeatedNumber = -1; // sentinel value
int count = 0;
BitSet bits = new BigSet(); // this bitset needs to have 2^31 bits, roughly 2.1 billion
boolean duplicate = false;
for (int i : elements) {
if (bits[i].isSet()) {
if (repeatedNumber == -1) {
repeatedNumber = i;
count = 1;
} else if (i == repeatedNumber) {
count++;
} else {
System.out.println("Array has more than one repeated element");
duplicate = true;
break;
}
} else {
bits[i].set();
}
}
if (!duplicate && repeatedNumber != -1 && count == elements.length/2) {
System.out.println(repeatedNumber + " occurred " + count + " times. The rest of the elements are unique");
} else {
System.out.println("Not true");
}
Аналогичный метод используется для сортировки массива уникальных целых чисел в O (n) (сортировка по методу radix).
Для наихудшего детерминированного поведения O (N) является правильным (я уже видел более одного доказательства в предыдущих ответах).
Тем не менее, современная алгоритмическая теория не касается только худшего поведения (почему существует так много других больших вещей, помимо большого О, хотя ленивые программисты в спешке часто используют big-O, даже когда то, что они иметь в виду, ближе к big-theta OR big-omega;-), а не только с детерминизмом (совпадение с критерием примитивности Миллера-Рабина...;).Любая случайная выборка из K < N элементов не будет отображать дубликатов с вероятностью, что < 2 ** K - легко и быстро сводится к по существу настолько низким, насколько вы хотите, независимо от того, что N (например, вы могли бы уменьшить его до меньшей вероятности того, что случайный космический луч будет случайно и необнаружимо перевернуться в вашей памяти; ) - это наблюдение вряд ли требует творчества Рабина и Миллера, чтобы найти их вероятностный подход к первому тестированию; -).
Это сделало бы довольно паршивый вопрос интервью. Подобные менее объективные вопросы часто возникают, часто неверно, и часто ошибочно запоминаются неудачными кандидатами. Например, типичный вопрос может быть задан массивом из N элементов, не зная, есть ли элемент большинства, чтобы определить, есть ли он, а какой он есть, в O (N) времени и O (1) вспомогательный space (так что вы не можете просто настроить хеш-таблицу или что-то, чтобы считать вхождения разных значений). "Moore Voting Approach" - хорошее решение (возможно, лучшее) для этого достойного интервьюирования.
Еще одна интересная вариация: что, если у вас есть 10**18 64-разрядные номера (общая стоимость 8 терабайт данных, скажем, на большой таблице или клоне), и столько же машин, сколько вы хотите, каждый с примерно 4 ГБ ОЗУ на довольно быстрой локальной сети, скажем, что существенно лучше, чем GB ethernet - как вы оштрафовали проблему в условиях тех? Что делать, если вам нужно использовать mapreduce/hadoop? Что делать, если вы свободны создавать свою собственную выделенную инфраструктуру только для этой проблемы - можете ли вы получить лучшую производительность, чем при использовании mapreduce? Насколько лучше, при гранулярности оценки обратного конверта? Я не знаю ни одного опубликованного алгоритма для ЭТОГО варианта, так что это может быть отличный тест, если вы хотите проверить общий объект кандидата с высокораспределенными подходами к вычислению tera-scale...
Мой ответ был,
Время выполнения - O (N)
Пусть множество S - множество, содержащее N элементов. Это объединение двух множеств: p, которое содержит символ & alpha; повторение N/2 раза и q, которое содержит N/2 уникальных символа & omega; 1.. & omega; n/2. S = p & cup; кв.
Предположим, что существует алгоритм, который может обнаружить ваш дублированный номер в log (n) сравнениях в наихудшем случае для всех N > 2. В худшем случае означает, что там не существует любое подмножество r & sub; S такой, что | r | = log 2 N где & alpha; &не в; г.
Однако, поскольку S = p & cup; q, существуют | p | много элементов & ne; &альфа; в S. | p | = N/2, поэтому & forall; N/2 такой, что N/2 & ge; log 2 N, должно существовать хотя бы одно множество r & sub; S такой, что | r | = log 2 N и & alpha; &не в; р. Это относится к любому N & ge; 3. Это противоречит предположению выше, поэтому не может быть такого алгоритма.
QED.
Чтобы сделать это меньше, чем O (n), вам не нужно будет считывать все числа.
Если вы знаете, что есть значение, которое удовлетворяет отношениям, тогда вы можете просто попробовать небольшое подмножество показать, что только одно число появляется достаточно времени, чтобы встретить связь. Вы должны были бы предположить, что значения достаточно равномерно распределены.
Изменить. вам нужно было бы прочитать n/2, чтобы доказать, что такое число существует, но если вы знали, что число существует и только хочет его найти, вы можете прочитать образцы sqrt (n)
Ответ прост и может быть достигнут в худшем случае (n/2 + 1) сравнения
Сравнить парные первые (n-2) числа, то есть сравнение nos. при 0 и 1, затем 2 и 3 и т.д.... всего n/2 -1 сравнений. Если мы находим одинаковые числа в любом из приведенных выше сравнений, мы имеем повторное число... else:
Возьмите любое из двух последних оставшихся чисел (скажем, второе последнее, что я взял) и сравните его с числами во второй последней паре. Если произойдет совпадение... второй последний нет. является повторным, а последний - повторенным... во всех 2 сравнениях.
Всего сравнений = n/2 - 1 + 2 = n/2 + 1 (наихудший случай) Я не думаю, что есть какой-либо метод O (log n) для достижения этого
Довольно просто видеть, что алгоритм O (log n) не существует. Ясно, что вам нужно взглянуть на элементы массива, чтобы выяснить, что представляет собой повторяющийся элемент, но независимо от того, какой порядок вы выбираете для просмотра элементов, элементы первого этажа (n/2), которые вы смотрите, могут быть уникальными. Вам просто просто не повезло. Если это произойдет, у вас не будет никакого способа узнать, что было повторным элементом. Поскольку ни один алгоритм, который использует меньше, чем пол (n/2) ссылок на массивы или меньше на каждом прогоне, будет работать, нет никакого сублинейного алгоритма.
Если я правильно понимаю проблему: все, что мы знаем о массиве, это длина и имеет (N/2) +1 уникальные элементы, где 1 элемент повторяется N/2 раза (в определенном порядке).
Я думаю, что для этого решения существует жесткий предел O (N), поскольку вы не можете утверждать (для общего массива), что вы нашли номер, не найдя хотя бы 2 одинакового числа. Я не думаю, что существует поиск неупорядоченного массива, который может обнаружить дубликат в O (logN) (пожалуйста, поправьте меня, если я ошибаюсь). Вам всегда нужно прочитать хотя бы N/2 +1 элементов в худшем случае.
Отправляя свое решение из комментария к версии Ganesh, я могу отформатировать его:
for (i=0; i<N-2; i+=3) {
if a[i] == a[1+1] || a[i] == a[i+2] return a[i];
if a[i+1] == a[i+2] return a[i+1];
}
return a[N-1]; // for very small N
Вероятность выигрыша после 1-й итерации: 50%
Вероятность выигрыша после 2 итераций: 75%
Etc.
В худшем случае O (n) время O (1) пробел.
Обратите внимание, что после N/4 итераций вы использовали все уникальные номера N/2, поэтому этот цикл никогда не будет проходить через более 3/4 массива, если он указан как указано.
Предположим, что у вас есть такой алгоритм python:
import math
import random
def find_duplicate(arr, gap):
cost, reps = 0, 0
while True:
indexes = sorted((random.randint(0,len(arr)-i-1) for i in xrange(gap)), reverse=True)
selection = [arr.pop(i) for i in indexes]
selection_set = set(selection)
cost += len(selection)
reps += 1
if len(selection) > len(selection_set):
return cost, reps
Идея состоит в том, что arr - это ваш набор значений, а gap - это база данных-2 размера. Каждый раз, когда вы выбираете элементы gap и видите, есть ли дублированные значения. Если это так, верните стоимость (в счетчике рассмотренных элементов) и количество итераций (где вы просматриваете элементы log2 (размер) на итерацию). В противном случае просмотрите другой пробел -размерный набор.
Проблема с бенчмаркингом этого алгоритма заключается в том, что создание данных каждый раз через цикл и изменение данных является дорогостоящим, предполагая большой объем данных. (Вначале я делал 1 000 000 элементов с 10 000 000 итераций.)
Итак, давайте сведем к эквивалентной проблеме. Данные передаются в виде n/2 уникальных элементов и n/2 повторяющихся элементов. Алгоритм выбирает случайные индексы элементов log2 (n) и проверяет дубликаты. Теперь нам даже не нужно создавать данные и удалять проверенные элементы: мы можем просто проверить, есть ли у нас два или более индексов над половинной точкой. Выберите индексы gap, проверьте на 2 или более за половину точки: верните, если найдено, в противном случае повторите.
import math
import random
def find_duplicate(total, half, gap):
cost, reps = 0, 0
while True:
indexes = [random.randint(0,total-i-1) for i in range(gap)]
cost += gap
reps += 1
above_half = [i for i in indexes if i >= half]
if len(above_half) >= 2:
return cost, reps
else:
total -= len(indexes)
half -= (len(indexes) - len(above_half))
Теперь введите код следующим образом:
if __name__ == '__main__':
import sys
import collections
import datetime
for total in [2**i for i in range(5, 21)]:
half = total // 2
gap = int(math.ceil(math.log10(total) / math.log10(2)))
d = collections.defaultdict(int)
total_cost, total_reps = 0, 1000*1000*10
s = datetime.datetime.now()
for _ in xrange(total_reps):
cost, reps = find_duplicate(total, half, gap)
d[reps] += 1
total_cost += cost
e = datetime.datetime.now()
print "Elapsed: ", (e - s)
print "%d elements" % total
print "block size %d (log of # elements)" % gap
for k in sorted(d.keys()):
print k, d[k]
average_cost = float(total_cost) / float(total_reps)
average_logs = average_cost / gap
print "Total cost: ", total_cost
print "Average cost in accesses: %f" % average_cost
print "Average cost in logs: %f" % average_logs
print
Если вы попробуете этот тест, вы обнаружите, что количество раз, которое алгоритм должен выполнять несколько выборок, уменьшается с количеством элементов в данных. То есть средняя стоимость в журналах асимптотически приближается к 1.
elements accesses log-accesses
32 6.362279 1.272456
64 6.858437 1.143073
128 7.524225 1.074889
256 8.317139 1.039642
512 9.189112 1.021012
1024 10.112867 1.011287
2048 11.066819 1.006075
4096 12.038827 1.003236
8192 13.022343 1.001719
16384 14.013163 1.000940
32768 15.007320 1.000488
65536 16.004213 1.000263
131072 17.002441 1.000144
262144 18.001348 1.000075
524288 19.000775 1.000041
1048576 20.000428 1.000021
Теперь это аргумент для идеального алгоритма: log2 (n) в среднем случае? Может быть. Это, конечно, не так в худшем случае.
Кроме того, вам не нужно сразу выбирать элементы log2 (n). Вы можете выбрать 2 и проверить равенство (но в дегенеративном случае вы вообще не найдете дублирование) или проверьте любое другое число, большее для дублирования. На этом этапе все алгоритмы, которые выбирают элементы и проверяют дублирование, идентичны, варьируя только то, сколько они выбирают и как они идентифицируют дублирование.
Если вам говорят, что элемент, который вы ищете, является неповторимым, безусловно, самый быстрый способ сделать это - перебирать массив по мере того, как вы найдете два одинаковых, а затем вернете этот элемент и перестанете смотреть. В лучшем случае вам нужно искать половину массива.
Я думаю, что это O (n), поэтому я думаю, что это действительно не помогает.
Кажется слишком простым, поэтому я думаю, что я не понимаю проблему правильно.
Вот ответ Дон Джой в Ruby:
#!/usr/bin/ruby1.8
def find_repeated_number(a)
return nil unless a.size >= 3
(0..a.size - 3).each do |i|
[
[0, 1],
[0, 2],
[1, 2],
].each do |j1, j2|
return a[i + j1] if a[i + j1] == a[i + j2]
end
end
end
p find_repeated_number([1, 1, 2]) # => 1
p find_repeated_number([2, 3, 2]) # => 1
p find_repeated_number([4, 3, 3]) # => 1
О (п)
Алгоритм RepeatedElement(a, n)
while (true) do
{
i=Random() mod n+1; j=Random() mod n+1;
// i and j are random numbers in the range [1,n]
if ((i ≠ j) and a[i]=a[j])) then return;
}
Аналогично fooobar.com/questions/138534/....
Давайте сравним 3 элемента (3 операции сравнения), в худшем случае один и тот же элемент появится один раз. Таким образом, мы уменьшаем хвост на 3 и уменьшаем количество "одинаковых" элементов на единицу.
В последнем шаге (после k итераций) наш хвост будет содержать (n/2) - k "одинаковых" элементов. Пусть сравнивается длина хвоста.
С одной стороны, будет n-3k с другой стороны (n/2) - k + 1. Возможны последние неиспользуемые элементы.
n-3k = (n/2) - k + 1
k = 1/4 * (n-2)
После k итераций мы обязательно получим результат.
Число сравнений 3/4 * (n-2)
Прежде всего, он прошел мимо моего времени на кровать, и я должен знать лучше, чем публиковать публичный код, не пытаясь сначала, yada, yada. Надеюсь, критика, которую я получу, по крайней мере будет образовательной.: -)
Я считаю, что проблему можно переформулировать так: "Найти номер, который встречается более одного раза".
В абсолютном худшем случае нам нужно будет перебирать чуть более половины списка (1 + N/2), прежде чем мы найдем второй экземпляр не уникального числа.
Пример наихудшего случая: array [] = {1, 2, 3, 4, 5, 10, 10, 10, 10, 10}
В среднем, однако, нам нужно будет только итератировать 3 или 4 элемента, так как половина элементов будет содержать неповторимое число i.e примерно любое другое число.
Отличные примеры распространения:
Другими словами, даже если N = 1 миллион вам все равно нужно будет искать; в среднем, первые 3 или 4 элемента, прежде чем вы обнаружите дубликат.
Какая большая нотация O для фиксированной/постоянной времени выполнения, которая не увеличивается с помощью N?
код:
int foundAt = -1;
for (int i=0; (i<N) && (foundAt==-1); i++)
{
for (int j=i+1; j<N; j++)
{
if (array[i] == array[j])
{
foundAt = i;
break;
}
}
}
int uniqueNumber = array[foundAt];
Это плохой вопрос для интервью.
В основном из-за первого. Что вы ищете? Что кандидат должен придумать это решение O (log n), которое вы не знаете, существует? Если вы должны спросить StackOverflow, это то, что вы можете разумно ожидать от кандидата в интервью?
В отличие от ответов выше, существует решение с поведением наихудшего случая по запросу, O (log n) ВРЕМЯ РАБОТЫ. Проблема заключается не в том, чтобы найти решение с худшим случаем сравнения O (log N) (что невозможно), а для того, чтобы сделать это O (log N).
Если вы можете параллельно сравнивать N сравнений, решение является тривиальным делением и победой. Не очень практично в реальном мире, но это вопрос интервью, а не реальная проблема.
Обновление: я думаю, вы можете сделать это в постоянное время с O (N) процессорами