sprawdź 1 miliard numerów telefonów komórkowych pod kątem duplikatów

To pytanie z wywiadu:

Istnieje 1 miliard numerów telefonów komórkowych, które mają 11 cyfr, są one przechowywane losowo w pliku, dla przykład 12345678910, pierwsza cyfra to 1. Przejrzyj te liczby, aby zobaczyć, czy jest jeden z duplikatem, po prostu sprawdź, czy duplikat istnieje, jeśli duplikat został znaleziony, return True, or return False. dozwolone tylko 10 MB pamięci.

Oto moje rozwiązanie:

Podziel wszystkie te liczby na 1000 plików używając hash(num)%1000, duplikaty powinny trafić do tego samego pliku.

Po hashowaniu mam 1000 małych plików, z których każdy zawiera 1 million liczby at most, prawda? Nie jestem tego pewien, po prostu to robię 1 billion / 1000 = 1 million.

Następnie dla każdego pliku zbuduj tabelę hash, aby przechowywać każdą liczbę i flag reprezentującą jej wystąpienie.

Myślę, że potrzeba 5 B, aby przedstawić liczbę, 4 B dla dolnego 8 digits i 1 B dla górnego 3 digits; a właściwie 1 bit wystarczy flag, bo muszę się tylko dowiedzieć, czy duplikat istnieje, tylko ile razy. Ale jak mogę zastosować flagę 1 bit do każdej liczby? Jestem potknięty, więc wybieram bool być flagą, 1 B jest zajęte. Na koniec, każda liczba w tabeli hash przyjmie 5B<for number> + 1B<for flag> + 4B<for the next-pointer> = 10B, a następnie każdy plik przyjmie 10M dla tabeli hash.

To moje głupie rozwiązanie, proszę daj mi lepsze.

Dzięki.

KONTYNUACJA:

Jeśli są no duplicates w tych 1 miliard numerów telefonów, biorąc pod uwagę jeden numer telefonu, jak sprawdzić podany is or is not in Te 1 miliard liczb? Użyj jak najmniej pamięci.

Wymyśliłem 2 rozwiązania,

  1. Numer telefonu może być reprezentowany za pomocą 5B, jak powiedziałem powyżej, przeskanuj plik, odczytaj jeden numer raz, i xor the given number with the one read from the file, jeśli wynik to 0, to podany jest w pliku, zajmie to O(n) czas, prawda?

  2. Partition liczby te do 2 small files leading bit, co oznacza, że te liczby z leading 1-bit idą do pliku, leading 0-bit idą do innego pliku, tymczasem policz ile liczb w każdym pliku, jeśli dana liczba spadnie do pliku 1-bitowego, a plik 1-bitowy count jest not full, to again partition plik 1-bitowy zgodnie z secondary leading-bit, i sprawdź podaną liczbę rekurencyjnie; jeśli plik 1-bitowy is full, to numer musi być w aktach, to zajmie O(logn) czasu, prawda?

Author: Community, 2011-10-09
Source

6 answers

Najszybsze rozwiązanie (również pod względem programatora:) 

# Generate some 'phones'
yes 1 | perl -wne 'chomp; ++$a; print $_."$a\n";' > phones.txt

# Split phones.txt in 10MB chunks
split -C 10000000 phones.txt

# Sort each 10MB chunk with 10MB of memory
for i in x??; do sort -S 10M $i > $i.srt; echo -ne "$i.srt\0" >> merge.txt; done

# Merge the shorted chunks with 10MB of memory
sort -S 10M --files0-from=merge.txt -m > sorted.txt

# See if there is any duplicates
test -z $(uniq -d merge.txt)

Sprawdź, czy ograniczenie użycia pamięci jest spełnione z pmap $(pidof sort) na przykład:

 14
Author: piotr,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-10-09 22:19:29

Po hashowaniu otrzymałem 1000 małych plików, z których każdy zawiera 1 co najwyżej milion liczb, prawo

Nieprawda, w skrajnym przypadku jest możliwe, że jeden plik zawiera wszystkie liczby.

Utwórz pliki na podstawie pierwszych lub ostatnich x cyfr liczb (zignoruj początkowy 1). Podczas tworzenia tych plików można faktycznie wyciąć te cyfry, ponieważ są one równe w pliku. Jest to o wiele lepsze niż hashowanie, ponieważ chociaż wszystkie liczby mogą się jeszcze skończyć w jednym pliku, teraz zakres tych liczb jest ograniczony, więc można zmieścić go do 10MB.

Każda liczba może być stłumiona prostym bitem, ponieważ jedyną potrzebną informacją jest to, czy liczba wystąpiła wcześniej. Nie musisz przechowywać liczb rzeczywistych, adres bitu jest liczbą. W 10MB możesz zapisać 80m bitów, więc będziesz potrzebował plików 1G/80M = 12,5, ale pamiętaj, że te cyfry muszą się różnić, więc faktycznie będziesz potrzebował 100 plików (x=2).

Wreszcie, ty nie trzeba tworzyć tych plików, można również skanować cały plik wiele razy. W tym przypadku możesz mieć wiele bit-map w pamięci, ponieważ jedna nie zajmuje 10MB.

Zdecydowanie sugeruję przeczytanie tej książki, zaczyna się ona od niemal identycznego przykładu: http://www.amazon.co.uk/Programming-Pearls-ACM-Press-Bentley/dp/0201657880

 8
Author: Karoly Horvath,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-10-09 11:34:02

Nie ma potrzeby hashowania, 10M = 83886080 bitów, umieść każdą liczbę w [0, 83886080), [83886080, 83886080 * 2) ... [xx, 99999999999) (Nie bierz pod uwagę pierwszej cyfry), około 9999999999 / 83886080 = 120 plików, następnie zbuduj bit set, zajmuje O (N) całkowicie.

 5
Author: lostyzd,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-10-09 12:56:02

Możesz zastosować technikę bitset. Odnoś się do tego pytania i Odpowiedzi: Znajdź liczbę całkowitą nie spośród czterech miliardów podanych

 2
Author: vine'th,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-05-23 11:45:54

Pytanie podczas rozmowy kwalifikacyjnej nakłada jedynie limit na używaną pamięć, a nie na czas potrzebny na udzielenie odpowiedzi.

Rozsądne jest zatem wdrożenie tego pytania w ten sposób: 

take the first number
compare it to all numbers following it
take the second number
compare it to all numbers following it
...

Przetwarzanie miliardów liczb zajmuje ogromną ilość czasu (O (n^2)), ale nie zajmuje więcej niż 10 MB miejsca w pamięci.

 0
Author: Adrien Plisson,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-10-09 12:02:05

Możesz użyć filtrów Bloom, które zawierają tablicę bitów m i używają funkcji skrótu K. Choć nie jestem pewien, ile funkcji hash może być potrzebne.

 0
Author: NinjaCoder,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-10-10 16:04:45