Zdobądź 100 najwyższych liczb z nieskończonej listy

Jedno z moich znajomych zostało zadane w tym wywiadzie -

„Ciągły napływ liczb przychodzi z nieskończonej listy liczb, z których trzeba utrzymywać strukturę danych, aby zwracać 100 najwyższych liczb w danym momencie. Załóżmy, że wszystkie liczby są tylko liczbami całkowitymi”.

Jest to proste, musisz utrzymywać posortowaną listę w kolejności malejącej i śledzić najniższy numer na tej liście. Jeśli uzyskany nowy numer jest większy niż ten najniższy numer, należy usunąć ten najniższy numer i w razie potrzeby wstawić nowy numer na posortowanej liście.

Następnie pytanie zostało przedłużone -

„Czy możesz upewnić się, że zamówienie na wstawienie powinno mieć wartość O (1)? Czy to możliwe?”

O ile mi wiadomo, nawet jeśli dodasz nowy numer do listy i posortujesz go ponownie za pomocą dowolnego algorytmu sortowania, najlepiej byłoby O (logn) dla szybkiego sortowania (myślę). Więc mój przyjaciel powiedział, że to niemożliwe. Ale nie był przekonany, poprosił o zachowanie innej struktury danych niż listy.

Myślałem o zrównoważonym drzewie binarnym, ale nawet tam nie dostaniesz wstawienia w kolejności 1. Więc to samo pytanie mam również teraz. Chciałem wiedzieć, czy istnieje taka struktura danych, która może wstawiać w kolejności 1 dla powyższego problemu lub nie jest to w ogóle możliwe.

Powiedzmy, że k jest liczbą najwyższych liczb, które chcesz znać (100 w twoim przykładzie). Następnie możesz dodać nowy numer, w O(k)którym również jest O(1). Ponieważ O(k*g) = O(g) if k is not zero and constant.

Zachowaj listę nieposortowaną. Ustalenie, czy wstawić nowy numer zajmie więcej czasu, ale wstawienie będzie O (1).

To jest łatwe. Rozmiar listy stałej, dlatego czas sortowania listy jest stały. Mówi się, że operacja wykonywana w stałym czasie to O (1). Dlatego sortowanie listy to O (1) dla listy o ustalonym rozmiarze.

Po przejściu 100 liczb, maksymalny koszt, jaki kiedykolwiek poniesiesz za następną liczbę, to koszt sprawdzenia, czy liczba jest w najwyższej liczbie 100 ( oznaczmy to CheckTime ) plus koszt wpisania jej do tego zestawu i wysunięcie najniższy (nazwijmy to EnterTime ), który jest stałym czasem (przynajmniej dla liczb ograniczonych) lub O (1) .

Worst = CheckTime + EnterTime

Następnie, jeśli rozkład liczb jest losowy, średni koszt zmniejsza się, im więcej liczb masz. Na przykład szansa, że ​​będziesz musiał wpisać 101. liczbę do maksymalnego zestawu, wynosi 100/101, szanse na 1000. liczby to 1/10, a szanse na n-tą liczbę to 100 / n. Zatem nasze równanie średniego kosztu będzie:

Average = CheckTime + EnterTime / n

Zatem, gdy n zbliża się do nieskończoności, ważny jest tylko CheckTime :

Average = CheckTime

Jeśli liczby są powiązane, CheckTime jest stały, a zatem jest to czas O (1) .

Jeśli liczby nie są powiązane, czas sprawdzania wydłuży się wraz z większą liczbą liczb. Teoretycznie dzieje się tak, ponieważ jeśli najmniejsza liczba w maksymalnym zestawie stanie się wystarczająco duża, czas sprawdzania będzie dłuższy, ponieważ będziesz musiał rozważyć więcej bitów. To sprawia, że ​​wydaje się, że będzie nieco wyższy niż stały czas. Jednak można również argumentować, że szansa, że ​​następna liczba jest w najwyższym zbiorze, zbliża się do zera, gdy n zbliża się do nieskończoności, a więc szansa, że ​​musisz rozważyć więcej bitów, również zbliża się do 0, co byłoby argumentem dla O (1) czas.

Nie jestem pozytywny, ale moje jelita mówią, że jest to czas O (log (log (n))) . Jest tak, ponieważ szansa, że ​​najniższa liczba wzrośnie, jest logarytmiczna, a szansa, że ​​liczba bitów, które należy wziąć pod uwagę przy każdej kontroli, jest również logarytmiczna. Interesują mnie inne narody, ponieważ nie jestem do końca pewien ...

ten jest łatwy, jeśli znasz Binary Heap Trees . Sterty binarne wspierają wstawianie w średnim stałym czasie, O (1). I daje łatwy dostęp do pierwszych x elementów.

Jeśli na pytanie pytający naprawdę chciał zapytać „czy możemy upewnić się, że każdy przychodzący numer jest przetwarzany w stałym czasie”, to jak wielu już wskazało (np. Patrz odpowiedź @ duedl0r), rozwiązaniem twojego znajomego jest już O (1), i tak by było, nawet gdyby użył nieposortowanej listy, użył sortowania bąbelkowego lub cokolwiek innego. W takim przypadku pytanie nie ma większego sensu, chyba że było to trudne pytanie lub źle go pamiętasz.

Zakładam, że pytanie ankietera było znaczące, że nie pytał, jak zrobić coś, aby być O (1), co już bardzo oczywiste już jest.

Ponieważ złożoność algorytmu kwestionowania ma sens tylko wtedy, gdy wielkość danych wejściowych rośnie w nieskończoność, a jedyne dane wejściowe, które mogą tutaj wzrosnąć, to 100 - wielkość listy; Zakładam, że prawdziwym pytaniem było „czy możemy się upewnić, że Top N spędza O (1) czas na liczbę (nie O (N) jak w rozwiązaniu twojego przyjaciela), czy to możliwe?”.

Pierwszą rzeczą, która przychodzi na myśl, jest zliczanie sortowania, które kupi złożoność czasu O (1) na liczbę dla problemu Top-N za cenę użycia przestrzeni O (m), gdzie m jest długością zakresu liczb przychodzących . Tak, jest to możliwe.

Użyj kolejki o minimalnym priorytecie zaimplementowanej ze stertą Fibonacciego , która ma stały czas wstawiania:

1. Insert first 100 elements into PQ
2. loop forever
       n = getNextNumber();
       if n > PQ.findMin() then
           PQ.deleteMin()
           PQ.insert(n)

Zadanie polega na znalezieniu algorytmu O (1) o długości N wymaganej listy liczb. Nie ma więc znaczenia, czy potrzebujesz 100 najlepszych numerów, czy 10000 liczb, czas wstawienia powinien wynosić O (1).

Sztuczka polega na tym, że chociaż wspomniany jest wymóg O (1) dla wstawki listy, pytanie nie mówiło nic o kolejności czasu wyszukiwania w całej przestrzeni liczbowej, ale okazuje się, że można to zrobić O (1) także. Rozwiązanie jest następujące:

1. Umów się na tablicę skrótów z liczbami na klucze i parami połączonych wskaźników listy dla wartości. Każda para wskaźników jest początkiem i końcem połączonej sekwencji list. Zwykle będzie to tylko jeden element, a następnie następny. Każdy element na połączonej liście znajduje się obok elementu o kolejnym najwyższym numerze. Lista połączona zawiera posortowaną sekwencję wymaganych numerów. Przechowuj rekord o najniższej liczbie.

2. Weź nową liczbę x z losowego strumienia.

3. Czy jest wyższy niż ostatnio zarejestrowany najniższy numer? Tak => Krok 4, Nie => Krok 2

4. Traf w tablicę skrótów z właśnie pobraną liczbą. Czy jest wpis? Tak => Krok 5. Nie => Weź nową liczbę x-1 i powtórz ten krok (jest to proste wyszukiwanie liniowe w dół, po prostu zmiłuj się tutaj, można to poprawić, a ja wyjaśnię, jak)

5. Po uzyskaniu elementu listy z tabeli skrótów wstaw nowy numer zaraz po elemencie na liście połączonej (i zaktualizuj skrót)

6. Weź najniższą zarejestrowaną liczbę l (i usuń ją z mieszania / listy).

7. Traf w tablicę skrótów z właśnie pobraną liczbą. Czy jest wpis? Tak => Krok 8. Nie => Weź nową liczbę l + 1 i powtórz ten krok (jest to proste wyszukiwanie liniowe w górę)

8. Po trafieniu dodatnim liczba staje się nową najniższą liczbą. Przejdź do kroku 2

Aby pozwolić na zduplikowane wartości, skrót faktycznie musi utrzymywać początek i koniec połączonej sekwencji elementów, które są duplikatami. Dodanie lub usunięcie elementu pod danym klawiszem zwiększa lub zmniejsza wskazany zakres.

Tu wstawka to O (1). Wspomniane wyszukiwania to, jak sądzę, coś w rodzaju O (średnia różnica między liczbami). Średnia różnica rośnie wraz z rozmiarem przestrzeni liczbowej, ale maleje wraz z wymaganą długością listy liczb.

Zatem strategia wyszukiwania liniowego jest dość słaba, jeśli przestrzeń liczbowa jest duża (np. Dla typu int 4 bajtowego, od 0 do 2 ^ 32-1) i N = 100. Aby obejść ten problem z wydajnością, możesz przechowywać równoległe zestawy tablic mieszających, w których liczby są zaokrąglane do większych wielkości (np. 1s, 10s, 100s, 1000s), aby utworzyć odpowiednie klucze. W ten sposób możesz zwiększać i zmniejszać biegi, aby szybciej przeprowadzać wymagane wyszukiwania. Wydajność staje się wtedy O (logarytmiczny zakres), myślę, że jest stała, tj. O (1) również.

Aby to wyjaśnić, wyobraź sobie, że masz pod ręką liczbę 197. Trafiłeś tablicę haszującą 10s, z „190”, jest ona zaokrąglana do najbliższej dziesiątki. Byle co? Nie. Więc schodzisz za 10s, aż trafisz powiedz 120. Następnie możesz zacząć od 129 w tablicy 1s, a następnie spróbuj 128, 127, aż coś trafisz. Znalazłeś teraz miejsce na połączonej liście, aby wstawić numer 197. Podczas wpisywania musisz również zaktualizować tablicę hashtable 1 z wpisem 197, tablicę hasht z 10s o numerze 190, 100s ze 100 itd. Najwięcej kroków musisz tu zrobić 10 razy więcej niż dziennik zakresu liczb.

Mogłem pomylić niektóre szczegóły, ale ponieważ jest to wymiana programistów, a kontekstem były wywiady, mam nadzieję, że powyższe jest wystarczająco przekonującą odpowiedzią na tę sytuację.

EDYCJA Dodałem tutaj kilka dodatkowych szczegółów w celu wyjaśnienia równoległego schematu tablicy mieszającej i tego, jak to znaczy, że słabe wyszukiwania liniowe, o których wspomniałem, można zastąpić wyszukiwaniem O (1). Zdałem sobie również sprawę, że oczywiście nie ma potrzeby szukania następnej najniższej liczby, ponieważ możesz przejść od razu do niej, zaglądając do tablicy hasht z najmniejszą liczbą i przechodząc do następnego elementu.

Czy możemy założyć, że liczby mają stały typ danych, taki jak liczba całkowita? Jeśli tak, zachowaj podsumowanie każdego dodanego numeru. Jest to operacja O (1).

1. Zadeklaruj tablicę z tyloma elementami, ile jest możliwych liczb:
2. Czytaj każdy numer, który jest przesyłany strumieniowo.
3. Zlicz liczbę. Zignoruj ​​go, jeśli liczba ta została już zwiększona 100 razy, ponieważ nigdy jej nie będziesz potrzebować. Zapobiega to liczeniu przelewów przez nieskończoną liczbę razy.
4. Powtórz od kroku 2.

Kod VB.Net:

Const Capacity As Integer = 100

Dim Tally(Integer.MaxValue) As Integer ' Assume all elements = 0
Do
    Value = ReadValue()
    If Tally(Value) < Capacity Then Tally(Value) += 1
Loop

Po zwróceniu listy możesz wziąć tyle, ile chcesz. Po prostu iteruj od końca listy i utwórz nową listę z najwyższymi 100 zarejestrowanymi wartościami. To operacja O (n), ale to nieistotne.

Dim List(Capacity) As Integer
Dim ListCount As Integer = 0
Dim Value As Integer = Tally.Length - 1
Dim ValueCount As Integer = 0
Do Until ListCount = List.Length OrElse Value < 0
    If Tally(Value) > ValueCount Then
        List(ListCount) = Value
        ValueCount += 1
        ListCount += 1
    Else
        Value -= 1
        ValueCount = 0
    End If
Loop
Return List

Edycja: W rzeczywistości nie ma znaczenia, czy jest to stały typ danych. Biorąc pod uwagę, że nie ma narzuconych limitów zużycia pamięci (lub dysku twardego), możesz to zrobić dla dowolnego zakresu liczb całkowitych dodatnich.

Sto liczb można łatwo zapisać w tablicy, rozmiar 100. Każde drzewo, lista lub zestaw jest przesadzone, biorąc pod uwagę dane zadanie.

Jeśli liczba przychodząca jest wyższa niż najniższa (= ostatnia) w tablicy, przejrzyj wszystkie wpisy. Gdy znajdziesz pierwszy, który jest mniejszy niż nowy numer (możesz użyć do tego wyszukanych wyszukiwań), biegnij przez resztę tablicy, przesuwając każdy wpis „w dół” o jeden.

Ponieważ sortujesz listę od początku, nie musisz wcale uruchamiać żadnego algorytmu sortowania. To jest O (1).

Możesz użyć Binary Max-Heap. Będziesz musiał śledzić wskaźnik do minimalnego węzła (który może być nieznany / null).

Zaczynasz od wstawienia pierwszych 100 liczb do sterty. Maksimum będzie na górze. Po wykonaniu tej czynności zawsze będziesz przechowywać 100 numerów.

Następnie, gdy otrzymasz nowy numer:

if(minimumNode == null)
{
    minimumNode = findMinimumNode();
}
if(newNumber > minimumNode.Value)
{
    heap.Remove(minimumNode);
    minimumNode = null;
    heap.Insert(newNumber);
}

Niestety findMinimumNodejest O (n), a ty ponosisz ten koszt raz na wkładkę (ale nie podczas wkładki :). Usunięcie minimalnego węzła i wstawienie nowego węzła to średnio O (1), ponieważ będą dążyły do ​​dołu stosu.

Idąc w drugą stronę z Binary Min-Heap, min jest na górze, co jest świetne do znalezienia min do porównania, ale jest do bani, gdy trzeba zastąpić minimum nową liczbą, która jest> min. Jest tak, ponieważ musisz usunąć minimalny węzeł (zawsze O (logN)), a następnie wstawić nowy węzeł (średni O (1)). Tak więc nadal masz O (logN), co jest lepsze niż Max-Heap, ale nie O (1).

Oczywiście, jeśli N jest stałe, to zawsze masz O (1). :)