🥇Wir lösen eine Interviewaufgabe von Google in JavaScript: 4 verschiedene Ansätze

Als ich mich mit der Leistungsfähigkeit von Algorithmen beschäftigte, stieß ich auf dieses Video mit einem Mock-Interview von Google. Es vermittelt nicht nur einen Eindruck davon, wie Interviews in großen Technologiekonzernen ablaufen, sondern hilft auch zu verstehen, wie algorithmische Probleme effizient gelöst werden können.

Dieser Artikel ist eine Art Begleittext zu dem Video. Darin gebe ich Kommentare zu allen gezeigten Lösungen sowie meine eigene Version der Lösung in JavaScript. Außerdem werden die Feinheiten jedes Algorithmus diskutiert.

Wir erinnern daran: alle Leser von „Habr“ erhalten einen Rabatt von 10.000 Rubel bei der Anmeldung zu einem beliebigen Kurs von Skillbox mit dem Aktionscode „Habr“.

Skillbox empfiehlt: Praktischer Kurs „Mobiler Entwickler PRO“.

Aufgabenstellung

Wir erhalten ein sortiertes Array und einen bestimmten Wert. Dann werden wir gebeten, eine Funktion zu erstellen, die true oder false zurückgibt, abhängig davon, ob die Summe zweier beliebiger Zahlen aus dem Array dem angegebenen Wert entsprechen kann.

Mit anderen Worten: Gibt es im Array zwei ganze Zahlen x und y, deren Summe dem angegebenen Wert entspricht?

Beispiel A

Wenn uns das Array [1, 2, 4, 9] und der Wert 8 gegeben werden, gibt die Funktion false zurück, da keine zwei Zahlen aus dem Array eine Summe von 8 ergeben können.

Beispiel B

Aber wenn es sich um das Array [1, 2, 4, 4] und den Wert 8 handelt, sollte die Funktion true zurückgeben, da 4 + 4 = 8.

Lösung 1. Brute Force

Zeitkomplexität: O(N²).
Raumkomplexität: O(1).

Der offensichtlichste Ansatz ist die Verwendung von zwei verschachtelten 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 effizient betrachtet werden, da sie jede mögliche Summe zweier Elemente im Array überprüft und außerdem jedes Indexpaar zweimal vergleicht. (Zum Beispiel, wenn i = 1 und j = 2, ist das tatsächlich dasselbe wie i = 2 und j = 1, aber diese Lösung probiert beide Varianten aus).

Da unsere Lösung ein Paar von verschachtelten for-Schleifen verwendet, ist sie quadratisch und hat eine Zeitkomplexität von O (N²).

Lösung 2. Binäre Suche

Zeitkomplexität: O(Nlog(N)).
Raumkomplexität: O(1)..

Da die Arrays sortiert sind, können wir nach einer Lösung mit binärer Suche suchen. Dies ist der effizienteste Algorithmus für sortierte Arrays. An sich hat die binäre Suche eine Laufzeit von O(log(N)). Es ist jedoch dennoch erforderlich, eine for-Schleife zu verwenden, um jedes Element mit allen anderen Werten zu überprüfen.

So könnte eine Lösung aussehen. Um alles klar zu machen, verwenden wir eine separate Funktion zur Kontrolle der binären Suche. Außerdem die Funktion removeIndex (), die eine Version des Arrays ohne den angegebenen Index zurückgibt.

const findSum = (arr, val) => {
  for (let i = 0; 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]) {
      start = pivot + 1;
    };
    pivot = Math.floor((start + end) / 2);
    if (arr[pivot] === val) {
      return true;
    }
  };
  return false;
};

Der Algorithmus beginnt mit dem Index [0]. Dann erstellt er eine Version des Arrays, die den ersten Index ausschließt, und verwendet die binäre Suche, um zu überprüfen, ob eines der verbleibenden Werte zu dem Array hinzugefügt werden kann, um die gewünschte Summe zu erreichen. Diese Aktion wird einmal für jedes Element im Array ausgeführt.

An sich hat die for-Schleife eine lineare Zeitkomplexität von O (N), aber innerhalb der for-Schleife führen wir eine binäre Suche durch, was zu einer Gesamtzeitkomplexität von O (Nlog (N)) führt. Diese Lösung ist besser als die vorherige, aber es gibt noch Raum für Verbesserungen.

Lösung 3. Lineare Zeit

Zeitkomplexität: O(N).
Raumkomplexität: O(1).

Jetzt werden wir das Problem lösen, während wir uns daran erinnern, dass das Array sortiert ist. Die Lösung besteht darin, zwei Zahlen zu nehmen: eine am Anfang und eine am Ende. Wenn das Ergebnis anders als gewünscht ist, ändern wir den Anfangs- und Endpunkt.

Letztendlich werden wir entweder den gewünschten Wert treffen und true zurückgeben, oder die Anfangs- und Endpunkte werden sich treffen und false zurückgegeben.

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

Jetzt ist alles gut, die Lösung scheint optimal zu sein. Aber wer garantiert, dass das Array sortiert war?

Was dann?

Auf den ersten Blick könnten wir das Array zunächst einfach sortieren und dann die obige Lösung verwenden. Aber wie wirkt sich das auf die Ausführungszeit aus?

Der beste Algorithmus ist die schnelle Sortierung mit einer Zeitkomplexität von O (Nlog (N)). Wenn wir ihn in unserer optimalen Lösung verwenden, verändert sich die Leistung von O (N) auf O (Nlog (N)). Kann man eine lineare Lösung mit einem unsortierten Array finden?

Lösung 4

Zeitkomplexität: O(N).
Platzkomplexität: O(N).

Ja, es gibt eine lineare Lösung, dafür muss ein neues Array erstellt werden, das die Liste der Übereinstimmungen enthält, nach denen wir suchen. Der Kompromiss hier ist eine aktivere Nutzung des Speichers: dies ist die einzige Lösung im Artikel mit einer Speicherkomplexität, die O (1) übersteigt.

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

Dann können wir, indem wir jedes Element des Arrays bearbeiten, das Array "Suchwerte" überprüfen und sehen, ob eines davon unserem Wert entspricht. Wenn ja, geben wir 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 Grundlage der Lösung ist eine for-Schleife, die, wie wir oben gesehen haben, eine lineare zeitliche Komplexität von O (N) hat.

Der zweite iterierende Teil unserer Funktion ist Array.prototype.include (), eine JavaScript-Methode, die true oder false zurückgibt, abhängig davon, ob das Array den angegebenen Wert enthält.

Um die zeitliche Komplexität von Array.prototype.includes () zu ermitteln, können wir den Polyfill betrachten, der von MDN bereitgestellt wird (und in JavaScript geschrieben ist), oder wir können die Methode im Quellcode der JavaScript-Engine wie Google V8 (C++) verwenden.

// https://tc39.github.io/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 () eine while-Schleife in Schritt 7, die (fast) die gesamte Länge des gegebenen Arrays durchläuft. Das bedeutet, dass seine zeitliche Komplexität ebenfalls linear ist. Da sie immer einen Schritt hinter unserem Hauptarray liegt, ist die zeitliche Komplexität O (N + (N - 1)). Durch die Verwendung der Big O Notation vereinfacht sich dies auf O (N) — denn N hat den größten Einfluss bei wachsender Eingangsgröße.

Was die Speicherkomplexität betrifft, so ist ein zusätzliches Array erforderlich, dessen Länge dem ursprünglichen Array entspricht (minus eins, ja, aber das kann ignoriert werden), was zu einer Speicherkomplexität von O (N) führt. Der erhöhte Speicherverbrauch sorgt jedoch für maximale Effizienz des Algorithmus.

Ich hoffe, dieser Artikel erweist sich als nützlich für Sie als Ergänzung zum Video-Interview. Er zeigt, dass eine einfache Aufgabe auf verschiedene Arten mit unterschiedlichen Mengen an genutzten Ressourcen (Zeit, Speicher) gelöst werden kann.

Skillbox empfiehlt:

Angewandter Online-Kurs „Python-Datenanalyst“.

Online-Kurs „Beruf Frontend-Entwickler“.

Praktischer Jahreskurs „PHP-Entwickler von 0 bis PRO“.

Quelle: habr.com

Wir lösen eine Google-Interviewaufgabe in JavaScript: 4 verschiedene Ansätze

Aufgabenstellung

Was dann?