J'ai eu un entretien avec une société de hedge funds à New York il y a quelques mois et malheureusement, je n'ai pas reçu l'offre de stage en tant qu'ingénieur data / logiciel. (Ils ont également demandé que la solution soit en Python.)

J'ai assez merdé sur le premier problème d'entretien ...

Question: Étant donné une chaîne d'un million de nombres (Pi par exemple), écrivez une fonction / programme qui renvoie tous les nombres répétitifs à 3 chiffres et le nombre de répétitions supérieur à 1

Par exemple: si la chaîne était: 123412345123456alors la fonction / programme renverrait:

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

Ils ne m'ont pas donné la solution après avoir échoué à l'entretien, mais ils m'ont dit que la complexité temporelle de la solution était constante de 1000 puisque tous les résultats possibles sont compris entre:

000 -> 999

Maintenant que j'y pense, je ne pense pas qu'il soit possible de proposer un algorithme à temps constant. C'est ça?

Vous êtes descendu légèrement, vous ne voulez probablement pas travailler pour un hedge fund où les quants ne comprennent pas les algorithmes de base :-)

Il n'y a aucun moyen de traiter une structure de données de taille arbitraire O(1)si, comme dans ce cas, vous devez visiter chaque élément au moins une fois. Le mieux que vous puissiez espérer est O(n)dans ce cas, où nest la longueur de la chaîne.

Bien que, en aparté, un nominal O(n)algorithme sera être O(1)pour une taille d'entrée fixe donc, techniquement, ils ont eu raison ici. Cependant, ce n'est généralement pas ainsi que les gens utilisent l'analyse de complexité.

Il me semble que vous auriez pu les impressionner de plusieurs façons.

D'abord, en les informant qu'il n'est pas possible de le faire O(1), à moins que vous n'utilisiez le raisonnement «suspect» donné ci-dessus.

Deuxièmement, en montrant vos compétences d'élite en fournissant un code pythonique tel que:

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

Cela produit:

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

bien que vous puissiez, bien sûr, modifier le format de sortie à tout ce que vous désirez.

Et, enfin, en leur disant qu'il n'y a presque certainement aucun problème avec une O(n)solution, puisque le code ci-dessus fournit des résultats pour une chaîne d'un million de chiffres en moins d'une demi-seconde. Il semble également être mis à l'échelle de manière assez linéaire, car une chaîne de 10 000 000 de caractères prend 3,5 secondes et une chaîne de 100 000 000 de caractères prend 36 secondes.

Et, s'ils ont besoin de mieux que cela, il existe des moyens de paralléliser ce genre de choses qui peuvent considérablement l'accélérer.

Pas dans un seul interpréteur Python bien sûr, en raison du GIL, mais vous pouvez diviser la chaîne en quelque chose comme (le chevauchement indiqué par vvest nécessaire pour permettre un traitement approprié des zones de délimitation):

    vv
123412  vv
    123451
        5123456

Vous pouvez les regrouper pour séparer les travailleurs et combiner les résultats par la suite.

Le fractionnement de l'entrée et la combinaison de la sortie sont susceptibles de submerger toute économie avec de petites chaînes (et peut-être même des chaînes à millions de chiffres) mais, pour des ensembles de données beaucoup plus volumineux, cela peut bien faire une différence. Mon mantra habituel de «mesurer, ne pas deviner» s'applique ici, bien sûr.

Ce mantra s'applique également à d' autres possibilités, telles que le contournement de Python et l'utilisation d'un langage différent qui peut être plus rapide.

Par exemple, le code C suivant, exécuté sur le même matériel que le code Python précédent, gère cent millions de chiffres en 0,6 seconde, à peu près le même temps que le code Python en a traité un million. En d'autres termes, beaucoup plus rapide:

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

Le temps constant n'est pas possible. Tous les 1 million de chiffres doivent être examinés au moins une fois, c'est donc une complexité temporelle de O (n), où n = 1 million dans ce cas.

Pour une solution O (n) simple, créez un tableau de taille 1000 qui représente le nombre d'occurrences de chaque nombre à 3 chiffres possible. Avancez d'un chiffre à la fois, premier index == 0, dernier index == 999997 et incrémentez le tableau [numéro à 3 chiffres] pour créer un histogramme (nombre d'occurrences pour chaque numéro à 3 chiffres possible). Sortez ensuite le contenu du tableau avec des nombres> 1.

Un million est petit pour la réponse que je donne ci-dessous. En attendant seulement que vous deviez être en mesure d'exécuter la solution dans l'interview, sans pause, alors ce qui suit fonctionne en moins de deux secondes et donne le résultat souhaité:

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)

Espérons que l'intervieweur recherchera l'utilisation des collections de bibliothèques standard.

Version d'exécution parallèle

J'ai écrit un article de blog à ce sujet avec plus d'explications.

La solution simple O (n) serait de compter chaque nombre à 3 chiffres:

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

Cela permettrait de rechercher 1000 fois le million de chiffres.

Traverser les chiffres une seule fois:

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)

Le chronométrage montre qu'itérer une seule fois sur l'index est deux fois plus rapide que d'utiliser count.

Voici une implémentation NumPy de l'algorithme «consensus» O (n): parcourez tous les triplets et bin au fur et à mesure. Le regroupement est effectué en rencontrant, disons "385", en ajoutant un au bin [3, 8, 5] qui est une opération O (1). Les bacs sont disposés dans un 10x10x10cube. Comme le binning est entièrement vectorisé, il n'y a pas de boucle dans le code.

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

Sans surprise, NumPy est un peu plus rapide que la solution pure Python de @ Daniel sur de grands ensembles de données. Exemple de sortie:

# 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

Je résoudrais le problème comme suit:

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

Appliqué à votre exemple de chaîne, cela donne:

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

Cette solution fonctionne dans O (n) pour n étant la longueur de la chaîne fournie, et est, je suppose, la meilleure que vous puissiez obtenir.

Selon ma compréhension, vous ne pouvez pas avoir la solution dans un temps constant. Il faudra au moins un passage sur le nombre à millions de chiffres (en supposant qu'il s'agit d'une chaîne). Vous pouvez avoir une itération glissante à 3 chiffres sur les chiffres du nombre de millions de longueur et augmenter la valeur de la clé de hachage de 1 si elle existe déjà ou créer une nouvelle clé de hachage (initialisée par la valeur 1) si elle n'existe pas déjà dans le dictionnaire.

Le code ressemblera à ceci:

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

Vous pouvez filtrer jusqu'aux clés dont la valeur d'élément est supérieure à 1.

Comme mentionné dans une autre réponse, vous ne pouvez pas faire cet algorithme en temps constant, car vous devez regarder au moins n chiffres. Le temps linéaire est le plus rapide que vous puissiez obtenir.

Cependant, l'algorithme peut être fait dans l' espace O (1) . Il vous suffit de stocker les nombres de chaque nombre à 3 chiffres, vous avez donc besoin d'un tableau de 1000 entrées. Vous pouvez ensuite diffuser le numéro au format.

Je suppose que soit l'intervieweur s'est mal exprimé lorsqu'il vous a donné la solution, soit vous avez mal entendu «temps constant» quand il a dit «espace constant».

Voici ma réponse:

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

La méthode de recherche de tableau est très rapide (encore plus rapide que la méthode numpy de @ paul-panzer!). Bien sûr, il triche car il n'est pas techniquement terminé après l'avoir terminé, car il renvoie un générateur. Il n'est pas non plus nécessaire de vérifier à chaque itération si la valeur existe déjà, ce qui est susceptible d'aider beaucoup.

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

Image comme réponse:

On dirait une fenêtre coulissante.

Voici ma solution:

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}

Avec un peu de créativité dans la boucle for (et une liste de recherche supplémentaire avec True / False / None par exemple), vous devriez pouvoir vous débarrasser de la dernière ligne, car vous ne voulez créer que des clés dans dict que nous avons visitées une fois jusqu'à ce point . J'espère que ça aide :)

-Dire du point de vue de C. -Vous pouvez avoir un tableau int 3-d résultats [10] [10] [10]; -Aller du 0ème emplacement au n-4ème emplacement, où n étant la taille du tableau de chaînes. -Sur chaque emplacement, vérifiez le courant, le suivant et le suivant. -Incrémenter le cntr comme resutls [courant] [suivant] [suivant suivant] ++; -Imprimer les valeurs 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]

-Il est temps O (n), il n'y a pas de comparaison impliquée. -Vous pouvez exécuter des trucs parallèles ici en partitionnant le tableau et en calculant les correspondances autour des partitions.

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