Hintergrund:
Ich habe diese Frage gestern Abend ursprünglich gepostet und eine Antwort auf ihre Unbestimmtheit erhalten. Ich habe seitdem viele Mitarbeiter nicht nur zum Wortlaut des Problems befragt, sondern auch zu seiner Komplexität (die nicht O (1) ist). Dieses Programmierproblem ist eine böse Wendung in einer Amazon-Interviewfrage.
Frage:
Bei einer Folge von zufällig verketteten ganzen Zahlen (0, 250), 0 bis 250 exklusiv, fehlt EINE Zahl in der Folge. Ihre Aufgabe ist es, ein Programm zu schreiben, das diese fehlende Zahl berechnet. Es gibt keine anderen fehlenden Zahlen in der Sequenz außer der einen, und das macht dieses Problem so schwierig und möglicherweise rechenintensiv.
Dieses Problem von Hand mit kleineren Zeichenfolgen wie den Beispielen 1 und 2 zu lösen, ist offensichtlich sehr einfach. Umgekehrt wäre die Berechnung einer fehlenden Zahl für unglaublich große Datensätze mit dreistelligen oder vierstelligen Zahlen unglaublich schwierig. Die Idee hinter diesem Problem ist, ein Programm zu erstellen, das diesen Prozess für Sie erledigt.
Wichtige Informationen:
Eine Sache, die als ziemlich verwirrend erschien, als ich dieses Problem letzte Nacht postete, war: als was genau eine fehlende Zahl definiert wird. Eine fehlende Nummer ist die Nummer INNERHALB des oben angegebenen Bereichs. NICHT unbedingt die Ziffer. In Beispiel 3 sehen Sie, dass die fehlende Zahl 9 ist, obwohl sie in der Sequenz erscheint. Es gibt 3 Stellen, an denen DIGIT 9 in einer Reihe von [0, 30] angezeigt wird: "9", "19" und "29". Ihr Ziel ist es, zwischen diesen zu unterscheiden und herauszufinden, dass 9 die fehlende NUMMER ist (in Beispiel 3). Mit anderen Worten, der schwierige Teil besteht darin, herauszufinden, welche Ziffernfolgen vollständig sind und welche zu anderen Zahlen gehören.
Eingang:
Die Eingabe ist eine Zeichenfolge S, die Ganzzahlen von 0 bis 249 (einschließlich) oder 0 bis 250 (ausschließlich) enthält (mit anderen Worten [0, 250]). Diese ganzen Zahlen werden, wie oben angegeben, zu einer zufälligen Folge zusammengesetzt. Es gibt KEINE Begrenzer ("42, 31, 23, 44") oder Auffüllungs-Nullen (003076244029002). Die Probleme sind genau wie in den Beispielen beschrieben. Es ist garantiert, dass es nur 1 Lösung für die tatsächlichen Probleme gibt. Mehrfachlösungen sind hierfür nicht zulässig.
Gewinnkriterien:
Wer die schnellste und niedrigste Speichernutzung hat, gewinnt. In dem wunderbaren Fall, dass eine Zeit bindet, wird weniger Speicher für den Zeitbrecher verwendet. Bitte listen Sie Big O auf, wenn Sie können!
Beispiele:
Die Beispiele 1 und 2 haben einen Bereich von [0, 10)
Die Beispiele 3 und 4 haben einen Bereich von [0, 30]
(Die Beispiele 1 bis 4 dienen nur zur Veranschaulichung. Ihr Programm muss sie nicht verarbeiten.)
Beispiele 5 haben einen Bereich von [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
, nicht nur250
? / Was ist mit dem232
Problem? Alle Möglichkeiten oder eine? Mir ist klar, dass Sie über dieses Problem Bescheid wussten, aber ich finde es in der Frage unklar. / Wenn dies der schnellste Code ist, muss es eine Möglichkeit geben, sie zu messen. Natürlich unterscheidet sich die Ausführung auf einem Supercomputer von der Ausführung auf einem alten Computer. / Weil das niemand gesagt hat, - Willkommen bei PPCG!N
, um 1000 oder 10000 zu sagen.Antworten:
Clingo , 0,03 Sekunden
Dies ist zu schnell, um genau gemessen zu werden. Sie müssen größere Eingabefälle zulassen, anstatt bei 250 künstlich anzuhalten.
Beispiel Eingabe
Die Eingabe ist eine Liste von ( k , k- te Stelle) Paaren. Hier ist Problem 1:
Beispielausgabe
quelle
45879362100
mitn = 11
und ohne1
(Antwortenmissing(0)
).missing(10)
gilt das auch)?C ++, 5000 zufällige Testfälle in 6,1 Sekunden
Dies ist praktisch schnell, aber es gibt möglicherweise einige Testfälle, die es langsam machen. Komplexität unbekannt.
Wenn es mehrere Lösungen gibt, werden alle gedruckt. Beispiel .
Erläuterung:
Zählen Sie die Vorkommen von Ziffern.
Listen Sie alle möglichen Antworten auf.
Überprüfen Sie, ob ein Kandidat eine gültige Antwort ist:
3-1. Versuchen Sie, die Zeichenfolge (n) durch Zahlen zu teilen, die nur einmal vorkommen, und markieren Sie sie als identifiziert, mit Ausnahme des Kandidaten.
Hat zum Beispiel
2112282526022911192312416102017731561427221884513
nur einen14
, so kann er in211228252602291119231241610201773156
und aufgeteilt werden27221884513
.3-2. Wenn eine geteilte Zeichenfolge die Länge 1 hat, markieren Sie sie als identifiziert.
Wenn ein Widerspruch vorliegt (mehrmals identifiziert), ist der Kandidat ungültig.
Wenn wir den Kandidaten in der Zeichenfolge nicht finden können, ist der Kandidat gültig.
3-3. Wenn eine Teilung vorgenommen wird, wiederholen Sie Schritt 3-1. Führen Sie andernfalls eine Brute-Force-Suche durch, um zu überprüfen, ob der Kandidat gültig ist.
Probieren Sie es online!
quelle
Sauber , ~ 0,3s
Es wurde ein großer Fehler im Algorithmus behoben, der jetzt erneut optimiert werden musste.
Kompilieren mit
clm -h 1024M -s 16M -nci -dynamics -fusion -t -b -IL Dynamics -IL Platform main
Dies funktioniert, indem jede Zahl genommen wird, die die Zeichenfolge enthalten muss, und die Anzahl der Stellen gezählt wird, an denen die erforderliche Ziffernfolge in der Zeichenfolge vorhanden ist. Es werden dann wiederholt die folgenden Schritte ausgeführt:
singles
)singles
) überschneiden.quelle