Ответ 1

Вы получили легкомысленно, вы, вероятно, не хотите работать в хедж-фонде, где кванты не понимают базовые алгоритмы: -)

Невозможно обработать структуру данных произвольного размера в O(1), если, как в этом случае, вам нужно посетить каждый элемент хотя бы один раз. Лучшее, на что вы можете надеяться, это O(n) в этом случае, где n - длина строки.

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

Мне кажется, вы могли бы произвести впечатление на них несколькими способами.

Во-первых, сообщив им, что это невозможно сделать в 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;
}

Ответ 2

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

Для простого решения O (n) создайте массив размером 1000, который представляет количество вхождений каждого возможного 3-значного числа. Продвиньте 1 цифру за раз, первый индекс == 0, последний индекс == 999997 и увеличите массив [3-значное число], чтобы создать гистограмму (количество вхождений для каждого возможного 3-значного числа). Затем выведите содержимое массива с counts > 1.

Ответ 3

Простым решением O (n) было бы подсчитать каждое трехзначное число:

for nr in range(1000):
    cnt = text.count('%03d' % nr)
    if cnt > 1:
        print '%03d is found %d times' % (nr, cnt)

Это будет поиск по всем миллионам 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.

Ответ 4

Миллион для ответа ниже. Ожидая только, что вы должны иметь возможность запускать решение в интервью без паузы, то следующее работает менее чем за две секунды и дает требуемый результат:

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)

Надеюсь, интервьюер будет искать использование стандартных коллекций библиотек. Класс.

Параллельная версия исполнения

Я написал сообщение в блоге об этом с большим количеством объяснений.

Ответ 5

Вот реализация NumPy алгоритма "консенсуса" O (n): пройдите через все триплеты и bin, когда вы идете. Биннинг выполняется, если встретить "385", добавив один к бин [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 pure 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

Ответ 6

Я решил бы проблему следующим образом:

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 является длиной предоставленной строки и, я думаю, лучшее, что вы можете получить.

Ответ 7

Как уже упоминалось в другом ответе, вы не можете делать этот алгоритм в постоянное время, потому что вы должны смотреть хотя бы на n цифр. Линейное время - это самое быстрое, что вы можете получить.

Однако алгоритм может быть выполнен в пространстве O (1). Вам нужно только сохранить подсчеты каждого трехзначного числа, поэтому вам понадобится массив из 1000 записей. Затем вы можете передать номер в.

Моя догадка заключается в том, что либо собеседник оговорился, когда они дали вам решение, либо вы пробовали "постоянное время", когда говорили "постоянное пространство".

Ответ 8

По моему пониманию, вы не можете иметь решение в течение постоянного времени. Это займет, по крайней мере, один проход над миллионным номером (при условии его строки). Вы можете иметь трехзначную циклическую итерацию над цифрами миллионного номера длины и увеличить значение хэш-ключа на 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.

Ответ 9

Вот мой ответ:

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

Метод поиска массива выполняется очень быстро (даже быстрее, чем метод paul-panzer numpy!). Конечно, он обманывает, так как он не заканчивается после завершения, потому что он возвращает генератор. Также не нужно проверять каждую итерацию, если значение уже существует, что может сильно помочь.

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

Ответ 10

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