Inhaltsverzeichnis[Ausblenden][Zeigen]
- 1. Wie definiert man ein Array?
- 2. Dynamische Arrays: Was sind sie? Was unterscheidet sie von Basic Arrays?
- 3. Wie unterscheiden sich ein Array und ein Dictionary voneinander?
- 4. Nennen Sie einige Vor- und Nachteile von Arrays.
- 5. Worauf bezieht sich „Sparse Array“?
- 6. Wann würden Sie eine verkettete Liste einem Array vorziehen?
- 7. Was unterscheidet ein indiziertes Array von einem assoziativen Array?
- 8. Welche Vorteile hat Heap gegenüber sortierten Arrays?
- 9. Können wir die Größe des Arrays als negativ definieren?
- 10. Wie finden Sie die fehlende Ganzzahl in einem Array mit 1 bis 100 Elementen?
- 11. Wie finden Sie den Index eines Elements in einem Array?
- 12. Wie kann man ein bestimmtes Element aus einem Array entfernen?
- 13. Wie kann die Gleichheit zweier Arrays überprüft werden?
- 14. Wenn wir über Arrays sprechen, was meinen Sie mit den Ausdrücken „Dimension“ und „Tiefstellung“?
- Codieren von Interviewfragen
- 15. Suchen Sie ein Paar in einem Array, das die angegebene Summe hat
- 16. Binäre Array-Sortierung mit linearer Zeit
- 17. Finden Sie das größte Zwei-Ganzzahl-Produkt in einem Array.
- 18. Wie man alle Nullen des Arrays an das Ende verschiebt
- 19. Wie man ein Array mit zwei Einträgen sortiert, die in einem Vorgang vertauscht werden.
- 20. Wie man zwei sortierte Arrays an Ort und Stelle kombiniert.
- 21. Wie kann ich eine Reihe von Artikeln in abwechselnd hohen und niedrigen Positionen neu anordnen?
- 22. Wie ersetzt man jedes Element eines Arrays ohne Verwendung eines Divisionsoperators durch das Produkt jedes Elements im Array?
- 23. Finde das ungeradeste Element in einem Array in logarithmischer Zeit
- 24. Wie erhält man das nachfolgende größere Element für jedes Element in einem kreisförmigen Array?
- 25. Den Inversionszähler eines Arrays finden?
- 26. Was ist das Regenwasserfangproblem?
- Zusammenfassung
Codierungsinterviews enthalten eine Reihe von DSA-Fragen. Sie sollten mit Arrays vertraut sein, wenn Sie sich auf Ihr bevorstehendes Tech-Interview mit FAANG oder einem anderen Tier-1-Tech-Unternehmen vorbereiten.
In den meisten Coding-Interviews belegt es den zweiten Platz nach Strings. Ein Array ist eine Gruppierung zusammengehöriger Datenelemente, die in unmittelbarer Nähe zueinander im Speicher gehalten werden.
Da sie mit allen Programmiersprachen wie C, C++, Java, Python, Perl und Ruby verbunden sind, sind sie überall. Lesen Sie weiter für einige Übungsherausforderungen und Interviewfragen und -antworten auf der Grundlage von Arrays.
Python wird in diesem Beitrag verwendet, um die Codierungsprobleme anzugehen, da es einfach zu verwenden und zu verstehen ist und den meisten von uns vertraut sein muss.
Lass uns anfangen.
1. Wie definiert man ein Array?
- Eine Gruppe verwandter Datentypen ist ein Array.
- Arrays sind immer fest.
- Die gleiche Art von Variablen wird von Array-Objekten an mehreren Stellen gespeichert.
- Sowohl primitive Typen als auch Objektreferenzen sind damit kompatibel.
2. Dynamische Arrays: Was sind sie? Was unterscheidet sie von Basic Arrays?
Die automatische Skalierung, die dynamische Arrays (in Java auch als Growable Arrays, Resizing Arrays, Changeable Arrays oder ArrayLists bezeichnet) bieten, ist ein wesentlicher Vorteil.
Sie müssen immer im Voraus wissen, wie viele Elemente Ihr Array speichern wird, da Arrays eine feste Größe haben. Andererseits wächst ein dynamisches Array, wenn Sie weitere Mitglieder hinzufügen, sodass Sie seine genaue Größe nicht vorher kennen müssen.
3. Wie unterscheiden sich ein Array und ein Dictionary voneinander?
Dies ist eine auf Grundlagen basierende Reihe von Interviewfragen, die regelmäßig gestellt werden. Im Folgenden sind die wichtigsten Unterschiede zwischen Arrays und Wörterbüchern aufgeführt:
- Ein Array ist eine geordnete Liste ähnlicher Elemente. Dictionary hingegen hat Schlüssel-Wert-Paare.
- Array-Größen können sich dynamisch ändern. Solche dynamischen Ideen gibt es in Wörterbüchern nicht.
- Vor der Verwendung eines Arrays muss seine Größe angegeben werden. Wörterbuchgrößen müssen nicht angepasst werden.
- Verwenden Sie die Redim-Anweisung, wenn Sie die Größe des Arrays erweitern möchten. In Wörterbüchern kann ein Element ohne Deklaration hinzugefügt werden.
4. Nennen Sie einige Vor- und Nachteile von Arrays.
Vorteile:
- Arrays können mehrere Elemente gleichzeitig sortieren.
- Andere Datenstrukturen, wie Stapel, Warteschlangen, verkettete Listen, Bäume, Graphen usw., können in einem Array implementiert werden.
- Ein Index kann verwendet werden, um ein Element eines Arrays zu erreichen.
Nachteile:
- Die Größe eines Arrays muss im Voraus deklariert werden. Im Moment der Array-Deklaration sind wir uns jedoch möglicherweise nicht der Größe bewusst, die wir benötigen.
- Die Struktur des Arrays ist statisch. Dies impliziert, dass die Arraygröße immer fest ist und dass die Speicherzuordnung nicht erhöht oder verringert werden kann.
5. Worauf bezieht sich „Sparse Array“?
Ein Sparse-Array ist ein Datenarray, das viele Einträge mit Nullwerten enthält. Im Gegensatz dazu enthält ein dichtes Array die Mehrheit seiner Elemente mit Werten ungleich Null. Die Indizes eines Sparse-Arrays, das Zahlen in Objekte umwandelt, können Lücken enthalten. Im Vergleich zu einer HashMap sind sie speichereffizienter.
6. Wann würden Sie eine verkettete Liste einem Array vorziehen?
Beachten Sie bei der Verwendung von verknüpften Listen anstelle von Arrays Folgendes:
- Sie benötigen keine Elemente, um wahlfreien Zugriff zu haben.
- Wo zeitliche Vorhersagbarkeit wesentlich ist, benötigen Sie konstante Einfügungen und Entfernungen aus der Liste.
- Um eine Prioritätswarteschlange zu erstellen, müssen Sie möglicherweise Elemente in der Mitte der Liste platzieren.
- Sie haben keine Ahnung, wie lang die Liste sein wird. Wenn die Array-Größe zunimmt, müssen Sie Speicher neu deklarieren und duplizieren, genau wie bei einfachen Arrays.
7. Was unterscheidet ein indiziertes Array von einem assoziativen Array?
Die Hauptunterschiede zwischen assoziativen und indizierten Arrays sind in der folgenden Tabelle aufgeführt.
- Ein Schlüssel-Wert-Paar im Text- oder Zahlenformat wird verwendet, um ein assoziatives Array zu sortieren. Die Schlüssel des indizierten Arrays sind alle numerisch, und jeder Schlüssel ist mit einem bestimmten Wert verbunden.
- In einem assoziativen Array kann der Schlüssel ein String sein. Indiziertes Array mit ganzzahligen Schlüsseln beginnend bei 0.
- Eine zweispaltige Tabelle ahmt das Verhalten eines assoziativen Arrays nach. Ähnlich wie eine einspaltige Tabelle sind indizierte Arrays.
- Karten sind ein assoziativer Array-Typ. Ein Index-Array ist keine Karte.
8. Welche Vorteile hat Heap gegenüber sortierten Arrays?
Die Zeiteffizienz bei der Verwendung von Heap über Sorted Arrays ist der Hauptvorteil. Während Heap-Operationen schneller sind, erfordert das Sortieren eines Arrays viel Zeit. Ein Heap kann das kleinste Element erheblich schneller entdecken, als ein Array sortiert werden kann.
Eine bestimmte Sammlung von Zahlen kann mithilfe von Sorted Arrays auf zwei Arten angeordnet werden. Andererseits kann es für eine gegebene Sammlung von Zahlen mehr als einen potentiellen Haufen geben.
9. Können wir die Größe des Arrays als negativ definieren?
Nein, wir können keine negative Ganzzahl als Größe eines Arrays definieren. Es wird keinen Kompilierungsfehler geben, wenn wir deklarieren. Zur Laufzeit werden wir jedoch auf eine NegativeArraySizeException stoßen.
10. Wie finden Sie die fehlende Ganzzahl in einem Array mit 1 bis 100 Elementen?
Die Summe der Reihen kann durch Anwendung der folgenden Funktion berechnet werden: n (n + 1) / 2
Nur wenn das Array keine Duplikate hat oder mehr als eine Ganzzahl fehlt, wird diese Funktion ausgeführt. Unabhängig davon, ob ein Array doppelte Elemente enthält, können Sie das Array sortieren, um festzustellen, ob es äquivalente Elemente gibt.
11. Wie finden Sie den Index eines Elements in einem Array?
Der Index eines Elements kann über eine lineare oder binäre Suche ermittelt werden. Bis es die Übereinstimmung des erforderlichen Elements findet, durchläuft eine lineare Suchfunktion jedes einzelne Element in einem Array. Es gibt den Index zurück, sobald es das übereinstimmende Element gefunden hat. Folglich ist die zeitliche Komplexität der linearen Suche O. (n). Sowohl ein sortiertes als auch ein unsortiertes Array können eine lineare Suche verwenden.
Mit einer binären Suche, die das Array kontinuierlich halbiert, bis der Median des Intervalls mit dem erforderlichen Element übereinstimmt und den Index liefert, können Sie den Index des Elements erhalten, wenn das Array sortiert ist. Folglich ist die zeitliche Komplexität der binären Suche O. (log n).
12. Wie kann man ein bestimmtes Element aus einem Array entfernen?
Da Sie Elemente aus dem ursprünglichen Array nicht einfach löschen können, da es sich um feste Mengen mit einer definierten Größe handelt, bittet der Interviewer Sie um einen anderen Ansatz und um das Problem, das die Frage aufwirft. Die beste Vorgehensweise besteht darin, ein neues Array zu erstellen, um ein Element zu löschen. Sie können die Elemente aus dem ersten Array in diesem Array duplizieren und nur das Element einfügen, das Sie löschen möchten.
Eine andere Strategie besteht darin, das Zielelement im Array zu finden und dann die Reihenfolge aller Elemente umzukehren, die sich rechts vom Zielelement befinden.
13. Wie kann die Gleichheit zweier Arrays überprüft werden?
Sie müssen zuerst die Längen der beiden bereitgestellten Arrays überprüfen. Die übereinstimmenden Elemente beider Arrays werden verglichen, wenn ihre Längen gleich sind. Die beiden Arrays werden als gleich angesehen. wenn jedes Komponentenpaar in jeder Korrespondenz gleich ist. Dieser Ansatz wird nicht empfohlen, um die Gleichheit zweier Arrays zu überprüfen, wenn die Arrays groß sind, da dies viel Zeit in Anspruch nehmen wird. Sie können auch die Methode equals() verwenden, die in der Klasse Arrays enthalten ist. Wenn der Interviewer Sie jedoch auffordert, zwei Arrays zu vergleichen, ohne integrierte Methoden zu verwenden, ist diese Methode hilfreich.
14. Wenn wir über Arrays sprechen, was meinen Sie mit den Ausdrücken „Dimension“ und „Tiefstellung“?
Die „Dimension“ eines Arrays ist die Anzahl der Indizes oder Indizes, die erforderlich sind, um jedes einzelne Mitglied zu identifizieren. Indizes und Abmessungen können unklar sein. Eine Dimension ist eine Beschreibung des Bereichs zulässiger Schlüssel, während ein Index eine Zahl ist. Für jede Array-Dimension ist nur ein Index erforderlich.
Beispielsweise hat das Array arr[10][5] zwei Dimensionen. Größen 10 auf der einen und 5 auf der anderen. Um seine Komponenten anzusprechen, benötigen Sie zwei Indizes. Beide liegen zwischen 0 und 4; eine zwischen 0 und 9, einschließlich.
Codieren von Interviewfragen
15. Suchen Sie ein Paar in einem Array, das die angegebene Summe hat
Zum Beispiel,
Eingang:
- Zahlen = [8, 7, 2, 5, 3, 1]
- Ziel = 10
Ausgang:
- Paar gefunden (8, 2)
- Or
- Paar gefunden (7, 3)
Eingang:
- Zahlen = [5, 2, 6, 8, 1, 9]
- Ziel = 12
Ausgang:
- Paar nicht gefunden
16. Binäre Array-Sortierung mit linearer Zeit
Sortieren Sie ein binäres Array in linearer Zeit und in einem festen Bereich. Die Ausgabe sollte zuerst alle Nullen und dann alle Einsen anzeigen.
Zum Beispiel,
- Eingabe: { 1, 0, 1, 0, 1, 0, 0, 1 }
- Ausgabe: { 0, 0, 0, 0, 1, 1, 1, 1 }
Ein einfacher Ansatz wäre, die Gesamtzahl der Nullen des Arrays zu berechnen, sagen wir k, und dann die ersten k Indizes im Array mit 0en und die verbleibenden Indizes mit 0 zu füllen. Als Alternative könnten wir berechnen, wie viele 1s insgesamt in sind Array k, füllen Sie die letzten k Indizes im Array mit 1 und lassen Sie die restlichen Indizes mit 1 gefüllt.
Der gegebene Ansatz hat eine Zeitkomplexität von O(n) und verwendet keinen zusätzlichen Speicher, wobei n die Größe der Eingabe ist.
17. Finden Sie das größte Zwei-Ganzzahl-Produkt in einem Array.
Finden Sie das größte Produkt zweier Zahlen in einem Integer-Array.
Denken Sie an das Array 10 3 5 6 2 als Beispiel. Das Paar (-10, -3) oder (5, 6) ist das höchste Produkt.
Über jede Elementkombination nachzudenken und ihr Produkt herauszufinden, ist ein dummer Ansatz. Wenn das Produkt des aktuellen Paars größer als das bisher erhaltene maximale Produkt ist, aktualisieren Sie das maximale Produkt. Drucken Sie die Komponenten des Endprodukts zuletzt.
Die obige Lösung, bei der n die Menge der Eingabe ist, hat eine zeitliche Komplexität von O(n2) und nimmt keinen weiteren Platz ein.
18. Wie man alle Nullen des Arrays an das Ende verschiebt
Verschieben Sie alle Nullen in einem Integer-Array an das Ende. Die Antwort sollte die Verwendung von konstantem Leerzeichen vermeiden und die relative Reihenfolge der Komponenten des Arrays beibehalten.
Eingabe: {1,2,3,0,8,0,4,7}
Die Ausgabe ist {1,2,3,8,4,7,0,0}
Setzen Sie das Element an die folgende verfügbare Position im Array, wenn das aktuelle Element nicht Null ist. Füllen Sie alle verbleibenden Indizes mit 0, sobald alle Elemente des Arrays verarbeitet wurden.
Die vorhergehende Lösung hat eine Zeitkomplexität von O(n), wobei n die Größe der Eingabe ist.
19. Wie man ein Array mit zwei Einträgen sortiert, die in einem Vorgang vertauscht werden.
Sortieren Sie ein Array in der linearen Zeit, wenn zwei vertauschte Elemente und ein Array mit allen seinen Elementen in aufsteigender Reihenfolge angeordnet sind. Stellen Sie sich vor, dass das Array keine Duplikate enthält.
Eingabe:= [1,9,3,4,7,2] oder [9,3,7,2,1,4] oder [2,4,1,7,3,9]
Ausgabe: = [1,2,3,4,7,9]
Beginnend mit dem zweiten Element im Array besteht das Ziel darin, jedes Element mit seinem Vorgänger zu vergleichen. Die Streitposition wird gespeichert, indem zwei Zeiger x und y genommen werden.
Aktualisieren Sie x auf den Index des vorherigen Elements und y auf den Index des aktuellen Elements, wenn ersteres größer als letzteres ist. Aktualisieren Sie y auf den Index des aktuellen Elements, wenn sich herausstellt, dass das vorherige Element größer als das aktuelle Element ist.
Schalten Sie schließlich die Elemente an den Indizes x und y um, sobald wir die Verarbeitung jedes benachbarten Paars von Elementen beendet haben.
Aufgrund der Tatsache, dass das oben erwähnte Verfahren nur einen einzigen Scan des Eingangsarrays der Größe n durchführt, ist seine Zeitkomplexität O(n). Für die Lösung wird kein zusätzlicher Raum benötigt.
20. Wie man zwei sortierte Arrays an Ort und Stelle kombiniert.
Führen Sie die Elemente der Arrays X[] und Y[] zusammen – zwei sortierte Arrays der Größe m und n –, indem Sie die sortierte Reihenfolge beibehalten, d. h. indem Sie X[] mit den ersten m kleinsten Elementen und Y[] mit den füllen verbleibende Elemente.
Wenn sich ein Element im Array X[] bereits an der richtigen Position befindet (dh dasjenige, das das kleinste unter den verbleibenden Elementen ist), ignorieren Sie es; Ersetzen Sie es andernfalls durch das kleinste Element, das zufällig auch das erste Element von Y[] ist. Um die sortierte Reihenfolge nach dem Austauschen beizubehalten, übertragen Sie das Element (jetzt bei Y[0]) an die richtige Stelle in Y[].
Die Größe des ersten Arrays ist m und die Größe des zweiten Arrays ist n, und die Zeitkomplexität ist O(mn).
21. Wie kann ich eine Reihe von Artikeln in abwechselnd hohen und niedrigen Positionen neu anordnen?
Ordnen Sie ein Integer-Array neu an, sodass jedes nachfolgende Element größer als die vorhergehenden und folgenden Elemente ist. Angenommen, das Array enthält keine doppelten Elemente.
Das Sortieren des Arrays oder das Verwenden von zusätzlichem Platz ist für einen effektiven Ansatz nicht erforderlich. Der Plan ist, zunächst das zweite Mitglied des Arrays zu nehmen und für jede Schleifeniteration um zwei nach oben zu gehen.
Vertausche die Komponenten, wenn das letzte Element das erste übersteigt. Wechseln Sie auf ähnliche Weise beide Elemente, wenn das folgende Element größer als das aktuelle Element ist. Am Ende der Schleife erhalten wir das gewünschte Array, das den angegebenen Einschränkungen entspricht.
22. Wie ersetzt man jedes Element eines Arrays ohne Verwendung eines Divisionsoperators durch das Produkt jedes Elements im Array?
Ersetzen Sie ohne Verwendung des Divisionsoperators jedes Element in einem Integer-Array durch das Produkt aller anderen Elemente.
In linearer Zeit und konstantem Raum können wir Rekursion verwenden, um dieses Problem anzugehen. Das rekursive Berechnen der Produkte jedes Elements im rechten Subarray und das Übergeben des linken Subarray-Produkts als Funktionsparameter ist die Idee.
Die Zeitkomplexität ist O(n).
23. Finde das ungeradeste Element in einem Array in logarithmischer Zeit
Bei einem Integer-Array, in dem alle bis auf ein Element eine gerade Anzahl von Vorkommen haben, besteht das Problem darin, zu bestimmen, wie oft dieses eine Element vorkommt. Finden Sie das ungerade vorkommende Element in logarithmischer Zeit und konstantem Raum, wenn die gleichen Elemente paarweise im Array vorkommen und es nie mehr als zwei Instanzen eines gegebenen Elements in einer Reihe geben kann.
Die XOR-Operation ermöglicht es uns, dieses Problem in linearer Zeit zu lösen. Das Ziel besteht darin, jedes Element im Array mit XOR zu verknüpfen. Nur die ungeradzahlig vorkommenden Elemente bleiben übrig, nachdem sich die gerade vorkommenden Elemente gegenseitig aufheben.
Dieses Problem kann sogar in O(log(n))-Zeit gelöst werden.
24. Wie erhält man das nachfolgende größere Element für jedes Element in einem kreisförmigen Array?
Das nächstgrößere Element für jedes Element in einem kreisförmigen Integer-Array sollte lokalisiert werden. Die erste größere Ganzzahl nach einem Element x im Array ist das nachfolgende größere Element dieses Elements.
Von rechts nach links können wir Array-Elemente bearbeiten. Das Ziel ist es, für jedes Element x eine Schleife zu durchlaufen, bis entweder der Stapel leer ist oder wir ein höheres Element darauf haben. Legen Sie fest, dass das nächstgrößere Element von x oben auf dem Stapel erscheint, wenn dies der Fall ist.
25. Den Inversionszähler eines Arrays finden?
Finden Sie die Gesamtzahl der Inversionen eines Arrays. Ein Paar I j) wird als Inversion eines Arrays A bezeichnet, wenn I j) und (A[i] > A[j]). Wir müssen jedes Paar davon im Array zählen.
Das Zählen aller Array-Mitglieder, die kleiner sind als es, und das Hinzufügen des Ergebnisses zur Ausgabe ist ein einfacher Ansatz.
Diese Lösung hat eine Komplexität von O(n2), wobei n die Größe der Eingabe ist.
26. Was ist das Regenwasserfangproblem?
Das Finden des meisten Wassers, das in einem bestimmten Satz von Balken mit einer Breite von jeweils einer Einheit eingeschlossen werden kann, wird als Problem des „Einfangens von Niederschlag“ bezeichnet.
Ziel ist es, den höchsten Balken zu bestimmen, der links und rechts von jedem Balken platziert werden darf. Das Minimum der führenden Balken links und rechts, abzüglich der Höhe des aktuellen Balkens, ist die Wassermenge, die über jedem Balken gespeichert wird.
Zusammenfassung
Im Vergleich zu anderen Datenstrukturthemen sind Arrays einfacher. Um Array-Interviewfragen zu beantworten, müssen Sie ein grundlegendes Verständnis von Arrays haben.
Sie sollten die Grundlagen von Arrays, einschließlich Array-Operationen (vom Deklarieren/Erstellen eines Arrays bis zum Zugreifen auf/Ändern von Array-Elementen), sowie Programmierkonzepte wie Schleifen, Rekursion und grundlegende Operatoren ausführlich wiederholen, um Interviewfragen zu Arrays erfolgreich zu beantworten. Erkennen Sie das Problem vollständig.
Bei Fragen sollten Sie um Klärung bitten. Denken Sie darüber nach, das Problem in überschaubarere Teile zu unterteilen. Stellen Sie sicher, dass Sie den Algorithmus im Hinterkopf haben, bevor Sie mit dem Programmieren beginnen; Schreiben Sie es auf oder visualisieren Sie es in einem Flussdiagramm. Beginnen Sie dann mit dem Schreiben von Code.
Hinterlassen Sie uns einen Kommentar