Dada uma sequência de um milhão de números, retorne todos os números repetidos de 3 dígitos

137

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?

its.david
fonte
68
Se eles acham que a solução é uma constante de 1000, isso me faz pensar que eles teriam construído todos os números de três dígitos e, em seguida, o regex os procuraria. É muito comum as pessoas pensarem que as operações que na verdade não escreveram / viram são "gratuitas". Tenho certeza de que isso seria linear ao comprimento da string.
mypetlion
54
Nitpickingly, se o tamanho da entrada é uma constante, cada algoritmo é tempo constante ;-)
Paulo Ebermann
34
uma constante de 1000 o que ? (adições elefantes?)
ilkkachu
31
Bem, se o comprimento da corda é constante (1M) e o comprimento substring / número é constante (3), então tecnicamente cada solução é constante de tempo ...
Kevin
8
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 Este foi provavelmente o teste real. Para ver se você poderia provar a eles por que isso não é possível e mostrar a eles a complexidade mínima de tempo correta.
James

Respostas:

168

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 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;
}
paxdiablo
fonte
19
Esse "tamanho fixo de entrada" realmente soa como uma piada de mau gosto que o entrevistador ou o entrevistado não entendeu. Cada algoritmo torna-se O(1)é né fixo ou delimitado.
Eric Duminil
5
Se eles precisam melhor do que isso, talvez não devam usar o Python, pelo menos para o algoritmo específico.
Sebastian Redl
3
@ezzzCash Porque pode haver sobreposição nos pontos em que a string está sendo "quebrada" ao tentar uma abordagem paralela. Como você procura grupos de 3 dígitos, -2 permite que a verificação nos dois agrupamentos paralelos não perca uma correspondência potencialmente válida.
código é o seguinte
5
@ezzzCash Não é falta de conhecimento de programação paralela. Considere uma sequência de comprimento N. Se você o dividir em duas partes na posição N/2, você ainda precisará levar em consideração o fato de que pode perder uma correspondência válida de três dígitos na "borda", no final string1e no início de string2. Portanto, você precisa verificar as correspondências entre string1[N/2-2]e string2[2](usando um índice baseado em zero), etc. Essa é a ideia.
Codigo_dredd
1
Com seqüências de dígitos mais longas, há algo a ganhar com a otimização da conversão para número inteiro com uma janela deslizante que permite soltar o dígito mais alto e adicionar um novo dígito. (A sobrecarga do Python provavelmente mataria isso, portanto só se aplicaria ao C ou a outras implementações de baixo nível). val -= 100 * (d[i]-'0');para soltar o dígito inicial. val = 10*val + d[i+2]-'0'para acumular um novo dígito menos significativo (seqüência normal-> análise de número inteiro). val % 100é possivelmente não horrível, mas apenas se 100for uma constante em tempo de compilação, para que ela não use uma divisão HW real.
Peter Cordes
78

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.

rcgldr
fonte
26
@ezzzCash - sim, um dicionário funcionaria, mas não é necessário. Todas as possíveis "chaves" são conhecidas antecipadamente, limitadas ao intervalo de 0 a 999. A diferença de sobrecarga seria o tempo necessário para fazer um acesso baseado em chave usando três cadeias de caracteres como chaves, em comparação com o tempo necessário para converter um número 3. cadeia de dígitos para um índice e, em seguida, usando o índice para acessar a matriz.
rcgldr
4
Se você quiser truques numéricos, também pode optar por usar o BCD e armazenar os três dígitos em 12 bits. E decodifique dígitos ASCII mascarando os 4 bits baixos. Mas esse x-'0'padrão não é válido no Python, é um C-ism (onde os caracteres são inteiros).
Yann Vernier
5
@LorenPechtel: as pesquisas de dicionário em Python são realmente rápidas. Concedido, o acesso ao array é ainda mais rápido; portanto, se estivéssemos lidando com números inteiros desde o início, você estaria certo. No entanto, nesse caso, temos seqüências de três comprimentos, que primeiro precisamos converter em números inteiros, se quisermos usá-las com matrizes. Acontece que, ao contrário do que se poderia esperar primeiro, a pesquisa no dicionário é realmente mais rápida que a conversão de número inteiro + acesso à matriz. A solução do array é de fato 50% mais lenta nesse caso.
Aleksi Torhamo
2
Eu acho que alguém poderia argumentar que, se o número de entrada sempre tiver exatamente 1 milhão de dígitos, esse algoritmo será O (1), com um fator constante de 1 milhão.
Tobias_k
2
@AleksiTorhamo - Se o objetivo é comparar as velocidades relativas das implementações de um algoritmo, eu preferiria uma linguagem tradicional como C ou C ++, pois o Python é significativamente mais lento e parece ter sobrecargas exclusivas do Python em comparação com outras linguagens.
Rcgldr
14

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.

Paddy3118
fonte
Funciona bem e parece ser a solução mais rápida e não numpy.
Eric Duminil
3
@ EricDuminil, não acho que você deva se preocupar em ter os horários mais rápidos aqui, quando a maioria das soluções fornecidas não o atrasar muito. É muito melhor mostrar que você tem uma boa compreensão da biblioteca padrão do Python e pode escrever código sustentável em uma situação de entrevista que eu pensaria. (A menos que o entrevistador enfatize a crítica de tempo com a qual deve pedir horários reais antes de avaliar o que vem a seguir).
precisa saber é o seguinte
1
Nós concordamos 100%. Embora eu não tenha certeza de que alguma resposta seja relevante se o entrevistador realmente achar que é possível responder O(1).
Eric Duminil
1
Se o entrevistador enfatizou que o tempo era crítico, depois de criar um perfil para confirmar que esse é o limite, talvez seja hora de escrever um módulo C para resolver esse gargalo. Eu tenho um script que viu uma melhoria de 84x sobre o código python depois que passamos a usar o módulo ac.
TemporalWolf
Olá @TemporalWolf, li o que você disse e pensou que outra solução, mais rápida e escalável pode ser alterá-la para um algoritmo paralelo, para que possa ser executada em muitos processos em um farm / nuvem de computação. Você precisa dividir a string em n seções; sobrepondo os últimos 3 caracteres de cada seção com a próxima seção. Cada seção pode ser digitalizada em busca de triplos de forma independente, os triplos somados e os três caracteres triplos no final de tudo, exceto a última seção, subtraída, pois teria sido contada duas vezes. Eu tenho o código e provavelmente o transformará em uma postagem no blog ...
Paddy3118
13

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.

Daniel
fonte
37
Existe um desconto de sexta-feira negra em text.count()?
precisa
3
@EricDuminil Você tem um bom argumento, mas, como text.counté feito em uma linguagem compilada de alta velocidade (por exemplo, C), em oposição a um loop interpretado no nível python lento, sim, há um desconto.
John1024
É muito ineficiente contar cada número separadamente, mas é um tempo constante, portanto ainda O (n).
Loren Pechtel 30/11
11
A opção que você propôs usar countestá incorreta, pois não conta padrões sobrepostos. Note que '111'.count('11') == 1quando esperamos que seja 2.
Cireo
2
Além disso, sua " O(n)solução simples " está na verdade O(10**d * n)com do número de dígitos pesquisados ​​e no comprimento total da string. O segundo é o O(n)tempo e o O(10**d + n)espaço.
Eric Duminil
10

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
Paul Panzer
fonte
Provavelmente significativamente mais rápido para achatar a sequência de dígitos em vez de ter caixas aninhadas, a menos que o NumPy acabe implementando-a como uma matriz 3D com indexação eficiente. Qual versão do @ Daniel's você jogou contra; aquele que executa uma pesquisa de string para cada número inteiro ou aquele com um histograma?
Peter Cordes
2
@PeterCordes Eu duvido. ndarrays, o tipo numpy central, trata-se de armazenamento, manipulação e indexação eficiente de matrizes multidimensionais de números. Às vezes, você pode cortar alguns% achatando, mas nesse caso, fazer 100 x [0] + 10 x [1] + x [2] manualmente não ganhará muito. Eu usei o que o @Daniel disse que era mais rápido, você mesmo pode verificar o código de referência.
Paul Panzer
Eu realmente não conheço o NumPy (ou Python em geral; geralmente faço C e ajuste de desempenho de montagem para x86), mas acho que você tem uma única matriz 3D, certo? Eu estava pensando no seu texto em inglês (que aparentemente nem li com atenção) que você tinha objetos Python aninhados e estava indexando-os separadamente. Mas esse não é o caso, então nvm meu primeiro comentário.
Peter Cordes
Eu acho que a versão pura do Python que você usou é praticamente a mesma implementação de histograma usada pelas respostas votadas ainda mais altas, mas se diferentes maneiras de escrevê-lo no Python afetam muito a velocidade.
Peter Cordes
3

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.

pho7
fonte
Você pode simplesmente usar a Counter. Você não precisa de um final_dicte não precisa atualizá-lo a cada iteração.
precisa
2

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.

Abhishek Arora
fonte
2

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".

Cort Ammon
fonte
Como outros já apontaram, a abordagem do histograma é O(10**d)espaço extra, onde dé o número de dígitos decimais que você está procurando.
Peter Cordes
1
A abordagem do dicionário seria O (min (10 ^ d, n)) para n dígitos. Por exemplo, se você tiver n = 10 ^ 9 dígitos e quiser encontrar as raras seqüências de 15 dígitos que ocorrem mais de uma vez.
precisa saber é o seguinte
1

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)]
Turksarama
fonte
1
Então, o que você está comparando exatamente? Você não deve retornar listas em vez de geradores não utilizados?
Eric Duminil
Countersnão são usados ​​dessa maneira. Usados ​​corretamente, eles se tornam a opção mais rápida com o seu exemplo. Se você usar timeitcom uma lista instalada de um gerador, seu método se tornará mais lento que Counterou dict. Veja aqui .
Eric Duminil
Finalmente, você f_arraypode ser mais rápido se primeiro converter todos os caracteres em int: ints = [int(c) for c in text]e depois usar i, j, k = ints[n:n+3].
Eric Duminil
1

Imagem como resposta:

IMAGEM COMO RESPOSTA

Parece uma janela deslizante.

天 杀 包子
fonte
1

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

econ
fonte
Veja a resposta de pho7 . E comentários. Tente descobrir por que não recebe muitos votos.
precisa
0

-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.

Suresh
fonte
-1
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
Gourav Mittal
fonte
Obrigado pela sua resposta, mas é um algoritmo muito semelhante ao fornecido por @abhishek arora há 5 a 6 dias. Além disso, a pergunta original não estava solicitando o algoritmo, mas sim uma pergunta diferente (que já foi respondida várias vezes)
its.david