Eu tive uma entrevista com uma empresa de fundos de hedge em Nova York há alguns meses atrás e, infelizmente, não recebi a oferta de estágio como engenheiro de dados / software. (Eles também pediram que a solução estivesse em Python.)

Eu estraguei tudo sobre o primeiro problema de entrevista ...

Pergunta: Dada uma sequência de um milhão de números (Pi, por exemplo), escreva uma função / programa que retorne todos os números de 3 dígitos repetidos e o número de repetições maior que 1

Por exemplo: se a sequência fosse 123412345123456:, a função / programa retornaria:

123 - 3 times
234 - 3 times
345 - 2 times

Eles não me deram a solução depois que eu falhei na entrevista, mas disseram que a complexidade do tempo para a solução era constante de 1000, pois todos os resultados possíveis estão entre:

000 -> 999

Agora que estou pensando nisso, não acho possível criar um algoritmo de tempo constante. É isso?

Você saiu de ânimo leve, provavelmente não quer trabalhar para um fundo de hedge onde os quantos não entendem algoritmos básicos :-)

Não há como processar uma estrutura de dados de tamanho arbitrário O(1)se, como neste caso, você precisar visitar todos os elementos pelo menos uma vez. O melhor que você pode esperar é O(n), neste caso, onde nestá o comprimento da string.

Embora, como um aparte, uma nominal O(n)algoritmo vai ser O(1)para um tamanho de entrada fixa assim, tecnicamente, eles podem ter sido correto aqui. No entanto, geralmente não é assim que as pessoas usam a análise de complexidade.

Parece-me que você poderia tê-los impressionado de várias maneiras.

Primeiro, informando-lhes que é não possível fazê-lo em O(1), a menos que você use o "suspeito" fundamentação apresentada acima.

Segundo, mostrando suas habilidades de elite, fornecendo código Pythonic, como:

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

Isso gera:

[(123, 3), (234, 3), (345, 2)]

embora você possa, é claro, modificar o formato de saída para o que desejar.

E, finalmente, dizendo a eles que quase certamente não há problema com uma O(n)solução, pois o código acima fornece resultados para uma sequência de um milhão de dígitos em menos de meio segundo. Também parece ter uma escala linear, pois uma sequência de 10.000.000 caracteres leva 3,5 segundos e uma sequência de 100.000.000 caracteres leva 36 segundos.

E, se eles precisarem melhor do que isso, existem maneiras de paralelizar esse tipo de coisa que pode acelerar muito.

Evidentemente, não dentro de um único intérprete Python, devido ao GIL, mas você pode dividir a string em algo como (sobreposição indicada por vvé necessária para permitir o processamento adequado das áreas de fronteira):

    vv
123412  vv
    123451
        5123456

Você pode cultivá-las para separar os trabalhadores e combinar os resultados posteriormente.

A divisão da entrada e a combinação da saída provavelmente inundarão qualquer economia com pequenas cadeias (e possivelmente até milhões de dígitos), mas, para conjuntos de dados muito maiores, pode muito bem fazer a diferença. Meu mantra habitual de "medir, não acho" se aplica aqui, é claro.

Esse mantra também se aplica a outras possibilidades, como ignorar completamente o Python e usar uma linguagem diferente que pode ser mais rápida.

Por exemplo, o código C a seguir, executado no mesmo hardware que o código Python anterior, manipula cem milhões de dígitos em 0,6 segundos, aproximadamente a mesma quantidade de tempo que o código Python processou um milhão. Em outras palavras, muito mais rápido:

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

Tempo constante não é possível. Todos os 1 milhão de dígitos precisam ser visualizados pelo menos uma vez, para que seja uma complexidade de tempo de O (n), em que n = 1 milhão neste caso.

Para uma solução O (n) simples, crie uma matriz de tamanho 1000 que represente o número de ocorrências de cada número possível de 3 dígitos. Avance 1 dígito por vez, primeiro índice == 0, último índice == 999997 e incremente a matriz [número de 3 dígitos] para criar um histograma (contagem de ocorrências para cada número possível de 3 dígitos). Em seguida, imprima o conteúdo da matriz com contagens> 1.

Um milhão é pequeno para a resposta que dou abaixo. Esperando apenas que você precise executar a solução na entrevista, sem uma pausa, o seguinte funciona em menos de dois segundos e fornece o resultado necessário:

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)

Esperamos que o entrevistador esteja procurando o uso das coleções de bibliotecas padrão.

Versão de execução paralela

Eu escrevi um post sobre isso com mais explicações.

A solução O (n) simples seria contar cada número de 3 dígitos:

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

Isso pesquisaria todos os 1 milhão de dígitos 1000 vezes.

Atravessando os dígitos apenas uma vez:

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)

O tempo mostra que a iteração apenas uma vez no índice é duas vezes mais rápida que a utilização count.

Aqui está uma implementação NumPy do algoritmo "consenso" O (n): percorra todos os trigêmeos e bin à medida que avança. O binning é feito ao encontrar, digamos "385", adicionando um ao bin [3, 8, 5], que é uma operação O (1). As caixas são organizadas em um 10x10x10cubo. Como o binning é totalmente vetorizado, não há loop no código.

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

Sem surpresa, o NumPy é um pouco mais rápido que a solução Python pura do @ Daniel em grandes conjuntos de dados. Saída de amostra:

# 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

Eu resolveria o problema da seguinte maneira:

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

Aplicado à sua sequência de exemplo, isso gera:

>>> find_numbers("123412345123456")
{345: 2, 234: 3, 123: 3}

Essa solução é executada em O (n) por n ser o comprimento da string fornecida e é, eu acho, o melhor que você pode obter.

De acordo com o meu entendimento, você não pode ter a solução em um tempo constante. Será necessário pelo menos uma passagem sobre o número de um milhão de dígitos (supondo que seja uma string). Você pode ter uma iteração de rolagem de três dígitos sobre os dígitos do número de milhões de comprimentos e aumentar o valor da chave de hash em 1, se ele já existir, ou criar uma nova chave de hash (inicializada pelo valor 1), se ainda não existir. o dicionário.

O código será algo como isto:

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

Você pode filtrar até as chaves com valor de item maior que 1.

Como mencionado em outra resposta, você não pode executar esse algoritmo em tempo constante, porque deve procurar pelo menos n dígitos. O tempo linear é o mais rápido possível.

No entanto, o algoritmo pode ser feito em O (1) espaço . Você só precisa armazenar as contagens de cada número de 3 dígitos, portanto, precisa de uma matriz de 1000 entradas. Em seguida, você pode transmitir o número.

Meu palpite é que, ou o entrevistador falou errado quando lhe deram a solução, ou você ouviu "tempo constante" quando disse "espaço constante".

Aqui está a minha resposta:

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

O método de pesquisa de array é muito rápido (ainda mais rápido que o método numpy do @ paul-panzer!). Obviamente, ele trapaceia, pois não é tecnicamente terminado depois de concluído, porque está retornando um gerador. Ele também não precisa verificar todas as iterações se o valor já existir, o que provavelmente ajudará muito.

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

Imagem como resposta:

Parece uma janela deslizante.

Aqui está a minha solução:

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}

Com um pouco de criatividade no loop for (e uma lista de pesquisa adicional com True / False / None, por exemplo), você poderá se livrar da última linha, pois só deseja criar chaves no dict que visitamos uma vez até aquele momento . Espero que ajude :)

-Dizer a partir da perspectiva de C. -Você pode obter resultados de uma matriz 3-d int [10] [10] [10]; -Vá do 0º local para o 4º local, onde n é o tamanho da matriz de cadeias. -Em cada local, verifique o atual, o próximo e o próximo é o próximo. -Incrementa o cntr como resutls [atual] [próximo] [próximo é próximo] ++; -Imprima os valores de

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]

-É hora O (n), não há comparações envolvidas. -Você pode executar algumas coisas paralelas aqui particionando a matriz e calculando as correspondências em torno das partições.

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