Otrzymujesz plik, który zawiera wszystkie możliwe liczby w architekturze 32-bitowej. W tym pliku brakuje 4 liczb. Znajdź 4 brakujące liczby

To pytanie do wywiadu, na które natknąłem się kilka razy i naprawdę nie jestem pewien, jak je rozwiązać, biorąc pod uwagę brak czterech liczb. Znam algorytmy wyszukiwania jednej lub dwóch liczb, ale nie widzę sposobu na uogólnienie żadnej z nich na cztery.

Niezależnie od tego, czy chodzi o rozmowę kwalifikacyjną, czy faktyczną pracę, Twoim priorytetem musi być działające rozwiązanie, które ma dla Ciebie sens . Które zwykle oznacza, że należy zaoferować pierwsze rozwiązanie można myśleć, że jest prosty i łatwy do wy wyjaśnić.

Dla mnie oznacza to sortowanie liczb i skanowanie w poszukiwaniu luk. Ale pracuję na systemach biznesowych i aplikacjach internetowych. Nie bawię się kawałkami i nie chcę, żeby mój zespół to zrobił!

Jeśli przeprowadzasz wywiad w sprawie niskiego poziomu, bliższego metalowi zadania, „sortowanie” prawdopodobnie spotka się z pustymi spojrzeniami. Chcą, abyś czuł się swobodnie myśląc o bitach i tak dalej. Twoja pierwsza odpowiedź powinna brzmieć: „Och, użyłbym mapy bitowej”. (Lub tablica bitów lub zestaw bitów.)

A potem, w obu przypadkach - nawet jeśli podasz „złe” rozwiązanie, jeśli Twój ankieter (lub szef!) Naciska na to , możesz zaproponować ulepszenia lub alternatywy, koncentrując się na konkretnym obszarze zainteresowania menedżera.

• Poważnie ograniczona pamięć RAM? Mniej niż 512 MB?
  Posortuj na miejscu, na dysku. Możesz użyć najczęściej dowolnej ilości pamięci RAM, aby zoptymalizować i / lub buforować posortowane bloki.
• Ograniczony czas?
  Użyj tej pamięci RAM! Sortowanie już jest O(n*log(n)). (Lub O (n) dla sortowania według liczb całkowitych!)
• Konserwowalność?
  Co może być łatwiejszego niż sortowanie ?!
• Nie wykazuje znajomości flag / pól bitowych? ( BitSet/ BitMap/ BitArray)
  Cóż OK ... śmiało i użyj a BitArraydo oflagowania „znalezionych liczb”. A następnie wyszukaj 0.
• Przewidywalna złożoność „w czasie rzeczywistym”?
  Użyj rozwiązania bitmapy. Jest to jedno przejście przez plik i kolejne przejście przezBitArray/BitSet(aby znaleźć0). TakO(n)myślę!

Lub cokolwiek.

Rozwiąż swoje obawy . Najpierw rozwiąż problem, używając w razie potrzeby naiwnych rozwiązań. Nie trać czasu na rozwiązywanie problemów, które jeszcze nie istnieją.

Ponieważ jest to plik, zakładam, że możesz wykonywać wiele przejść. Najpierw utwórz tablicę 256 liczników, iteruj po pliku i dla każdego przyrostu liczby licznik indeksowany jako pierwszy bajt liczby. Po zakończeniu większość liczników powinna mieć wartość 2 ^ 24, ale od 1 do 4 liczników powinno mieć niższe wartości. Każdy z tych wskaźników reprezentuje pierwszy bajt jednej z brakujących liczb (jeśli jest mniej niż 4, to dlatego, że wiele brakujących liczb ma ten sam pierwszy bajt).

Dla każdego z tych indeksów utwórz kolejną tablicę 256 liczników i powtórz plik. Tym razem, jeśli pierwszy bajt jest jedną z wcześniejszych wartości, zwiększ licznik w tablicy na podstawie drugiego bajtu. Kiedy skończysz, poszukaj ponownie liczników niższych niż 2 ^ 16, a otrzymasz drugi bajt brakujących liczb, każdy dopasowany do pierwszego bajtu.

Zrób to ponownie dla trzeciego bajtu (zauważ, że potrzebujesz maksymalnie 4 tablic w każdym przebiegu, mimo że po każdym bajcie mogą następować maksymalnie 4 różne bajty) i dla czwartego bajtu, a znalazłeś wszystkie brakujące liczby.

Złożoność czasowa - Złożoność O(n * log n)
przestrzeni - stała !

Edytować:

Właściwie uważałem to za n=2^32parametr, ale liczba brakujących liczb k=4jest również parametrem. Zakładając, k<<nże oznacza to złożoność przestrzeni O(k).

Aktualizacja:

Dla zabawy (i ponieważ obecnie próbuję nauczyć się Rust) zaimplementowałem go w Rust: https://gist.github.com/idanarye/90a925ebb2ea57de18f03f570f70ea1f . Zdecydowałem się na reprezentację tekstową, ponieważ jeden-on będzie go obsługiwał z ~ 2 ^ 32 liczbami ...

Gdyby to była Java, możesz użyć BitSet. Cóż, dwa z nich, ponieważ nie mogą pomieścić wszystkich 32-bitowych liczb. Kod szkieletowy, być może błędny:

BitSet bitsetForPositives = new Bitset(2^31);  // obviously not 2^31 but you get the idea
BitSet bitsetForNegatives = new Bitset(2^31);

for (int value: valuesTheyPassInSomehow) {
  if ((value & 0x80000000) == 0)
     bitsetForPositives.set(value );
  else
     bitsetForNegatives.set(value & ~0x80000000);
}

Następnie użyj, BitSet.nextClearBit()aby dowiedzieć się, kto zaginął.

Uwaga dodana znacznie później:

Zauważ, że dzięki temu algorytmowi równoległe jest uruchamianie czasochłonnej części . Powiedzmy, że oryginalny plik został podzielony na cztery mniej więcej równe części. Przydziel 4 pary BitSetów (2 GB, nadal możliwe do zarządzania).

1. Mają równolegle cztery wątki, każdy przetwarza jeden plik we własną parę bitSetów.
2. Po zakończeniu wróć do pojedynczego wątku lub zestawów bitów (czas trywialny), a następnie czterokrotnie wywołaj nextClearBit (również czas trywialny).

Spodziewałbym się, że operacje wejścia / wyjścia będą nadal krokiem ograniczającym szybkość, ale jeśli magicznie wszystkie liczby byłyby w pamięci, można by naprawdę przyspieszyć.

To pytanie można rozwiązać za pomocą tablicy bitów (prawda / fałsz). Powinna to być najbardziej efektywna struktura do przechowywania odpowiedzi dla wszystkich liczb przy użyciu indeksu tablicy, aby zatrzymać, czy konkretna liczba została znaleziona.

DO#

var bArray = new BitArray(Int32.MaxValue);

//Assume the file has 1 number per line
using (StreamReader sr = File.OpenText(fileName))
{
        string s = String.Empty;
        while ((s = sr.ReadLine()) != null)
        {
            var n = int32.Parse(s);
            bArray[n] = true;
        }
}

Następnie wystarczy wykonać iterację w tablicy, a dla wartości, które nadal są fałszywe, nie ma ich w pliku.

Możesz podzielić plik na mniejsze części, ale udało mi się przydzielić pełną tablicę o maksymalnych rozmiarach int32 (2147483647) na moim laptopie 16,0 GB z systemem Windows 7 (64-bitowym).

Nawet gdybym nie uruchomił wersji 64-bitowej, mógłbym przydzielić mniejsze tablice bitowe. Przetwarzałbym wstępnie plik, tworząc zestaw mniejszych plików, każdy w zakresie [0-64000] [64001-128000] itd., Które byłyby odpowiednie dla dostępnych zasobów środowiska. Przejrzyj duży plik i zapisz każdą liczbę w odpowiednim pliku zestawu. Następnie przetworz każdy mniejszy plik. Zajmie to trochę więcej czasu z powodu etapu wstępnego przetwarzania, ale obejdzie to ograniczenia zasobów, jeśli będą ograniczone zasoby.

Ponieważ jest to pytanie do wywiadu, chciałbym pokazać ankieterowi trochę zrozumienia na temat ograniczeń. Co zatem oznaczają „wszystkie możliwe liczby”? Czy to naprawdę 0 ... 2 <(32-1), jak wszyscy się domyślają? Zwykłe architektury 32-bitowe mogą pracować z wieloma więcej niż tylko 32-bitowymi liczbami. Oczywiście to tylko kwestia reprezentacji.

Czy należy to rozwiązać w systemie 32-bitowym, czy jest to raczej część ograniczenia liczbowego? Na przykład typowy system 32-bitowy nie będzie w stanie załadować pliku do pamięci RAM jednocześnie. Wspomnę również, że system 32-bitowy często nie może mieć pliku zawierającego wszystkie liczby z powodu ograniczenia rozmiaru pliku. Cóż, chyba że ma jakieś sprytne kodowanie, takie jak „Wszystkie liczby oprócz tych czterech”, w którym to przypadku problem został rozwiązany w sposób trywialny.

Ale jeśli naprawdę chcesz zrozumieć pytanie jako „Biorąc pod uwagę plik ze wszystkimi liczbami od 0 ... 2 ^ (32-1) oprócz kilku, podaj mi brakujące” (a to duże, jeśli !), To istnieje wiele sposobów rozwiązania tego problemu.

Trywialne, ale niewykonalne: dla każdego możliwego numeru przeskanuj plik i sprawdź, czy tam jest.

Z 512 MB pamięci RAM i pojedynczym przejściem przez plik: zaznacz każdą liczbę (= ustaw bit przy tym indeksie) odczytaną z pliku, a następnie przepuść raz pamięć RAM i zobacz brakujące.

Jednym podejściem, które jest łatwe do zapamiętania i wyrażenia w wywiadzie, byłoby wykorzystanie faktu, że jeśli spojrzysz na wszystkie liczby w N bitach, każdy bit zostanie ustawiony dokładnie w połowie tych wartości, a nie w drugiej połowie .

Jeśli powtórzysz wszystkie wartości w pliku i zachowasz 32 wartości na końcu, otrzymasz 32 wartości, które są dokładnie (2 ^ 32/2) lub nieco mniejsze od tej wartości. Różnica między maksimum (2 ^ 32/2) a sumą daje całkowitą liczbę bitów ustawioną w każdej pozycji brakujących wartości.

Gdy to zrobisz, możesz określić wszystkie możliwe zestawy 4 wartości, które mogłyby dać te sumy. Biorąc to pod uwagę, możesz ponownie przejrzeć wartości w pliku, sprawdzając, czy są to wartości należące do tych kombinacji. Kiedy je znajdziesz, kombinacje zawierające tę wartość są eliminowane jako możliwości. Gdy masz tylko jedną możliwą kombinację, musisz odpowiedzieć.

Na przykład za pomocą skubka masz następujące wartości:

1010
0110
1111
0111
1101
1001
0100
0101
0001
1011
1100
1110

Całkowita liczba bitów ustawionych dla każdej pozycji wynosi:

7867

Odejmując te od 8 (4 ^ 2/2) otrzymujemy:

1021

Co oznacza, że ​​istnieją następujące możliwe zestawy 4 wartości:

1000
0000
0011
0010

1010
0001
0010
0000

(wybacz mi, jeśli coś przeoczyłem, robię to tylko na podstawie wzroku)

A potem, patrząc ponownie na oryginalne liczby, od razu znajdujemy 1010, co oznacza, że ​​pierwszy zestaw był odpowiedzią.

Zakładając, że plik jest sortowany według rosnących liczb:

Upewnij się, że rzeczywiście zawiera (2³²-4) liczby.
Teraz, jeśli plik był kompletny (lub jeśli 4 brakujące liczby były ostatnimi 4), odczytanie dowolnego słowa w pliku w pozycji N zwróci pasującą wartość N.

Użyj wyszukiwania dychotomii w pozycjach [0..2³²-4-1), aby wyszukać pierwszą nieoczekiwaną liczbę X1.
Po znalezieniu pierwszego brakującego numeru, ponownie przeszukaj dichtotomię w pozycjach [X1 .. (2³²-4-1)], aby znaleźć drugą brakującą liczbę, X2: Tym razem czytanie słowa w pozycji N powinno zwrócić pasującą wartość N-1 jeśli nie było już więcej brakujących liczb (ponieważ przekazałeś jedną brakującą liczbę).
Powtórz podobnie dla dwóch pozostałych liczb. Przy trzeciej iteracji czytanie słowa w pozycji N powinno zwrócić N-2, a przy czwartej powinno zwrócić N-3.

Zastrzeżenie: Nie testowałem tego. Ale myślę, że powinno działać. :)

Teraz w prawdziwym życiu zgadzam się z innymi odpowiedziami: pierwsze pytania dotyczyłyby środowiska. Czy mamy dostępną pamięć RAM (ile), czy plik znajduje się na urządzeniu pamięci masowej z dostępem bezpośrednim, czy jest to operacja jednorazowa (nie wymaga optymalizacji) lub krytyczna (każda liczba cykli), czy mamy dostępne narzędzie do sortowania zewnętrznego itd.
Następnie znajdź kompromis akceptowalny w kontekście. To przynajmniej pokazuje, że zaczynasz analizować problem, zanim zaczniesz szukać algorytmu.

Podobnie jak w przypadku wszystkich standardowych pytań, rozwiązaniem jest wyszukanie ich w Google przed rozmową.

To pytanie i odmiany mają bardzo wyraźną „poprawną” odpowiedź obejmującą XORing wszystkich liczb. Ma pokazać, że rozumiesz indeksy w bazach danych lub coś w tym rodzaju. Zatem zero punktów dla każdego „może działać, ale nie to, co jest napisane na papierze”, odpowiedz im afriad.

Na plus jest skończony zestaw tych pytań. Kilka godzin rewizji sprawi, że będziesz wyglądać jak geniusz. Pamiętaj tylko, aby udawać, że pracujesz nad tym w swojej głowie.

Edytować. Ahh wydaje się, że dla 4 istnieje inne podejście niż XOR

http://books.google.com/books?id=415loiMd_c0C&lpg=PP1&dq=muthukrishnan%20data%20stream%20algorithms&hl=el&pg=PA1#v=onepage&q=muthukrishnan%20data%20stream%20algorithms&f=false

Edytować. Downvoters: Jest to opublikowane w podręczniku O (n) rozwiązanie dokładnie problemu określonego w PO.