Zwei Murmeln und ein 100-stöckiges Gebäude

https://stackoverflow.com/questions/6547

08-06-2019
|

Frage

Eine dieser klassischen Programmierinterviewfragen ...

Sie erhalten zwei Murmeln und erfahren, dass sie zerbrechen, wenn sie aus einer bestimmten Höhe fallen gelassen werden (und vermutlich keinen Schaden erleiden, wenn sie aus einer bestimmten Höhe fallen gelassen werden).Sie werden dann zu einem 100-stöckigen Gebäude geführt (vermutlich höher als die bestimmte Höhe) und werden gebeten, möglichst effizient das höchste Stockwerk zu finden, von dem aus Sie eine Murmel fallen lassen können, ohne sie zu zerbrechen.

Zusatzinformation

Sie müssen den richtigen Boden finden (kein möglicher Bereich)
Es ist garantiert, dass beide Murmeln auf derselben Etage zerbrechen
Gehen Sie davon aus, dass Sie für den Bodenwechsel keine Zeit benötigen – nur die Anzahl der Marmortropfen zählt
Gehen Sie davon aus, dass die richtige Etage im Gebäude zufällig verteilt ist

Lösung

Das Interessante dabei ist, wie man es mit möglichst wenigen Tropfen erreichen kann.In die 50. Etage zu gehen und die erste fallen zu lassen, wäre katastrophal, wenn die brechende Etage die 49. ist, was dazu führt, dass wir 50 Drops machen müssen.Wir sollten die erste Murmel auf Etage n fallen lassen, wobei n die maximal erforderliche Anzahl an Tropfen ist.Wenn die Murmel auf der Etage n zerbricht, müssen wir danach möglicherweise n-1 Tropfen machen.Wenn die Murmel nicht zerbricht, gehen wir auf die Etage 2n-1 und wenn sie hier zerbricht, müssen wir im schlimmsten Fall die zweite Murmel n-2 Mal fallen lassen.So machen wir bis zum 100. Stockwerk weiter und versuchen, es bei 3n-2, 4n-3... zu durchbrechen.
und n+(n-1)+(n-2)+...1 <=100
n=14 Ist die maximal erforderliche Anzahl an Drops

Andere Tipps

Dieses Problem wird in Problem 6.5 aus Buch „Das Coding-Interview knacken (5.)", mit Lösungen wie folgt zusammengefasst:

Überwachung:

Unabhängig davon, wie wir Marble1 löschen, muss Marble2 eine lineare Suche durchführen.ZB, wenn der Marmor1 zwischen den Boden 10 und 15 bricht, müssen wir jeden Stock zwischen dem Marmor 2 überprüfen

Die Vorgehensweise:

Ein erster Versuch: Angenommen, wir lassen eine Murmel aus dem 10. Stock fallen, dann aus dem 20. …

In den ersten Murmelpausen beim ersten Drop (Etage 10) haben wir dann insgesamt höchstens 10 Drops.
Wenn der erste Marmor im letzten Tropfen (Boden 100) bricht, haben wir höchstens 19 Tropfen insgesamt (Böden 1 bis 100, dann 91 bis 99).
Das ist ziemlich gut, aber alles, woran wir denken, ist der absolut schlimmste Fall.Wir sollten einige „Lastausgleich“ durchführen, um diese beiden Fälle gleichmäßiger zu gestalten.

Ziel: Erstellen Sie ein System zum Fallenlassen von Marble1, damit die Anzahl der erforderlichen Drops konsistent ist, unabhängig davon, ob Marble1 beim ersten Drop oder beim letzten Drop zerbricht.

Ein perfektes, ausgewogenes System wäre eines, bei dem Marmortropfen von Marmor2 immer gleich sind, unabhängig davon, wo Marble1 gebrochen wurde.
Damit dies der Fall ist, ist Marble2, da jeder Tropfen Marble1 einen weiteren Schritt macht, einen Schritt weniger.
Wir müssen daher die Anzahl der Schritte reduzieren, die marble2 jedes Mal durch einen Tropfen benötigt werden.Wenn Marble1 beispielsweise auf dem Boden 20 und dann auf Boden 30 fallen gelassen wird, muss Marble2 möglicherweise 9 Stufen unternehmen.Wenn wir Marble1 wieder fallen lassen, müssen wir potenzielle Marble2-Schritte auf nur 8 reduzieren.Beispielsweise müssen wir Marble1 auf Etage 39 ablegen.
Wir wissen daher, dass Marble1 in Floor X beginnen muss und dann mit X-1-Böden, dann X-2,… bis zu 100 angeht.
Lösen Sie nach X+(X-1)+(X-2)+…+1 = 100 auf.X(X+1)/2 = 100 -> X = 14

Wir gehen zur 14. Etage, dann zur 27., dann zur 39. Etage, … Dies dauert maximal 14 Schritte.

Code & Erweiterung:

Informationen zur Code-Implementierung finden Sie hier Hier.
Für die Erweiterung auf N Murmeln, M Böden, check out Kapitel 12:Das Rätsel aus Eiern und Böden .

Sie brechen alle, wenn sie aus der gleichen Höhe fallen gelassen werden, oder sind sie unterschiedlich?

Wenn sie gleich sind, gehe ich in den 50. Stock und lasse die erste Murmel fallen.Wenn es nicht kaputt geht, gehe ich in die 75. Etage und mache das Gleiche. Solange es nicht kaputt geht, gehe ich weiter um 50 % des Rests nach oben.Wenn sie kaputt geht, gehe ich zurück zu einer höheren Stelle als zuvor (wenn sie also im 75. Stock kaputt geht, gehe ich zurück in den 51. Stock) und lasse die zweite Murmel fallen und bewege mich jeweils eine Etage nach oben, bis sie zerbricht. An diesem Punkt kenne ich die höchste Etage, aus der ich fallen kann, ohne dass die Marmorplatte zerbricht.

Wahrscheinlich nicht die beste Antwort, ich bin gespannt, wie andere antworten.

Lassen Sie die erste Murmel auf Etage 10, 20, 30 usw. fallen.bis es kaputt geht, dann springe zurück zum letzten bekannten Gut Boden und beginnen Sie, von dort aus eine Etage nach der anderen Murmeln fallen zu lassen.Im schlimmsten Fall handelt es sich bei 99 um den Magic Floor, und Sie können ihn immer in 19 Tropfen oder weniger finden.

Ich persönlich bin kein großer Fan von solchen Rätselfragen, ich bevorzuge tatsächliche Programmierübungen in Vorstellungsgesprächen.

Allerdings hängt es zunächst davon ab, ob ich anhand des Bodens, auf den ich sie fallen lasse, erkennen kann, ob sie kaputt sind oder nicht.Ich gehe davon aus, dass ich es kann.

Ich ging in den zweiten Stock und ließ die erste Murmel fallen.Wenn es kaputt gehen würde, würde ich es im ersten Stock versuchen.Wenn das kaputt ginge, wüsste ich, dass es kein Boden war.

Wenn der erste nicht kaputt ging, würde ich in den 4. Stock gehen und von dort aus fallen.Wenn das kaputt ginge, würde ich wieder nach unten gehen und die andere Murmel holen und mich dann im 3. Stock fallen lassen, ob kaputt oder nicht, ich wüsste, wo die Grenze liegt.

Wenn keines kaputt gehen würde, würde ich beide holen und den gleichen Vorgang durchführen, diesmal beginnend im 6. Stock.

Auf diese Weise kann ich jedes zweite Stockwerk überspringen, bis ich eine Murmel bekomme, die zerbricht.

Dies wäre optimiert, wenn die Murmel früh bricht ...Ich nehme an, dass es wahrscheinlich eine optimale Anzahl an Stockwerken gibt, die ich überspringen könnte, um bei jedem Überspringen das Beste herauszuholen ...Aber wenn dann eines kaputt geht, müsste ich jedes Stockwerk einzeln überprüfen, vom ersten Stockwerk über dem letzten bekannten Stockwerk ...Was natürlich mühsam wäre, wenn ich zu viele Stockwerke überspringe (leider finde ich momentan nicht die optimale Lösung).

Idealerweise hätte ich gerne eine ganze Tüte Murmeln, dann könnte ich einen binären Suchalgorithmus verwenden und die Anzahl der Stockwerke mit jedem Tropfen halbieren ...aber das war doch nicht die Frage, oder?

Ich denke der real Die Frage ist, wie genau soll die Antwort sein.Denn Ihre Effizienz wird wirklich davon abhängen.

Ich werde Justin zustimmen, wenn Sie eine 100% ige Genauigkeit auf den Murmeln haben möchten, dann müssen Sie nach dem ersten Marmor ausbricht, um nach dem zuletzt bekannten "guten" Boden nach dem anderen zu steigen, bis Sie herausfinden, welcher Boden ist der Gewinner." Vielleicht sogar ein paar Statistiken einwerfen und im 25. Stock anstelle des 50. Stocks beginnen, damit Sie das schlechteste Szenario anstelle von 49 beträgt.

Wenn Ihre Antwort plus oder minus ein oder zwei Untergrenzen sein kann, könnte es einige Optimierungen geben.

Zweitens: Zählt das Auf- und Absteigen der Treppe zu Ihrer Leistungsfähigkeit?Lassen Sie in diesem Fall bei jeder Auf-/Ab-Fahrt immer beide Murmeln fallen und nehmen Sie beide wieder auf.

Lassen Sie die erste Murmel aus dem 3. Stock fallen.Wenn es kaputt geht, wissen Sie, dass es Etage 1 oder 2 ist, also lassen Sie die andere Murmel von Etage 2 fallen.Wenn es nicht kaputt geht, haben Sie festgestellt, dass Etage 2 die höchste ist.Wenn es kaputt geht, haben Sie festgestellt, dass Etage 1 die höchste ist.2 Tropfen.

Wenn die Murmel beim Herunterfallen aus der 3. Etage nicht zerbricht, stürzen Sie sich aus der 6. Etage.Wenn es kaputt geht, wissen Sie, dass Etage 4 oder 5 die höchste ist.Lassen Sie die zweite Murmel von Etage 5 fallen.Wenn es nicht kaputt geht, haben Sie herausgefunden, dass 5 der höchste Wert ist.Wenn ja, ist Etage 4 die höchste.4 Tropfen.

Weitermachen.

3 Etagen – maximal 2 Drops

6 Etagen – maximal 4 Drops

9 Etagen – maximal 6 Drops

12 Etagen – maximal 8 Drops

usw.

3x Etagen - maximal 2x Drops

Bei einem Gebäude mit 99 Stockwerken hätte man also maximal 66 Stürze.Und das ist das Maximum.Sie würden wahrscheinlich weniger Tropfen haben.Oh, und 66 ist auch das Maximum für ein 100-stöckiges Gebäude.Sie würden nur 66 Drops benötigen, wenn der Pausenboden 98 oder 97 wäre.Wenn die Pausenuntergrenze 100 wäre, würden Sie 34 Tropfen verwenden.

Auch wenn Sie gesagt haben, dass es keine Rolle spielt, erfordert dies wahrscheinlich den geringsten Fußmarsch und Sie müssen nicht wissen, wie hoch das Gebäude ist.

Ein Teil des Problems besteht darin, wie Sie Effizienz definieren.Ist es „effizienter“, immer eine Lösung in weniger als x Tropfen zu haben, oder ist es effizienter, eine gute Chance auf eine Lösung in y Tropfen zu haben, wobei y < x ist, mit der Einschränkung, dass es mehr als x Tropfen geben könnte? ?

Mit nur 7 Murmeln geht das besser.

Nehmen wir also nach der abgestimmten Antwort an, dass die Murmel mindestens im 49. Stock bricht.

50. Stock -> Pausen (Antwort liegt zwischen 1 und 50 inklusive)
25. Stock -> geht nicht kaputt (26 bis 50)
37. Stock -> geht nicht kaputt (38 bis 50)
43. Stock -> geht nicht kaputt (44 bis 50)
46. Stock -> geht nicht kaputt (47 bis 50)
48. Stock -> geht nicht kaputt (49 oder 50)
49. Etage -> Pausen (49., dieser Schritt ist tatsächlich erforderlich, da dies möglicherweise die minimale Etage war, in der Murmeln brechen konnten, und zwar bei der 50. Etage)

Man kann sich das so vorstellen, als würde man eine binäre Suche in einer sortierten Menge nach einem k durchführen, wobei wir bei jedem Versuch den Lösungsraum halbieren.Für 100 Stockwerke benötigen wir log2 100 = 6,644 (7 Versuche).Mit 7 Murmeln können wir sicher sein, welches die Mindestetage ist, die Marmor auf bis zu 128 Stockwerke aufbrechen kann.

Als Erstes würde ich den absolut einfachen Algorithmus verwenden, der bei Etage 1 beginnt und die Murmel eine Etage nach der anderen fallen lässt, bis sie 100 erreicht oder die Murmel zerbricht.

Dann würde ich fragen, warum ich Zeit damit verbringen sollte, es zu optimieren, bis jemand nachweisen kann, dass es ein Problem sein wird.Allzu oft sind die Leute damit beschäftigt, den perfekten komplizierten Algorithmus zu finden, während ein viel einfacherer das Problem lösen kann.Mit anderen Worten: Optimieren Sie Dinge erst, wenn sie benötigt werden.

Dies könnte eine Fangfrage sein, um herauszufinden, ob Sie zu den Menschen gehören, die aus einem Maulwurfshügel einen Berg machen können.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow