Wenn Sie Eier vom Dach werfen müssen: Tägliches Codierungsproblem

Tägliches Codierungsproblem 24

Willkommen zurück mit einem weiteren Problem, das es zu lösen gilt! Heute beschäftigen wir uns mit Eiern, die von Dächern fallen, mit diesem wirklich schönen Problem, für das es zwei mögliche Lösungen gibt: eine ziemlich naive und eine cleverere. Letzteres wird uns auch die Gelegenheit geben, über einen ziemlich berühmten Algorithmus zu sprechen.

Das heutige Problem liefert wie immer der wunderbare Newsletter Tägliches Codierungsproblem , das Sie kostenlos abonnieren können, um auch an Ihrer täglichen Programmierherausforderung teilzunehmen. Probieren Sie es aus und versuchen Sie auch, Ihre Probleme zu lösen!

Dann genug geredet; Schauen wir uns das Problem an!

Das Problem

Dieses Problem wurde von Goldman Sachs in einem Vorstellungsgespräch gestellt. Schauen wir uns das Problem an.

Du erhältst N identische Eier und Zugang zu einem Gebäude mit k Etagen. Ihre Aufgabe besteht darin, die unterste Etage zu finden, bei der ein Ei zerbricht, wenn es von dieser Etage herunterfällt. Sobald ein Ei zerbricht, kann es nicht wieder fallen gelassen werden. Wenn ein Ei zerbricht, wenn es aus der xth Etage fällt, können Sie davon ausgehen, dass es auch dann zerbricht, wenn es aus jeder Etage höher als x fällt.

Schreiben Sie einen Algorithmus, der die minimale Anzahl von Probeabwürfen ermittelt, die im schlimmsten Fall erforderlich sind, um diese Etage zu identifizieren.

Wenn beispielsweise N = 1 und k = 5 ist, müssen wir versuchen, das Ei auf jeder Etage abzulegen, beginnend mit der ersten, bis wir die fünfte Etage erreichen. Unsere Lösung lautet also 5 .

Wir erhalten also einige Eier, die wir von verschiedenen Etagen eines Gebäudes aus werfen können. Wir sind traurig, dass ab einem bestimmten Boden (den wir targetFloor nennen) weggeworfene Eier nicht zerbrechen, wenn sie zu Boden fallen.

Von dieser Etage bis zu jeder Etage darunter zerbrechen die Eier nicht, wenn sie aus dem Fenster geworfen werden. Unsere Aufgabe besteht darin, eine effiziente Methode zum Finden des targetFloor zu finden.

Wie erwartet werden wir zwei Methoden sehen, um dieses Problem zu lösen: eine wirklich einfache, die die Lösung brutal erzwingt, aber nicht effizient ist. Die zweite Methode ist viel effizienter und versucht, das Problem durch Unterbrechen der geringsten Anzahl von Schritten zu lösen.

Es wird uns auch die Gelegenheit geben, über einen wirklich berühmten und wichtigen Algorithmus zu sprechen; Einer von denen, die Sie kennen müssen, um … im Grunde alles zu tun!

Einrichten der Umgebung

Zu Beginn müssen wir ein wenig Umgebung einrichten, nämlich das Gebäude und den targetFloor . Um das Gebäude zu erstellen, erstellen wir einfach ein Array mit den Nummern der Stockwerke, vom Erdgeschoss bis zum ersten Stockwerk. Dann generieren wir eine Zufallszahl, die unser targetFloor sein wird.

Wir werden dieses Problem noch einmal in Go schreiben: einfach genug, um lesbar zu sein, aber komplex genug, um die innere Mechanik zu verstehen.

Zuerst erstellen wir das Array, das als unser Gebäude dienen soll: Wir können ihm die gewünschte Größe geben, je größer die Größe, desto höher wird das Gebäude sein. Danach erstellen wir eine Instanz von targetFlor mithilfe des in Go integrierten math/rand Moduls.

Im Grunde erstellen wir eine neue zufällige Ganzzahl zwischen 0 und der Höhe des Gebäudes (… der Länge des Arrays :D), wobei wir als Quelle die aktuelle Zeit verwenden.

Die Brute-Force-Lösung

Die einfachste mögliche Lösung wäre natürlich, jedes Ei auf jeder Etage rauszuwerfen, um zu sehen, auf welcher Etage die Eier anfangen zu zerbrechen. Da wir eine Variable haben, die diese Informationen enthält, könnte man einfach eine for-Schleife ausführen, um das Problem zu lösen:

Obwohl dies die einfachste Lösung ist, ist sie leider äußerst ineffizient. Stellen Sie sich vor, der rechte Boden wäre der oberste: Man müsste 100.000 Eier zerschlagen, um das Problem zu lösen: Das wäre ein riesiges Omelett, aber eine ziemliche Verschwendung!

Im Allgemeinen hat diese Lösung eine zeitliche Komplexität von O(n), da die Komplexität der Lösung linear mit der Komplexität des Eingabeproblems wächst. Dies ist jedoch nicht die effizienteste Lösung, die wir uns vorstellen können.

Eine effiziente Lösung

Dann lassen Sie uns über eine effiziente Lösung nachdenken. Anstatt Etage für Etage zu gehen und jedes Ei auf jeder Etage zu zerschlagen, könnten wir eine Vermutung anstellen und, basierend auf dem Ergebnis dieser Vermutung, die nächste Vermutung anpassen.

Hier ist ein Beispiel: Angenommen, wir haben ein Gebäude mit 10 Stockwerken und die targetFloor ist die 7. Etage (das wissen wir natürlich nicht). Wir könnten die folgenden Vermutungen annehmen:

Grundsätzlich gehen wir davon aus, dass targetFloor das mittlere Stockwerk des Gebäudes ist. Wir werfen das Ei von dort aus und die möglichen Ergebnisse sind zwei:

• das Ei zerbricht, was bedeutet, dass wir zu high sind. Wir können die Etage höher als diese verwerfen und mit unseren Vermutungen weitermachen.

• Das Ei zerbricht nicht, was bedeutet, dass wir zu niedrig oder auf dem richtigen Boden sind. Wir verwerfen jede Etage tiefer als diese, einschließlich und

Vor diesem Hintergrund nehmen wir nun eine weitere fundierte Vermutung über das mittlere Stockwerk oder das „verbleibende“ Gebäude an und wenden die gleiche Strategie wie oben an. Wir können mit diesem Ansatz fortfahren, bis nur noch eine Etage übrig ist.

Wenn Sie diesen Ansatz kennen, haben Sie völlig Recht: Es handelt sich lediglich um eine binäre Suche , die auf ein Problem aus der „realen Welt“ angewendet wird. Die binäre Suche ist ein einfacher und übersichtlicher Divide-and-Conquer- Algorithmus, was bedeutet, dass sich die Größe des Problems bei jedem Schritt halbiert, bis wir die Lösung finden.

Dies bedeutet, dass dieser Algorithmus im Vergleich zum vorherigen viel schneller ist. Schauen wir uns den Code an!

Werfen wir einen genaueren Blick. Die binäre Suchfunktion akzeptiert 4 Argumente:

• overArray , ein Array von Ganzzahlen, das das Gebäude ist, über das wir eine Schleife durchlaufen;

• bottom , der untere Index des Gebäudes;

• top , der Index der obersten Etage des Gebäudes;

• breakFloor , die Variable mit targetFloor um zu überprüfen, ob wir sie im Gebäude finden können.

Danach durchlaufen wir eine Schleife über das Gebäude, wobei bottom tiefer als top liegt: Wenn sich bei der binären Suche die beiden Positionsargumente verschränken und vertauschen, bedeutet dies, dass das gesuchte Element nicht gefunden wurde.

Wenn der Algorithmus also in dieser Situation endet, endet die Schleife und wir geben -1 zurück, was bedeutet, dass das gesuchte Element nicht im Array vorhanden war. Wenn wir immer noch nach dem Element suchen, wenden wir das an, was im Bild oben gezeigt wird.

Wir berechnen das middlePoint Element als Boden zwischen bottom und top und prüfen, ob middlePoint == breakFloor . Wenn ja, geben wir den middlePoint als Ergebnis zurück.

Ist dies nicht der Fall, passen wir bottom oder top entsprechend an: Wenn middlePoint größer als breakFloor ist, bedeutet dies, dass wir uns zu hoch auf dem Gebäude befinden. Daher senken wir unsere Vorhersage, indem wir die top Etage auf middlePoint — 1 setzen.

Wenn middlePoint kleiner als breakFloor ist, passen wir unseren bottom an, indem wir ihn auf middlePoint+1 setzen.

Um nun alles zu überprüfen, generieren wir in der main die Umgebung wie zuvor und erstellen eine neue Variable namens bsFloor , die unser Ergebnis enthält.

Um zu bestätigen, dass unser Algorithmus zum richtigen Ergebnis geführt hat, drucken wir sowohl bsFloor als auch targetFloor aus, die zuvor zufällig generiert wurden.

Zeitkomplexität

Wie wir bereits erwartet haben, ist dieser Algorithmus viel schneller als der lineare. Da wir das Gebäude bei jedem Schritt halbieren, können wir die richtige Etage in log₂(n) finden, wobei n gleich len(building) ist.

Dies bedeutet, dass die zeitliche Komplexität dieses Algorithmus O(log(n)) beträgt. Um Ihnen einen Vergleich zwischen der linearen Lösung und dieser letzten zu ermöglichen: Wenn das Gebäude 100 Stockwerke hat, benötigt der lineare Algorithmus im schlimmsten Fall 100 Iterationen, während der binäre Suchalgorithmus log₂100 = 6,64, also 7 Iterationen, benötigt.

Außerdem ist letzteres zunehmend effizienter als die lineare, da die binäre Suche umso effizienter ist, je mehr das Gebäude wächst. Für ein Gebäude mit 1.000.000.000 Stockwerken benötigt die lineare Methode 1.000.000.000 Schritte, während die binäre Methode log₂1.000.000.000 = 29,9 benötigt, also 30 Schritte. Eine enorme Verbesserung!

Abschluss

Das ist es! Ich hoffe, dass Ihnen der Artikel genauso gut gefallen hat wie mir der Versuch, die Herausforderung zu lösen! Wenn ja, lasst bitte ein oder zwei Klatschen da, es wäre eine tolle Unterstützung! Wenn Ihnen diese Art von Artikeln gefällt und Sie mehr sehen möchten, folgen Sie der Seite, da ich diese Art von Inhalten jedes Mal veröffentliche, wenn ich kann.

Wenn Sie diesen Artikel schließlich interessant oder hilfreich fanden und mit einem Kaffee einen Beitrag leisten möchten, können Sie dies gerne auf meiner Website tun Ko-Fi Seite!

Und wie immer vielen Dank fürs Lesen!

Nicola

Auch hier veröffentlicht