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  , 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!   Tägliches Codierungsproblem  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.      identische Eier und Zugang zu einem Gebäude mit   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   Etage fällt, können Sie davon ausgehen, dass es auch dann zerbricht, wenn es aus jeder Etage höher als   fällt. Du erhältst N k xth x   Schreiben Sie einen Algorithmus, der die minimale Anzahl von Probeabwürfen ermittelt, die im schlimmsten Fall erforderlich sind, um diese Etage zu identifizieren.      und   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   . Wenn beispielsweise N = 1 k = 5 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   nennen) weggeworfene Eier nicht zerbrechen, wenn sie zu Boden fallen. targetFloor  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   zu finden. targetFloor  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   . 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   sein wird. targetFloor targetFloor  Wir werden dieses Problem noch einmal in Go schreiben: einfach genug, um lesbar zu sein, aber komplex genug, um die innere Mechanik zu verstehen.   https://gist.github.com/NicolaM94/85ae34f01e7de8cd00264276b385e137?embedable=true#file-main-go  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   mithilfe des in Go integrierten   Moduls. targetFlor math/rand  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:   https://gist.github.com/NicolaM94/dd49b3b44a8938c40d0539512fd613cb?embedable=true#file-main-go  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   ist die 7. Etage (das wissen wir natürlich nicht). Wir könnten die folgenden Vermutungen annehmen:  targetFloor  Grundsätzlich gehen wir davon aus, dass   das mittlere Stockwerk des Gebäudes ist. Wir werfen das Ei von dort aus und die möglichen Ergebnisse sind zwei: targetFloor  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   , die auf ein Problem aus der „realen Welt“ angewendet wird. Die binäre Suche ist ein einfacher und übersichtlicher   Algorithmus, was bedeutet, dass sich die Größe des Problems bei jedem Schritt halbiert, bis wir die Lösung finden. binäre Suche Divide-and-Conquer-  Dies bedeutet, dass dieser Algorithmus im Vergleich zum vorherigen viel schneller ist. Schauen wir uns den Code an!   https://gist.github.com/NicolaM94/79d625ecef07cb26a7a8d9bcdb6143fd?embedable=true#file-main-go  Werfen wir einen genaueren Blick. Die binäre Suchfunktion akzeptiert 4 Argumente:    , ein Array von Ganzzahlen, das das Gebäude ist, über das wir eine Schleife durchlaufen; overArray    , der untere Index des Gebäudes; bottom    , der Index der obersten Etage des Gebäudes; top    , die Variable mit   um zu überprüfen, ob wir sie im Gebäude finden können. breakFloor targetFloor  Danach durchlaufen wir eine Schleife über das Gebäude, wobei   tiefer als   liegt: Wenn sich bei der binären Suche die beiden Positionsargumente verschränken und vertauschen, bedeutet dies, dass das gesuchte Element nicht gefunden wurde. bottom top  Wenn der Algorithmus also in dieser Situation endet, endet die Schleife und wir geben   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. -1  Wir berechnen das   Element als Boden zwischen   und   und prüfen, ob   . Wenn ja, geben wir den   als Ergebnis zurück. middlePoint bottom top middlePoint == breakFloor middlePoint  Ist dies nicht der Fall, passen wir   oder   entsprechend an: Wenn   größer als   ist, bedeutet dies, dass wir uns zu hoch auf dem Gebäude befinden. Daher senken wir unsere Vorhersage, indem wir die   Etage auf   setzen. bottom top middlePoint breakFloor top middlePoint — 1  Wenn   kleiner als   ist, passen wir unseren   an, indem wir ihn auf   setzen. middlePoint breakFloor bottom middlePoint+1  Um nun alles zu überprüfen, generieren wir in der   die Umgebung wie zuvor und erstellen eine neue Variable namens   , die unser Ergebnis enthält. main bsFloor  Um zu bestätigen, dass unser Algorithmus zum richtigen Ergebnis geführt hat, drucken wir sowohl   als auch   aus, die zuvor zufällig generiert wurden. bsFloor targetFloor  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   ist. len(building)  Dies bedeutet, dass die zeitliche Komplexität dieses Algorithmus   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. O(log(n))  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  Seite!   Ko-Fi  Und wie immer vielen Dank fürs Lesen!   Nicola   Auch   veröffentlicht hier

Read My Stories

Dieses Audio ist in der Originalsprache der Geschichte produziert!

Zu lang; Lesen

Make resilience your competitive advantage

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

About Author

KOMMENTARE

Hängeetiketten

DIESER ARTIKEL WURDE VORGESTELLT IN

Related Stories

HackerNoon's DeFi Writing Contest with SORA Network: XSTUSD Use Cases

HackerNoon Decoded 2024: Wir feiern unsere Gaming-Community!

Genuine Content Creation in the Age of AI: Why Startups Need Quality Content

HackerNoon Decoded 2024: Celebrating Our Programming Community!

HackerNoon's DeFi Writing Contest with SORA Network: XSTUSD Use Cases

HackerNoon Decoded 2024: Wir feiern unsere Gaming-Community!

Genuine Content Creation in the Age of AI: Why Startups Need Quality Content

HackerNoon Decoded 2024: Celebrating Our Programming Community!

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps