Несколько месяцев назад у меня было собеседование с хедж-фондом в Нью-Йорке, и, к сожалению, я не получил предложения о стажировке в качестве инженера по данным / программному обеспечению. (Они также попросили, чтобы решение было на Python.)
Я в значительной степени облажался с первой задачей собеседования ...
Вопрос: Учитывая строку из миллиона чисел (например, Pi), напишите функцию / программу, которая возвращает все повторяющиеся трехзначные числа и количество повторений больше 1
Например: если строка была: 123412345123456
то функция / программа вернет:
123 - 3 times
234 - 3 times
345 - 2 times
Они не дали мне решения после того, как я провалил собеседование, но они сказали мне, что временная сложность решения была постоянной 1000, поскольку все возможные результаты находятся между:
000 -> 999
Теперь, когда я думаю об этом, я не думаю, что можно придумать алгоритм постоянного времени. Это?
источник
They did not give me the solution after I failed the interview, but they did tell me that the time complexity for the solution was constant of 1000 since all the possible outcomes are between: 000 --> 999
Вероятно, это был настоящий тест. Чтобы посмотреть, сможете ли вы доказать им, почему это невозможно, и показать им правильную минимальную временную сложность.Ответы:
Вы легко отделались, вы, вероятно , не хотите работать в хедж-фонде, где кванты не понимают базовых алгоритмов :-)
Там нет не способа обработать произвольно размер структуру данных в
O(1)
случае, так как в этом случае, вы должны посетить каждый элемент , по крайней мере один раз. Лучше вы можете надеяться на то ,O(n)
в этом случае, когдаn
это длина строки.Мне кажется, вы могли произвести на них впечатление разными способами.
Во- первых, сообщив им , что это не возможно сделать это
O(1)
, если вы не использовать «подозреваемый» рассуждения , приведенные выше.Во-вторых, продемонстрировав свои элитные навыки, предоставив код Pythonic, например:
inpStr = '123412345123456' # O(1) array creation. freq = [0] * 1000 # O(n) string processing. for val in [int(inpStr[pos:pos+3]) for pos in range(len(inpStr) - 2)]: freq[val] += 1 # O(1) output of relevant array values. print ([(num, freq[num]) for num in range(1000) if freq[num] > 1])
Это выводит:
[(123, 3), (234, 3), (345, 2)]
хотя вы, конечно, можете изменить выходной формат на все, что захотите.
И, наконец, сообщив им, что почти наверняка нет проблем с
O(n)
решением, поскольку приведенный выше код предоставляет результаты для строки из одного миллиона цифр менее чем за полсекунды. Кажется, что он также масштабируется довольно линейно, поскольку строка из 10 000 000 символов занимает 3,5 секунды, а строка из 100 000 000 символов - 36 секунд.И, если им нужно что-то получше, есть способы распараллелить подобные вещи, которые могут значительно ускорить это.
Конечно, не в рамках одного интерпретатора Python из-за GIL, но вы можете разделить строку на что-то вроде (
vv
для правильной обработки граничных областей требуется перекрытие, обозначенное значком):vv 123412 vv 123451 5123456
Вы можете разделить их на отдельных рабочих, а затем объединить результаты.
Разделение входных данных и объединение выходных данных может затопить любую экономию небольшими строками (и, возможно, даже строками из миллионов цифр), но для гораздо больших наборов данных это вполне может иметь значение. Моя обычная мантра «измеряйте, а не угадайте» , конечно, применима здесь.
Эта мантра также применима к другим возможностям, таким как полный обход Python и использование другого языка, который может быть быстрее.
Например, следующий код C, работающий на том же оборудовании, что и предыдущий код Python, обрабатывает сто миллионов цифр за 0,6 секунды, примерно столько же времени, сколько код Python обработал один миллион. Другими словами, намного быстрее:
#include <stdio.h> #include <string.h> int main(void) { static char inpStr[100000000+1]; static int freq[1000]; // Set up test data. memset(inpStr, '1', sizeof(inpStr)); inpStr[sizeof(inpStr)-1] = '\0'; // Need at least three digits to do anything useful. if (strlen(inpStr) <= 2) return 0; // Get initial feed from first two digits, process others. int val = (inpStr[0] - '0') * 10 + inpStr[1] - '0'; char *inpPtr = &(inpStr[2]); while (*inpPtr != '\0') { // Remove hundreds, add next digit as units, adjust table. val = (val % 100) * 10 + *inpPtr++ - '0'; freq[val]++; } // Output (relevant part of) table. for (int i = 0; i < 1000; ++i) if (freq[i] > 1) printf("%3d -> %d\n", i, freq[i]); return 0; }
источник
O(1)
являетсяn
фиксированным или ограниченным.N
. Если вы разделите его на две части в позицииN/2
, вам все равно придется учитывать тот факт, что вы можете пропустить действительное трехзначное совпадение на «границе», в концеstring1
и в началеstring2
. Таким образом, вам нужно проверять совпадения междуstring1[N/2-2]
иstring2[2]
(с использованием индекса с отсчетом от нуля) и т. Д. В этом суть.val -= 100 * (d[i]-'0');
чтобы отбросить первую цифру.val = 10*val + d[i+2]-'0'
для накопления новой наименее значащей цифры (обычная строка-> целочисленный синтаксический анализ).val % 100
возможно, не ужасно, но только если100
это константа времени компиляции, поэтому она не использует реальное разделение HW.Постоянное время невозможно. Все 1 миллион цифр необходимо просмотреть хотя бы один раз, так что это временная сложность O (n), где n = 1 миллион в данном случае.
Для простого решения O (n) создайте массив размером 1000, который представляет количество вхождений каждого возможного трехзначного числа. Переходите на 1 цифру за раз, первый индекс == 0, последний индекс == 999997 и увеличивайте массив [3-значное число], чтобы создать гистограмму (количество вхождений для каждого возможного 3-значного числа). Затем выведите содержимое массива с counts> 1.
источник
x-'0'
шаблон недействителен в Python, это C-ism (где символы - целые числа).Миллион мало для ответа, который я даю ниже. Ожидая только того, что вы должны иметь возможность запустить решение на собеседовании без паузы, тогда следующее работает менее чем за две секунды и дает требуемый результат:
from collections import Counter def triple_counter(s): c = Counter(s[n-3: n] for n in range(3, len(s))) for tri, n in c.most_common(): if n > 1: print('%s - %i times.' % (tri, n)) else: break if __name__ == '__main__': import random s = ''.join(random.choice('0123456789') for _ in range(1_000_000)) triple_counter(s)
Надеюсь, что интервьюер будет искать использование стандартных библиотек collections.Counter class.
Версия с параллельным исполнением
Я написал сообщение в блоге об этом с дополнительными объяснениями.
источник
O(1)
.Простым решением O (n) было бы подсчитать каждое трехзначное число:
for nr in range(1000): cnt = text.count('%03d' % nr) if cnt > 1: print '%03d is found %d times' % (nr, cnt)
Это позволит перебрать все 1 миллион цифр 1000 раз.
Обход цифр только один раз:
counts = [0] * 1000 for idx in range(len(text)-2): counts[int(text[idx:idx+3])] += 1 for nr, cnt in enumerate(counts): if cnt > 1: print '%03d is found %d times' % (nr, cnt)
Время показывает, что итерация только один раз по индексу в два раза быстрее, чем использование
count
.источник
text.count()
?text.count
это сделано на высокоскоростном компилируемом языке (например, C), а не на медленном интерпретируемом цикле на уровне Python, да, есть скидка.count
неверен, так как он не учитывает перекрывающиеся шаблоны. Обратите внимание на то,'111'.count('11') == 1
когда мы этого ожидали2
.O(n)
решение» на самом деле связаноO(10**d * n)
сd
количеством разыскиваемых цифр иn
общей длиной строки. Второй -O(n)
время иO(10**d + n)
пространство.Вот реализация NumPy «консенсусного» алгоритма O (n): пройдитесь по всем триплетам и бинам по мере продвижения. Биннинг выполняется, когда мы встречаем, скажем, «385», добавляя единицу в bin [3, 8, 5], что является операцией O (1). Бункеры расположены в виде
10x10x10
куба. Поскольку биннинг полностью векторизован, в коде нет цикла.def setup_data(n): import random digits = "0123456789" return dict(text = ''.join(random.choice(digits) for i in range(n))) def f_np(text): # Get the data into NumPy import numpy as np a = np.frombuffer(bytes(text, 'utf8'), dtype=np.uint8) - ord('0') # Rolling triplets a3 = np.lib.stride_tricks.as_strided(a, (3, a.size-2), 2*a.strides) bins = np.zeros((10, 10, 10), dtype=int) # Next line performs O(n) binning np.add.at(bins, tuple(a3), 1) # Filtering is left as an exercise return bins.ravel() def f_py(text): counts = [0] * 1000 for idx in range(len(text)-2): counts[int(text[idx:idx+3])] += 1 return counts import numpy as np import types from timeit import timeit for n in (10, 1000, 1000000): data = setup_data(n) ref = f_np(**data) print(f'n = {n}') for name, func in list(globals().items()): if not name.startswith('f_') or not isinstance(func, types.FunctionType): continue try: assert np.all(ref == func(**data)) print("{:16s}{:16.8f} ms".format(name[2:], timeit( 'f(**data)', globals={'f':func, 'data':data}, number=10)*100)) except: print("{:16s} apparently crashed".format(name[2:]))
Неудивительно, что NumPy немного быстрее, чем решение @ Daniel на чистом Python для больших наборов данных. Пример вывода:
# n = 10 # np 0.03481400 ms # py 0.00669330 ms # n = 1000 # np 0.11215360 ms # py 0.34836530 ms # n = 1000000 # np 82.46765980 ms # py 360.51235450 ms
источник
ndarray
s, основной тип numpy, посвящен эффективному хранению, обработке и индексации многомерных массивов чисел. Иногда вы можете сбрить несколько% путем выравнивания, но в этом случае выполнение 100 x [0] + 10 x [1] + x [2] вручную не принесет вам много пользы. Я использовал тот, который, как сказал @Daniel, был быстрее, вы можете сами проверить код теста.Я бы решил проблему следующим образом:
def find_numbers(str_num): final_dict = {} buffer = {} for idx in range(len(str_num) - 3): num = int(str_num[idx:idx + 3]) if num not in buffer: buffer[num] = 0 buffer[num] += 1 if buffer[num] > 1: final_dict[num] = buffer[num] return final_dict
Применительно к строке вашего примера это дает:
>>> find_numbers("123412345123456") {345: 2, 234: 3, 123: 3}
Это решение работает за O (n), где n - длина предоставленной строки, и, я думаю, это лучшее, что вы можете получить.
источник
Counter
. Вам не нуженfinal_dict
, и вам не нужно обновлять его на каждой итерации.Насколько я понимаю, у вас не может быть решения за постоянное время. Потребуется хотя бы один проход над числом из миллиона цифр (при условии, что это строка). У вас может быть 3-значная скользящая итерация по цифрам числа с миллионной длиной и увеличить значение хэш-ключа на 1, если он уже существует, или создать новый хэш-ключ (инициализированный значением 1), если он еще не существует в словарь.
Код будет выглядеть примерно так:
def calc_repeating_digits(number): hash = {} for i in range(len(str(number))-2): current_three_digits = number[i:i+3] if current_three_digits in hash.keys(): hash[current_three_digits] += 1 else: hash[current_three_digits] = 1 return hash
Вы можете фильтровать до ключей, у которых значение элемента больше 1.
источник
Как упоминалось в другом ответе, вы не можете выполнять этот алгоритм за постоянное время, потому что вы должны смотреть как минимум n цифр. Линейное время - это самое быстрое, что вы можете получить.
Однако алгоритм может быть выполнен в пространстве O (1) . Вам нужно хранить только счетчики каждого трехзначного числа, поэтому вам нужен массив из 1000 записей. Затем вы можете передать номер в потоковом режиме.
Я предполагаю, что либо интервьюер оговорился, когда давал вам решение, либо вы не услышали «постоянное время», когда они сказали «постоянное пространство».
источник
O(10**d)
дополнительное пространство, гдеd
- количество десятичных цифр, которые вы ищете.Вот мой ответ:
from timeit import timeit from collections import Counter import types import random def setup_data(n): digits = "0123456789" return dict(text = ''.join(random.choice(digits) for i in range(n))) def f_counter(text): c = Counter() for i in range(len(text)-2): ss = text[i:i+3] c.update([ss]) return (i for i in c.items() if i[1] > 1) def f_dict(text): d = {} for i in range(len(text)-2): ss = text[i:i+3] if ss not in d: d[ss] = 0 d[ss] += 1 return ((i, d[i]) for i in d if d[i] > 1) def f_array(text): a = [[[0 for _ in range(10)] for _ in range(10)] for _ in range(10)] for n in range(len(text)-2): i, j, k = (int(ss) for ss in text[n:n+3]) a[i][j][k] += 1 for i, b in enumerate(a): for j, c in enumerate(b): for k, d in enumerate(c): if d > 1: yield (f'{i}{j}{k}', d) for n in (1E1, 1E3, 1E6): n = int(n) data = setup_data(n) print(f'n = {n}') results = {} for name, func in list(globals().items()): if not name.startswith('f_') or not isinstance(func, types.FunctionType): continue print("{:16s}{:16.8f} ms".format(name[2:], timeit( 'results[name] = f(**data)', globals={'f':func, 'data':data, 'results':results, 'name':name}, number=10)*100)) for r in results: print('{:10}: {}'.format(r, sorted(list(results[r]))[:5]))
Метод поиска в массиве очень быстр (даже быстрее, чем метод numpy @ paul-panzer!). Конечно, это читерство, поскольку технически он не закончен после завершения, потому что он возвращает генератор. Также нет необходимости проверять каждую итерацию, существует ли значение уже, что, вероятно, очень поможет.
n = 10 counter 0.10595780 ms dict 0.01070654 ms array 0.00135370 ms f_counter : [] f_dict : [] f_array : [] n = 1000 counter 2.89462101 ms dict 0.40434612 ms array 0.00073838 ms f_counter : [('008', 2), ('009', 3), ('010', 2), ('016', 2), ('017', 2)] f_dict : [('008', 2), ('009', 3), ('010', 2), ('016', 2), ('017', 2)] f_array : [('008', 2), ('009', 3), ('010', 2), ('016', 2), ('017', 2)] n = 1000000 counter 2849.00500992 ms dict 438.44007806 ms array 0.00135370 ms f_counter : [('000', 1058), ('001', 943), ('002', 1030), ('003', 982), ('004', 1042)] f_dict : [('000', 1058), ('001', 943), ('002', 1030), ('003', 982), ('004', 1042)] f_array : [('000', 1058), ('001', 943), ('002', 1030), ('003', 982), ('004', 1042)]
источник
Counters
не используются таким образом. При правильном использовании они становятся самым быстрым вариантом на вашем примере. Если вы используетеtimeit
список со списком генератора, ваш метод будет медленнее, чемCounter
илиdict
. Смотрите здесь .f_array
могли бы быть быстрее, если бы сначала преобразовали каждый char в int :,ints = [int(c) for c in text]
а затем использовалиi, j, k = ints[n:n+3]
.Изображение как ответ:
Похоже на раздвижное окно.
источник
Вот мое решение:
from collections import defaultdict string = "103264685134845354863" d = defaultdict(int) for elt in range(len(string)-2): d[string[elt:elt+3]] += 1 d = {key: d[key] for key in d.keys() if d[key] > 1}
Приложив немного творчества в цикл for (и дополнительный список поиска, например, с True / False / None), вы сможете избавиться от последней строки, так как вы хотите создать только ключи в dict, которые мы посещали один раз до этого момента. . Надеюсь, это поможет :)
источник
-Теллинг с точки зрения C. -Вы можете иметь массив int 3-d results [10] [10] [10]; -Перейти из 0-го места в n-4-е место, где n - размер массива строк. -На каждом месте проверьте текущее, следующее и следующее следующее. -Увеличить cntr как resutls [текущий] [следующий] [следующий следующий] ++; -Печать значения
results[1][2][3] results[2][3][4] results[3][4][5] results[4][5][6] results[5][6][7] results[6][7][8] results[7][8][9]
-Это время O (n), никаких сравнений нет. -Вы можете запускать здесь некоторые параллельные вещи, разбивая массив и вычисляя совпадения по разделам.
источник
inputStr = '123456123138276237284287434628736482376487234682734682736487263482736487236482634' count = {} for i in range(len(inputStr) - 2): subNum = int(inputStr[i:i+3]) if subNum not in count: count[subNum] = 1 else: count[subNum] += 1 print count
источник