Leichte Interviewfrage wurde schwieriger: Finden Sie bei den Zahlen 1..100 die fehlende(n) Zahl(en), wenn genau k fehlen

Question

Ich hatte vor einiger Zeit eine interessante Erfahrung bei einem Vorstellungsgespräch. Die Frage begann ganz einfach:

Q1 : Wir haben eine Tasche mit Zahlen 1 , 2 , 3 , , 100 . Jede Zahl kommt genau einmal vor, also gibt es 100 Zahlen. Nun wird eine Zahl zufällig aus dem Beutel gezogen. Finde die fehlende Zahl.

Diese Frage habe ich natürlich schon einmal gehört, also habe ich sehr schnell geantwortet:

A1 : Nun, die Summe der Zahlen 1 + 2 + 3 + … + N es (N+1)(N/2) (siehe Wikipedia: Summe der arithmetischen Reihe ). Für N = 100 ist die Summe 5050 .

Wenn also alle Zahlen im Beutel vorhanden sind, ist die Summe genau 5050 . Da eine Zahl fehlt, ist die Summe kleiner als diese, und die Differenz ist diese Zahl. Wir können also die fehlende Zahl finden in O(N) Zeit und O(1) Raum.

Zu diesem Zeitpunkt dachte ich, ich hätte mich gut geschlagen, aber plötzlich nahm die Frage eine unerwartete Wendung:

Q2 : Das ist richtig, aber wie würden Sie das machen, wenn ZWEI Zahlen fehlen?

Ich hatte diese Variante noch nie gesehen/gehört/überlegt, also geriet ich in Panik und konnte die Frage nicht beantworten. Der Interviewer bestand darauf, meinen Gedankengang zu erfahren, also erwähnte ich, dass wir vielleicht mehr Informationen erhalten können, indem wir mit dem erwarteten Produkt vergleichen oder vielleicht einen zweiten Durchlauf machen, nachdem wir einige Informationen aus dem ersten Durchlauf gesammelt haben, usw., aber ich tappte wirklich nur im Dunkeln, anstatt wirklich einen klaren Weg zur Lösung zu haben.

Der Interviewer versuchte, mich zu ermutigen, indem er sagte, dass eine zweite Gleichung in der Tat eine Möglichkeit sei, das Problem zu lösen. An diesem Punkt war ich etwas verärgert (weil ich die Antwort nicht vorher wusste) und fragte, ob dies eine allgemeine (sprich: "nützliche") Programmiertechnik sei oder ob es sich dabei nur um einen Trick/eine Fangfrage handele.

Die Antwort des Interviewers hat mich überrascht: Man kann die Technik verallgemeinern, um 3 fehlende Zahlen zu finden. In der Tat kann man sie verallgemeinern, um Folgendes zu finden k fehlende Zahlen.

Qk : Wenn genau k Zahlen in der Tasche fehlen, wie würden Sie sie effizient finden?

Das war vor ein paar Monaten, und ich konnte immer noch nicht herausfinden, was diese Technik ist. Offensichtlich gibt es eine (N) Zeituntergrenze, da wir alle Zahlen mindestens einmal scannen müssen, aber der Interviewer bestand darauf, dass die ZEIT y SPACE Komplexität des Lösungsverfahrens (abzüglich der O(N) time input scan) ist definiert in k no N .

Die Frage ist hier also einfach:

• Wie würden Sie das Problem Q2 ?
• Wie würden Sie das Problem Q3 ?
• Wie würden Sie das Problem Qk ?

---

Klarstellungen

• Im Allgemeinen gibt es N Zahlen von 1.. N und nicht nur 1..100.
• Ich bin nicht auf der Suche nach der offensichtlichen mengenbasierten Lösung, z. B. mit einer Bit gesetzt , die das Vorhandensein bzw. Nichtvorhandensein jeder Zahl durch den Wert eines bestimmten Bits kodieren, also mit O(N) Bits an zusätzlichem Platz. Wir können uns keinen zusätzlichen Platz im Verhältnis zu N .
• Ich bin auch nicht auf der Suche nach dem offensichtlichen "sort-first"-Ansatz. Dieser und der mengenbasierte Ansatz sind es wert, in einem Interview erwähnt zu werden (sie sind einfach zu implementieren, und je nach N kann sehr praktisch sein). Ich bin auf der Suche nach der Lösung des Heiligen Grals (die praktisch umsetzbar sein kann oder auch nicht, aber dennoch die gewünschten asymptotischen Eigenschaften aufweist).

Auch hier müssen Sie natürlich die Eingabe in O(N) aber Sie können nur eine kleine Menge an Informationen erfassen (definiert in Form von k no N ), und muss dann die k irgendwie fehlende Zahlen.