Das Amazon-Interview knacken

Blog

Bild für Beitrag



Bild mit freundlicher Genehmigung des Autors

Einen Job bei Amazon zu bekommen, ist für viele Entwickler auf der ganzen Welt ein Traum. Amazon ist mit über einer halben Million Mitarbeitern eines der größten Unternehmen der Welt. Amazon stellt mit einem einzigartigen Einstellungsprozess schnell ein, der die Unternehmenskultur und die Führungsprinzipien betont. Heute werde ich alles durchgehen, was Sie brauchen, um ein Amazon-Interview zu knacken, einschließlich Codierungsfragen und einer Schritt-für-Schritt-Anleitung zur Vorbereitung.



jquery Mauerwerk Bildergalerie

Heute werden wir folgendes besprechen:

  • 45 häufige Fragen im Amazon-Coding-Interview
  • Übersicht über Amazon-Codierungsinterviews
  • So bereiten Sie sich auf ein Coding-Interview vor
  • Einpacken

Bild für Beitrag



Bild mit freundlicher Genehmigung des Autors


1. Finden Sie die fehlende Zahl im Array

Sie erhalten ein Array positiver Zahlen aus |_+_| bis |_+_|, sodass alle Zahlen von |_+_| nach |_+_| vorhanden sind bis auf eine Zahl |_+_|. Du musst |_+_| finden. Das Eingabearray ist nicht sortiert. Sehen Sie sich das folgende Array an und sehen Sie sich die Lösung in Python an. Klicken Hier um die Lösung in C++, Java, JavaScript und Ruby anzuzeigen.

Bild für Beitrag

1

Laufzeitkomplexität: Linear, O(n)

Speicherkomplexität: Konstante, O (1)

Eine naive Lösung besteht darin, einfach nach jeder ganzen Zahl zwischen |_+_| . zu suchen und |_+_| im Eingabearray und stoppt die Suche, sobald eine Zahl fehlt. Aber wir können es besser machen. Hier ist eine lineare O(n)-Lösung, die die Summenformel der arithmetischen Reihe verwendet. Hier sind die Schritte, um die fehlende Zahl zu finden:

  • Finde die Summe |_+_| aller Zahlen im Array. Dies würde eine lineare Abtastung O(n) erfordern.
  • Dann finde die Summe |_+_| des ersten |_+_| Zahlen mit der arithmetischen Reihensummenformel
  • Der Unterschied zwischen diesen, d. h. |_+_|, ist die fehlende Zahl im Array.

2. Bestimmen Sie, ob die Summe zweier ganzer Zahlen gleich dem angegebenen Wert ist

Bestimmen Sie bei einem gegebenen Array von ganzen Zahlen und einem Wert, ob es zwei beliebige ganze Zahlen im Array gibt, deren Summe gleich dem angegebenen Wert ist. Zurück |_+_| wenn die Summe existiert und zurück |_+_| wenn es nicht. Betrachten Sie dieses Array und die Zielsummen. Klicken Hier um die Lösung in C++, Java, JavaScript und Ruby anzuzeigen.

Bild für Beitrag

n

Laufzeitkomplexität: Linear, O(n)

Speicherkomplexität: Linear, O(n)

Sie können den folgenden Algorithmus verwenden, um ein Paar zu finden, das sich zum Ziel addiert (z. B. |_+_|).

  • Scannen Sie das gesamte Array einmal und speichern Sie besuchte Elemente in einem Hash-Set.
  • Während |_+_|, für jedes Element |_+_| im Array prüfen wir, ob |_+_| ist im Hash-Set vorhanden, d. h. |_+_| ist bereits besucht.
  • Wenn |_+_| im Hash-Set gefunden wird, bedeutet dies, dass es ein Paar (|_+_|, |_+_|) im Array gibt, dessen Summe gleich dem angegebenen |_+_| ist.
  • Wenn wir alle Elemente im Array erschöpft haben und kein solches Paar gefunden haben, gibt die Funktion |_+_| zurück.

3. Zwei sortierte verknüpfte Listen zusammenführen

Bei zwei sortierten verknüpften Listen führen Sie diese zusammen, damit die resultierende verknüpfte Liste ebenfalls sortiert wird. Betrachten Sie als Beispiel zwei sortierte verknüpfte Listen und die darunter liegende zusammengeführte Liste. Klicken Hier um die Lösung in C++, Java, JavaScript und Ruby anzuzeigen.

Bild für Beitrag

1

Laufzeitkomplexität: Linear, O(m+n) wobei m und n Längen beider verknüpften Listen sind

Speicherkomplexität: Konstante, O (1)

Behalten Sie einen Kopf- und einen Endzeiger in der zusammengeführten verknüpften Liste bei. Wählen Sie dann den Kopf der zusammengeführten verknüpften Liste aus, indem Sie den ersten Knoten der beiden verknüpften Listen vergleichen. Für alle nachfolgenden Knoten in beiden Listen wählen Sie den kleineren aktuellen Knoten, verknüpfen ihn mit dem Ende der zusammengeführten Liste und bewegen den aktuellen Zeiger dieser Liste einen Schritt nach vorne.

Fahren Sie damit fort, während in beiden Listen noch einige Elemente vorhanden sind. Wenn in nur einer der Listen noch einige Elemente vorhanden sind, verknüpfen Sie diese verbleibende Liste mit dem Ende der zusammengeführten Liste. Anfänglich ist die zusammengeführte verknüpfte Liste |_+_|.

Vergleichen Sie den Wert der ersten beiden Knoten und machen Sie den Knoten mit dem kleineren Wert zum Kopfknoten der zusammengeführten verknüpften Liste. In diesem Beispiel ist es |_+_| von |_+_|. Da es sich um den ersten und einzigen Knoten in der zusammengeführten Liste handelt, wird er auch der Schwanz sein. Dann bewege |_+_| Einen Schritt nach vorne.

4. Verknüpfte Liste mit beliebigem Zeiger kopieren

Sie erhalten eine verknüpfte Liste, in der der Knoten zwei Zeiger hat. Die erste ist die reguläre |_+_| Zeiger. Der zweite Zeiger heißt |_+_| und kann auf jeden Knoten in der verknüpften Liste zeigen. Ihre Aufgabe ist es, Code zu schreiben, um eine tiefe Kopie der angegebenen verknüpften Liste zu erstellen. Hier, tiefe Kopie bedeutet, dass alle Operationen an der ursprünglichen Liste die kopierte Liste nicht beeinflussen sollten. Klicken Hier um die Lösung in C++, Java, JavaScript und Ruby anzuzeigen.

n

Laufzeitkomplexität: Linear, O(n)

Speicherkomplexität: Linear, O(n)

Dieser Ansatz verwendet eine Karte, um beliebige Knoten zu verfolgen, auf die die ursprüngliche Liste zeigt. Sie erstellen in zwei Durchgängen eine tiefe Kopie der ursprünglichen verknüpften Liste (z. B. |_+_|).

  • Erstellen Sie im ersten Durchgang eine Kopie der ursprünglichen verknüpften Liste. Verwenden Sie beim Erstellen dieser Kopie dieselben Werte für Daten und |_+_| in der neuen Liste. Aktualisieren Sie die Zuordnung auch weiterhin mit Einträgen, bei denen der Schlüssel die Adresse des alten Knotens und der Wert die Adresse des neuen Knotens ist.
  • Nachdem die Kopie erstellt wurde, führen Sie einen weiteren Durchlauf der kopierten verknüpften Liste durch und aktualisieren Sie beliebige Zeiger auf die neue Adresse unter Verwendung der im ersten Durchlauf erstellten Karte.

5. Level-Order-Traversierung des Binärbaums

Zeigen Sie bei gegebener Wurzel eines Binärbaums die Knotenwerte auf jeder Ebene an. Knotenwerte für alle Ebenen sollten in separaten Zeilen angezeigt werden. Werfen wir einen Blick auf den folgenden Binärbaum. Klicken Hier um die Lösung in C++, Java, JavaScript und Ruby anzuzeigen.

Bild für Beitrag

x

Laufzeitkomplexität: Linear, O(n)

Speicherkomplexität: Linear, O(n)

Hier verwenden Sie zwei Warteschlangen: |_+_| und |_+_|. Sie pushen die Knoten in beiden Warteschlangen abwechselnd basierend auf der aktuellen Ebenennummer.

Sie entfernen Knoten aus der Warteschlange |_+_|, drucken die Daten des Knotens und stellen die Kinder des Knotens in die Warteschlange |_+_|. Sobald die |_+_| leer wird, haben Sie alle Knoten für das aktuelle |_+_| bearbeitet. Um das |_+_| anzuzeigen, drucken Sie einen Zeilenumbruch (|_+_|), tauschen Sie die beiden Warteschlangen aus und fahren Sie mit der oben genannten Logik fort.

Nachdem Sie die Blattknoten aus dem |_+_| gedruckt haben, tauschen Sie |_+_| und |_+_|. Seit dem |_+_| leer wäre, können Sie die Schleife beenden.

#programmierung #interview #amazon #job-interview #coding-interviews

medium.com

Das Amazon-Interview knacken

Ein Blick auf die Top-Fragen im Coding-Interview bei Amazon