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?
źródło
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
To był prawdopodobnie rzeczywisty test. Aby sprawdzić, czy możesz im udowodnić, dlaczego nie jest to możliwe, i pokazać im poprawną minimalną złożoność czasową.Odpowiedzi:
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 programie
O(1)
jeśli tak jak w tym przypadku, każdy element trzeba odwiedzić co najmniej raz. Najlepiej można liczyć toO(n)
w tym przypadku, gdzien
jest długością łańcucha.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:
To daje:
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 plikiem
O(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ę
vv
jest wymagane, aby umożliwić prawidłowe przetwarzanie obszarów granicznych):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:
źródło
O(1)
sięn
jest stałe lub ograniczone.N
. Jeśli podzielisz go na dwie części na pozycjiN/2
, nadal musisz wziąć pod uwagę fakt, że możesz przegapić prawidłowe 3-cyfrowe dopasowanie na „granicy”, na końcustring1
i na początkustring2
. W związku z tym musisz sprawdzić dopasowania międzystring1[N/2-2]
istring2[2]
(używając indeksu zaczynającego się od zera) itd. To jest idea.val -= 100 * (d[i]-'0');
aby usunąć wiodącą cyfrę.val = 10*val + d[i+2]-'0'
aby zgromadzić nową najmniej znaczącą cyfrę (zwykłe parsowanie ciąg-> liczb całkowitych).val % 100
jest prawdopodobnie okropne, ale tylko wtedy, gdy100
jest stałą czasu kompilacji, więc nie używa prawdziwego podziału sprzętowego.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.
źródło
x-'0'
wzorzec nie jest prawidłowy w Pythonie, jest to C-izm (gdzie znaki są liczbami całkowitymi).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:
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.
źródło
O(1)
.Prostym rozwiązaniem O (n) byłoby policzenie każdej 3-cyfrowej liczby:
Spowoduje to przeszukanie wszystkich 1 miliona cyfr 1000 razy.
Przechodzenie cyfr tylko raz:
Timing pokazuje, że iteracja tylko raz po indeksie jest dwa razy szybsza niż przy użyciu
count
.źródło
text.count()
?text.count
jest to zrobione w szybkim języku kompilowanym (np. C), w przeciwieństwie do powolnego interpretowanego zapętlania na poziomie Pythona, tak, jest to zniżka.count
jest nieprawidłowa, ponieważ nie będzie liczyć nakładających się wzorców. Zauważ, że'111'.count('11') == 1
kiedy byśmy się tego spodziewali2
.O(n)
rozwiązanie” jest w rzeczywistościO(10**d * n)
zd
liczby poszukiwanych cyfr in
łącznej długości łańcucha. Drugi toO(n)
czas iO(10**d + n)
przestrzeń.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
10x10x10
sześcian. Ponieważ binowanie jest w pełni wektoryzowane, w kodzie nie ma pętli.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:
źródło
ndarray
s, podstawowy typ numpy, dotyczą wydajnego przechowywania, manipulowania i indeksowania wielowymiarowych tablic liczb. Czasami możesz zgolić kilka% przez spłaszczenie, ale w tym przypadku ręczne wykonanie 100 x [0] + 10 x [1] + x [2] nie da wiele. Użyłem tego, który @Daniel powiedział, że jest szybszy, możesz sam sprawdzić kod testu.Rozwiązałbym problem w następujący sposób:
Zastosowany do przykładowego ciągu daje:
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ć.
źródło
Counter
. Nie potrzebujeszfinal_dict
i nie musisz aktualizować go przy każdej iteracji.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:
Możesz filtrować w dół do kluczy, które mają wartość elementu większą niż 1.
źródło
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ń”.
źródło
O(10**d)
dodatkowa spacja, gdzied
jest liczba cyfr dziesiętnych, których szukasz.Oto moja odpowiedź:
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.
źródło
Counters
nie są używane w ten sposób. Użyte prawidłowo, na twoim przykładzie stają się najszybszą opcją. Jeśli używasztimeit
z listą zamiast generatora, twoja metoda będzie wolniejsza niżCounter
lubdict
. Zobacz tutaj .f_array
być szybszy, jeśli najpierw przekonwertujesz każdy znak na int:ints = [int(c) for c in text]
a następnie użyjeszi, j, k = ints[n:n+3]
.Obraz jako odpowiedź:
Wygląda na przesuwane okno.
źródło
Oto moje rozwiązanie:
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 :)
źródło
-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
-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.
źródło
źródło