Tło:
Pierwotnie zadałem to pytanie zeszłej nocy i otrzymałem odrazę z powodu niejasności. Od tamtej pory skonsultowałem się z wieloma pracownikami nie tylko w sprawie treści problemu, ale także jego złożoności (która nie jest O (1)). Ten problem z programowaniem jest złym spinem w pytaniu na wywiad w Amazon.
Pytanie:
Biorąc pod uwagę ciąg losowo połączonych liczb całkowitych [0, 250), od 0 do 250 wyłącznych, w sekwencji brakuje JEDNEJ liczby. Twoim zadaniem jest napisanie programu, który obliczy tę brakującą liczbę. Nie ma żadnych innych brakujących liczb w sekwencji poza jedną, i to sprawia, że ten problem jest tak trudny i prawdopodobnie trudny obliczeniowo.
Ręczne rozwiązywanie tego problemu na mniejszych ciągach, takich jak przykłady 1 i 2 poniżej, jest oczywiście bardzo łatwe. I odwrotnie, obliczenie brakującej liczby na niewiarygodnie dużych zestawach danych obejmujących liczby trzycyfrowe lub czterocyfrowe byłoby niezwykle trudne. Ideą tego problemu jest skonstruowanie programu, który wykona ten proces DLA Ciebie.
Ważna informacja:
Jedną rzeczą, która wydała mi się dość myląca, kiedy opublikowałem ten problem zeszłej nocy, było: co dokładnie oznacza brakująca liczba. Brakująca liczba to liczba WEWNĘTRZNA zakresu określonego powyżej; Niekoniecznie cyfra. W przykładzie 3 zobaczysz, że brakująca liczba to 9, mimo że pojawia się w sekwencji. Istnieją 3 miejsca, w których DIGIT 9 pojawi się w serii [0, 30): „9”, „19” i „29”. Twoim celem jest rozróżnienie między nimi i odkrycie, że 9 to brakująca LICZBA (w przykładzie 3). Innymi słowy, trudna część polega na ustaleniu, które sekwencje cyfr są kompletne, a które należą do innych liczb.
Wkład:
Dane wejściowe to String S, zawierające liczby całkowite od 0 do 249 włącznie lub od 0 do 250 wyłącznie (innymi słowy, [0, 250)). Te liczby całkowite, jak wspomniano powyżej, są szyfrowane, aby utworzyć losową sekwencję. Nie ma żadnych ograniczników („42, 31, 23, 44”) ani dopełniania zer (003076244029002); problemy są dokładnie takie, jak opisano w przykładach. Gwarantowane jest, że istnieje tylko 1 rozwiązanie rzeczywistych problemów. Wiele rozwiązań jest dla nich niedozwolonych.
Zwycięskie kryteria:
Zwycięzcą zostanie ten, kto ma najszybsze i najniższe zużycie pamięci. W cudownym wydarzeniu, które wiąże czas, do przerywnika czasu zostanie użyta mniejsza pamięć. Proszę wymienić Big O, jeśli potrafisz!
Przykłady:
Przykłady 1 i 2 mają zakres [0, 10)
Przykłady 3 i 4 mają zakres [0, 30)
(Przykłady 1-4 są tylko dla celów demonstracyjnych. Twój program nie musi się z nimi obchodzić).
Przykłady 5 mają zakres [0, 250)
1. 420137659
- Missing number => 8
2. 843216075
- Missing number => 9
3. 2112282526022911192312416102017731561427221884513
- Missing number => 9
4. 229272120623131992528240518810426223161211471711
- Missing number => 15
5. 11395591741893085201244471432361149120556162127165124233106210135320813701207315110246262072142253419410247129611737243218190203156364518617019864222241772384813041175126193134141008211877147192451101968789181153241861671712710899168232150138131195104411520078178584419739178522066640145139388863199146248518022492149187962968112157173132551631441367921221229161208324623423922615218321511111211121975723721911614865611197515810239015418422813742128176166949324015823124214033541416719143625021276351260183210916421672722015510117218224913320919223553222021036912321791591225112512304920418584216981883128105227213107223142169741601798025
- Missing number => 71
Test Data:
Problem 1: 6966410819610521530291368349682309217598570592011872022482018312220241246911298913317419721920718217313718080857232177134232481551020010112519172652031631113791105122116319458153244261582135510090235116139611641267691141679612215222660112127421321901862041827745106522437208362062271684640438174315738135641171699510421015199128239881442242382361212317163149232839233823418915447142162771412092492141987521710917122354156131466216515061812273140130240170972181176179166531781851152178225242192445147229991613515911122223419187862169312013124150672371432051192510724356172282471951381601241518410318414211212870941111833193145123245188102
Problem 2: 14883423514241100511108716621733193121019716422221117630156992324819917158961372915140456921857371883175910701891021877194529067191198226669314940125152431532281961078111412624224113912011621641182322612016512820395482371382385363922471472312072131791925510478122073722091352412491272395020016194195116236186596116374117841971602259812110612913254255615723013185162206245183244806417777130181492211412431591541398312414414582421741482461036761192272120204114346205712198918190242184229286518011471231585109384415021021415522313136146178233133168222201785172212108182276835832151134861116216716910511560240392170208215112173234136317520219
Problem 3: 1342319526198176611201701741948297621621214122224383105148103846820718319098731271611601912137231471099223812820157162671720663139410066179891663131117186249133125172622813593129302325881203242806043154161082051916986441859042111711241041590221248711516546521992257224020174102234138991752117924457143653945184113781031116471120421331506424717816813220023315511422019520918114070163152106248236222396919620277541101222101232171732231122301511263822375920856142187182152451585137352921848164219492411071228936130762461191564196185114910118922611881888513917712153146227193235347537229322521516718014542248813617191531972142714505519240144
Problem 4: 2492402092341949619347401841041875198202182031161577311941257285491521667219229672211881621592451432318618560812361201172382071222352271769922013259915817462189101108056130187233141312197127179205981692121101632221732337196969131822110021512524417548627103506114978204123128181211814236346515430399015513513311152157420112189119277138882021676618323919018013646200114160165350631262167910238144334214230146151171192261653158161213431911401452461159313720613195248191505228186244583455139542924222112226148941682087115610915344641782142472102436810828123731134321131241772242411722251997612923295223701069721187182171471055710784170217851
N, a nie tylko 250? / Co z 232problemem? Wszystkie możliwości czy jedna? Zdaję sobie sprawę, że wiedziałeś o tym problemie, ale pytanie jest dla mnie niejasne. / Jeśli jest to najszybszy kod , musi istnieć sposób ich zmierzenia. Oczywiście działanie na superkomputerze różni się od działania na starym komputerze. / Ponieważ nikt tego nie powiedział: - Witamy w PPCG!
N, powiedzmy, 1000 lub 10000.