Kilka miesięcy temu miałem wywiad z funduszem hedgingowym w Nowym Jorku i niestety nie dostałem oferty stażu jako inżynier danych / oprogramowania. (Poprosili również, aby rozwiązanie było w języku Python).

Prawie schrzaniłem problem z pierwszym wywiadem ...

Pytanie: Biorąc pod uwagę ciąg miliona liczb (na przykład Pi), napisz funkcję / program, który zwraca wszystkie powtarzające się liczby 3-cyfrowe i liczbę powtórzeń większą niż 1

Na przykład: jeśli ciąg to 123412345123456:, funkcja / program zwróci:

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

Nie dali mi rozwiązania po tym, jak oblałem rozmowę kwalifikacyjną, ale powiedzieli mi, że złożoność czasowa rozwiązania była stała wynosząca 1000, ponieważ wszystkie możliwe wyniki mieszczą się w przedziale:

000 -> 999

Teraz, kiedy o tym myślę, myślę, że nie można wymyślić algorytmu stałego czasu. Czy to jest?

Wyszedłeś lekko, prawdopodobnie nie chcesz pracować dla funduszu hedgingowego, w którym kwanty nie rozumieją podstawowych algorytmów :-)

Nie ma sposobu na przetworzenie struktury danych o dowolnej wielkości w programieO(1) jeśli tak jak w tym przypadku, każdy element trzeba odwiedzić co najmniej raz. Najlepiej można liczyć to O(n)w tym przypadku, gdzie njest długością łańcucha.

Chociaż, na marginesie, nominalny O(n) algorytm będzie mieć O(1)za stałej wielkości wejściowych tak, technicznie, mogą być tutaj poprawne. Jednak zwykle nie jest to sposób, w jaki ludzie używają analizy złożoności.

Wydaje mi się, że mogłeś zrobić na nich wrażenie na wiele sposobów.

Po pierwsze, informując ich, że tak nie można tego zrobić O(1), chyba że użyjesz powyższego rozumowania „podejrzanego”.

Po drugie, pokazując swoje elitarne umiejętności, dostarczając kod Pythonic, taki jak:

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

To daje:

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

chociaż możesz oczywiście zmienić format wyjściowy na dowolny.

I wreszcie, mówiąc im, że prawie na pewno nie ma problemu z plikiemO(n) rozwiązaniem, ponieważ powyższy kod dostarcza wyniki dla jednomilionowego ciągu w znacznie mniej niż pół sekundy. Wydaje się, że skaluje się również dość liniowo, ponieważ ciąg 10 000 000 znaków zajmuje 3,5 sekundy, a 100 000 000 - 36 sekund.

A jeśli potrzebują czegoś więcej, istnieją sposoby na zrównoleglenie tego rodzaju rzeczy, które mogą znacznie przyspieszyć ten proces.

Oczywiście nie w obrębie jednego interpretera Pythona, ze względu na GIL, ale możesz podzielić ciąg na coś podobnego (nakładanie się vvjest wymagane, aby umożliwić prawidłowe przetwarzanie obszarów granicznych):

    vv
123412  vv
    123451
        5123456

Możesz je wyhodować, aby oddzielić pracowników, a następnie połączyć wyniki.

Dzielenie danych wejściowych i łączenie danych wyjściowych prawdopodobnie zatopi wszelkie oszczędności małymi ciągami (a być może nawet milionami cyfr), ale w przypadku znacznie większych zestawów danych może to mieć znaczenie. Oczywiście obowiązuje tutaj moja zwykła mantra „mierzyć, nie zgaduj” .

Ta mantra odnosi się również do innych możliwości, takich jak całkowite obejście Pythona i użycie innego języka, który może być szybszy.

Na przykład, następujący kod C, działa na tym samym sprzęcie, co wcześniej kodu Pythona, obsługuje 100 mln cyfr w 0,6 sekundy, z grubsza taką samą ilość czasu jak kod Python przetworzonego jednego miliona. Innymi słowy, znacznie szybciej:

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

Stały czas nie jest możliwy. Wszystkie 1 milion cyfr należy sprawdzić co najmniej raz, tak więc jest to złożoność czasowa O (n), gdzie n = 1 milion w tym przypadku.

Aby uzyskać proste rozwiązanie O (n), utwórz tablicę o rozmiarze 1000, która reprezentuje liczbę wystąpień każdej możliwej 3-cyfrowej liczby. Zwiększaj o 1 cyfrę naraz, pierwszy indeks == 0, ostatni indeks == 999997 i tablicę inkrementów [3-cyfrowy numer], aby utworzyć histogram (liczba wystąpień dla każdego możliwego 3-cyfrowego numeru). Następnie wyślij zawartość tablicy z liczbą> 1.

Milion to niewiele, jak na odpowiedź, której udzielę poniżej. Spodziewając się tylko, że musisz być w stanie uruchomić rozwiązanie w wywiadzie, bez przerwy, a następnie Poniższe działa w mniej niż dwie sekundy i daje wymagany wynik:

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)

Miejmy nadzieję, że ankieter będzie szukał możliwości korzystania ze standardowych kolekcji bibliotek.

Wersja z równoległym wykonaniem

Napisałem na ten temat wpis na blogu z dokładniejszym wyjaśnieniem.

Prostym rozwiązaniem O (n) byłoby policzenie każdej 3-cyfrowej liczby:

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

Spowoduje to przeszukanie wszystkich 1 miliona cyfr 1000 razy.

Przechodzenie cyfr tylko raz:

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)

Timing pokazuje, że iteracja tylko raz po indeksie jest dwa razy szybsza niż przy użyciu count.

Oto implementacja NumPy algorytmu „konsensusu” O (n): przejdź przez wszystkie trojaczki i bin na bieżąco. Kategoryzacja jest wykonywana po napotkaniu, powiedzmy "385", dodaniu jednego do przedziału [3, 8, 5], co jest operacją O (1). Pojemniki ułożone są w 10x10x10sześcian. Ponieważ binowanie jest w pełni wektoryzowane, w kodzie nie ma pętli.

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

Nic dziwnego, że NumPy jest nieco szybszy niż czyste rozwiązanie Pythona @ Daniela w przypadku dużych zbiorów danych. Przykładowe dane wyjściowe:

# 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

Rozwiązałbym problem w następujący sposób:

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

Zastosowany do przykładowego ciągu daje:

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

To rozwiązanie działa w O (n), ponieważ n jest długością podanego ciągu i jest, jak sądzę, najlepszym, jakie można uzyskać.

Jak rozumiem, nie możesz mieć rozwiązania w stałym czasie. Potrzeba co najmniej jednego przejścia przez milion cyfr (zakładając, że jest to ciąg). Możesz mieć 3-cyfrową kroczącą iterację po cyfrach liczby o milionie długości i zwiększyć wartość klucza skrótu o 1, jeśli już istnieje, lub utworzyć nowy klucz skrótu (zainicjowany przez wartość 1), jeśli nie istnieje już w słownik.

Kod będzie wyglądał mniej więcej tak:

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

Możesz filtrować w dół do kluczy, które mają wartość elementu większą niż 1.

Jak wspomniano w innej odpowiedzi, nie możesz wykonać tego algorytmu w stałym czasie, ponieważ musisz spojrzeć na co najmniej n cyfr. Czas liniowy jest najszybszy, jaki można uzyskać.

Jednakże, algorytm może być wykonane w O (1) przestrzeń . Musisz tylko zapisać liczbę każdej 3-cyfrowej liczby, więc potrzebujesz tablicy zawierającej 1000 wpisów. Następnie możesz przesyłać strumieniowo numer w formacie.

Domyślam się, że albo ankieter źle wypowiedział się, kiedy podał ci rozwiązanie, albo źle usłyszałeś „stały czas”, kiedy powiedział „stała przestrzeń”.

Oto moja odpowiedź:

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

Metoda wyszukiwania tablic jest bardzo szybka (nawet szybsza niż metoda numpy @ paul-panzer!). Oczywiście oszukuje, ponieważ nie jest technicznie zakończony po zakończeniu, ponieważ zwraca generator. Nie musi też sprawdzać każdej iteracji, czy wartość już istnieje, co może bardzo pomóc.

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

Obraz jako odpowiedź:

Wygląda na przesuwane okno.

Oto moje rozwiązanie:

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}

Przy odrobinie kreatywności w pętli for (i dodatkowej liście wyszukiwania z na przykład True / False / None) powinieneś być w stanie pozbyć się ostatniej linii, ponieważ chcesz utworzyć tylko klucze w dict, które odwiedziliśmy raz do tego momentu . Mam nadzieję, że to pomoże :)

-Opowiadanie z perspektywy C. -Możesz otrzymać int 3-d tablicę wyników [10] [10] [10]; -Przejdź z 0-tej lokalizacji do n-4-tej lokalizacji, gdzie n to rozmiar tablicy ciągów. -W każdej lokalizacji sprawdź bieżącą, następną i następną. -Increment the cntr as resutls [current] [next] [next's next] ++; -Drukuj wartości

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]

-To jest O (n) czas, nie ma porównań. -Możesz tutaj uruchomić kilka równoległych rzeczy, dzieląc tablicę i obliczając dopasowania wokół partycji.

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