Lösen einer Aufgabe aus einem Google-Interview mit JavaScript: 4 verschiedene Möglichkeiten

Als ich die Leistung von Algorithmen studierte, stieß ich auf dieses Video aus dem Scheininterview von Google . Es gibt nicht nur eine Vorstellung davon, wie Interviews in großen Technologieunternehmen durchgeführt werden, sondern ermöglicht Ihnen auch zu verstehen, wie algorithmische Probleme am effizientesten gelöst werden.

Dieser Artikel ist eine Art Begleitung zum Video. Darin gebe ich Kommentare zu allen gezeigten Lösungen sowie zu meiner eigenen Version der Lösung in JavaScript. Die Nuancen jedes Algorithmus werden ebenfalls diskutiert.

Wir erinnern Sie daran: Für alle Leser von „Habr“ - ein Rabatt von 10.000 Rubel bei der Anmeldung für einen Skillbox-Kurs mit dem Promo-Code „Habr“.

Skillbox empfiehlt: Praktikum "Mobile Developer PRO" .

Erklärung des Problems

Wir erhalten ein geordnetes Array und einen bestimmten Wert. Dann bitten sie darum, eine Funktion zu erstellen, die true oder false zurückgibt, je nachdem, ob die Summe von zwei beliebigen Zahlen aus dem Array dem angegebenen Wert entsprechen kann.

Mit anderen Worten, gibt es zwei Ganzzahlen x und y im Array, die beim Hinzufügen dem angegebenen Wert entsprechen?

Beispiel A.

Wenn wir ein Array [1, 2, 4, 9] und einen Wert von 8 erhalten haben, gibt die Funktion false zurück, da keine zwei Zahlen aus dem Array insgesamt 8 ergeben können.

Beispiel B.

Wenn es sich jedoch um ein Array [1, 2, 4, 4] handelt und der Wert 8 ist, sollte die Funktion true zurückgeben, da 4 + 4 = 8 ist.

Lösung 1. Bruteforce

Zeitliche Schwierigkeit: O (N²).
Räumliche Komplexität: O (1).

Die naheliegendste Bedeutung ist die Verwendung eines Paares verschachtelter Schleifen.

const findSum = (arr, val) => { for (let i = 0; i < arr.length; i++) { for (let j = 0; j < arr.length; j++) { if (i !== j && arr[i] + arr[j] === val) { return true; }; }; }; return false; }; 

Diese Lösung kann nicht als effektiv bezeichnet werden, da sie jede mögliche Summe von zwei Elementen im Array überprüft und jedes Indexpaar zweimal vergleicht. (Wenn zum Beispiel i = 1 und j = 2 ist, entspricht dies tatsächlich dem Vergleich mit i = 2 und j = 1, aber in dieser Lösung versuchen wir beide Optionen).

Da unsere Lösung ein Paar verschachtelter for-Schleifen verwendet, ist sie quadratisch mit einer Zeitkomplexität von O (N²).


Lösung 2. Binäre (binäre) Suche

Zeitliche Schwierigkeit: O (Nlog (N)).
Räumliche Komplexität: O (1) .

Da Arrays geordnet sind, können wir mithilfe der binären Suche nach einer Lösung suchen. Dies ist der effizienteste Algorithmus für geordnete Arrays. Die binäre Suche selbst hat eine O (log (N)) Laufzeit. Sie müssen jedoch weiterhin eine for-Schleife verwenden, um jedes Element mit allen anderen Werten zu vergleichen.

So könnte die Lösung aussehen. Um alles klar zu machen, verwenden wir eine separate Funktion, um die binäre Suche zu steuern. Sowie die Funktion removeIndex (), die die Version des Arrays abzüglich des angegebenen Index zurückgibt.

 const findSum = (arr, val) => { for (let i = 0; i < arr.length; i++){ if (binarySearch(removeIndex(arr, i), val - arr[i])) { return true; } }; return false; }; const removeIndex = (arr, i) => { return arr.slice(0, i).concat(arr.slice(i + 1, arr.length)); }; const binarySearch = (arr, val) => { let start = 0; let end = arr.length - 1; let pivot = Math.floor(arr.length / 2); while (start < end) { if (val < arr[pivot]) { end = pivot - 1; } else if (val > arr[pivot]) { start = pivot + 1; }; pivot = Math.floor((start + end) / 2); if (arr[pivot] === val) { return true; } }; return false; }; 

Der Algorithmus beginnt bei Index [0]. Anschließend wird eine Version des Arrays mit Ausnahme des ersten Index erstellt und mithilfe einer binären Suche überprüft, ob der verbleibende Wert zum Array hinzugefügt werden kann, um die gewünschte Menge zu erhalten. Diese Aktion wird einmal für jedes Element im Array ausgeführt.

Die for-Schleife selbst hat eine lineare Zeitkomplexität von O (N), aber innerhalb der for-Schleife führen wir eine binäre Suche durch, die die Gesamtzeitkomplexität von O (Nlog (N)) angibt. Diese Lösung ist besser als die vorherige, aber es gibt noch etwas zu verbessern.


Lösung 3. Lineare Zeit

Zeitliche Schwierigkeit: O (N).
Räumliche Komplexität: O (1).

Jetzt werden wir das Problem lösen und uns daran erinnern, dass das Array sortiert ist. Die Lösung besteht darin, zwei Zahlen zu verwenden: eine am Anfang und eine am Ende. Wenn das Ergebnis vom gewünschten abweicht, ändern wir den Start- und Endpunkt.

Am Ende erfüllen wir entweder den gewünschten Wert und geben true zurück, oder die Start- und Endpunkte konvergieren und geben false zurück.

 const findSum = (arr, val) => { let start = 0; let end = arr.length - 1; while (start < end) { let sum = arr[start] + arr[end]; if (sum > val) { end -= 1; } else if (sum < val) { start += 1; } else { return true; }; }; return false; }; 

Jetzt ist alles in Ordnung, die Lösung scheint optimal zu sein. Aber wer garantiert, dass das Array bestellt wurde?

Was dann?

Auf den ersten Blick könnten wir zuerst das Array sortieren und dann die obige Lösung verwenden. Aber wie wirkt sich das auf die Laufzeit aus?

Der beste Algorithmus ist die schnelle Sortierung mit der Zeitkomplexität O (Nlog (N)). Wenn wir es in unserer optimalen Lösung verwenden, ändert es seine Leistung von O (N) in O (Nlog (N)). Ist es möglich, eine lineare Lösung mit einem ungeordneten Array zu finden?

Entscheidung 4

Zeitliche Schwierigkeit: O (N).
Räumliche Komplexität: O (N).

Ja, es gibt eine lineare Lösung. Dazu müssen Sie ein neues Array erstellen, das eine Liste der Übereinstimmungen enthält, nach denen wir suchen. Der Kompromiss hierbei ist eine aktivere Nutzung des Speichers: Dies ist die einzige Lösung in dem Artikel mit einer räumlichen Komplexität von mehr als O (1).

Wenn der erste Wert dieses Arrays 1 und der Suchwert 8 ist, können wir den Wert 7 zum Array der "Suchwerte" hinzufügen.

Wenn wir dann jedes Element des Arrays verarbeiten, können wir das Array der „Suchwerte“ überprüfen und feststellen, ob einer von ihnen unserem Wert entspricht. Wenn ja, geben Sie true zurück.

 const findSum = (arr, val) => { let searchValues = [val - arr[0]]; for (let i = 1; i < arr.length; i++) { let searchVal = val - arr[i]; if (searchValues.includes(arr[i])) { return true; } else { searchValues.push(searchVal); } }; return false; }; 

Die Basis der Lösung ist die for-Schleife, die, wie wir oben gesehen haben, eine lineare Zeitkomplexität O (N) aufweist.

Der zweite Iterationsteil unserer Funktion ist Array.prototype.include (), eine JavaScript-Methode, die je nachdem, ob das Array den angegebenen Wert enthält, true oder false zurückgibt.

Um die zeitliche Komplexität von Array.prototype.includes () herauszufinden, können wir uns die von MDN bereitgestellte (und in JavaScript geschriebene) Polyfüllung ansehen oder eine Methode im Quellcode einer JavaScript-Engine wie Google V8 (C ++) verwenden.

 // https://tc39.imtqy.com/ecma262/#sec-array.prototype.includes if (!Array.prototype.includes) { Object.defineProperty(Array.prototype, 'includes', { value: function(valueToFind, fromIndex) { if (this == null) { throw new TypeError('"this" is null or not defined'); } // 1. Let O be ? ToObject(this value). var o = Object(this); // 2. Let len be ? ToLength(? Get(O, "length")). var len = o.length >>> 0; // 3. If len is 0, return false. if (len === 0) { return false; } // 4. Let n be ? ToInteger(fromIndex). // (If fromIndex is undefined, this step produces the value 0.) var n = fromIndex | 0; // 5. If n ≥ 0, then // a. Let k be n. // 6. Else n < 0, // a. Let k be len + n. // b. If k < 0, let k be 0. var k = Math.max(n >= 0 ? n : len - Math.abs(n), 0); function sameValueZero(x, y) { return x === y || (typeof x === 'number' && typeof y === 'number' && isNaN(x) && isNaN(y)); } // 7. Repeat, while k < len while (k < len) { // a. Let elementK be the result of ? Get(O, ! ToString(k)). // b. If SameValueZero(valueToFind, elementK) is true, return true. if (sameValueZero(o[k], valueToFind)) { return true; } // c. Increase k by 1. k++; } // 8. Return false return false; } }); } 

Hier ist der iterative Teil von Array.prototype.include () die while-Schleife in Schritt 7, die (fast) die gesamte Länge des angegebenen Arrays durchläuft. Dies bedeutet, dass seine zeitliche Komplexität ebenfalls linear ist. Nun, da es immer einen Schritt hinter unserem Hauptarray liegt, ist die zeitliche Komplexität O (N + (N - 1)). Mit der Big O-Notation vereinfachen wir sie auf O (N) - da N mit zunehmender Eingabegröße den größten Einfluss hat.

Für die räumliche Komplexität wird ein zusätzliches Array benötigt, dessen Länge das ursprüngliche Array widerspiegelt (minus eins, ja, aber dies kann ignoriert werden), was zur räumlichen Komplexität von O (N) führt. Eine erhöhte Speichernutzung sorgt für maximale Effizienz des Algorithmus.


Ich hoffe, dieser Artikel ist für Sie als Anhang zu einem Videointerview hilfreich. Es zeigt, dass ein einfaches Problem auf verschiedene Weise mit unterschiedlichen Ressourcen (Zeit, Speicher) gelöst werden kann.

Skillbox empfiehlt:

• Angewandter Python Data Analyst Online-Kurs.
  
• Online-Kurs "Beruf Frontend-Entwickler . "
• Praktischer Jahreskurs "PHP-Entwickler von 0 bis PRO" .