Wir lösen eine Aufgabe aus einem Google-Interview in JavaScript: 4 verschiedene Ansätze

Als ich mich mit der Leistungsbewertung von Algorithmen beschäftigte, stieß ich auf dieses Video mit einem Mock-Interview von Google. Es bietet nicht nur einen Einblick in die Interviews großer Technologiekonzerne, sondern zeigt auch, wie algorithmische Probleme auf möglichst effiziente Weise gelöst werden.

Dieser Artikel ist eine Art Begleitmaterial zum Video. Ich gebe Kommentare zu allen gezeigten Lösungen ab und präsentiere auch meine eigene Version der Lösung in JavaScript. Außerdem werden die Besonderheiten 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 „Mobile Entwickler PRO“.

Problemstellung

Uns wird ein sortiertes Array und ein bestimmter Wert gegeben. Dann sollen wir eine Funktion erstellen, die true oder false zurückgibt, je nachdem, ob die Summe von zwei Zahlen aus dem Array dem vorgegebenen Wert entspricht.

Anders ausgedrückt: Gibt es zwei ganze Zahlen x und y im Array, deren Summe dem angegebenen Wert entspricht?

Beispiel A

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

Beispiel B

Wenn es jedoch das Array [1, 2, 4, 4] und den Wert 8 gibt, sollte die Funktion true zurückgeben, weil 4 + 4 = 8.

Lösung 1. Brute Force

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

Die offensichtlichste Bedeutung ist die Verwendung eines Paares von 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 bezeichnet werden, da sie jede mögliche Summe von zwei Elementen im Array überprüft und jedes Indexpaar zweimal vergleicht. (Zum Beispiel, wenn i = 1 und j = 2 — das ist tatsächlich dasselbe wie der Vergleich von i = 2 und j = 1, aber diese Lösung versucht beide Varianten).

Da unsere Lösung ein Paar verschachtelter Schleifen verwendet, ist sie quadratisch mit einer zeitlichen Komplexitä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)). Dennoch muss ein for-Loop verwendet werden, um jedes Element mit allen anderen Werten zu überprüfen.

So könnte die Lösung aussehen. Um alles klar zu machen, verwenden wir eine separate Funktion zur Steuerung der binären Suche. Außerdem gibt es 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, in der der erste Index ausgeschlossen ist, und verwendet die binäre Suche, um zu überprüfen, ob eines der verbleibenden Werte dem Array hinzugefügt werden kann, um die gewünschte Summe zu erreichen. Diese Aktion wird einmal für jedes Element im Array durchgeführt.

Der for-Zyklus hat eine lineare zeitliche Komplexität von O(N), aber innerhalb des for-Zyklus führen wir eine binäre Suche durch, was zu einer Gesamtzeitkomplexität von O(N log(N)) führt. Diese Lösung ist besser als die vorherige, aber es gibt noch Verbesserungsmöglichkeiten.

Lösung 3. Lineare Zeit

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

Jetzt werden wir das Problem lösen, wobei wir daran denken, dass das Array sortiert ist. Die Lösung besteht darin, zwei Zahlen zu nehmen: eine am Anfang und eine am Ende. Wenn das Ergebnis von dem Geforderten abweicht, ändern wir den Anfangs- und Endpunkt.

Am Ende werden wir entweder den gewünschten Wert treffen und true zurückgeben, oder der Anfangs- und Endpunkt 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 in Ordnung, die Lösung scheint optimal zu sein. Aber wer garantiert, dass das Array sortiert war?

Was dann?

Auf den ersten Blick könnten wir zuerst einfach das Array sortieren und dann die obige Lösung verwenden. Aber wie würde sich das auf die Ausführungszeit auswirken?

Der beste Algorithmus ist die schnelle Sortierung mit einer zeitlichen Komplexität von O (N log (N)). Wenn wir ihn in unserer optimalen Lösung verwenden, wird sich die Leistung von O (N) auf O (N log (N)) ändern. Ist es möglich, eine lineare Lösung mit einem unsortierten Array zu finden?

Lösung 4

Zeitkomplexität: O(N).
Räumliche Komplexität: O(N).

Ja, eine lineare Lösung existiert. Dazu muss ein neues Array erstellt werden, das eine Liste der Übereinstimmungen enthält, die wir suchen. Der Kompromiss besteht hier im höheren Speicherverbrauch: Dies ist die einzige Lösung im Artikel mit einer räumlichen Komplexität, die O (1) übersteigt.

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

Dann können wir, indem wir jedes Element des Arrays verarbeiten, 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 oben gesehen, eine lineare zeitliche Komplexität von O (N) hat.

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

Um die zeitliche Komplexität von Array.prototype.includes() zu ermitteln, können wir den von MDN bereitgestellten Polyfill (geschrieben in JavaScript) betrachten oder die Methode im Quellcode einer 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;
    }
  });
}

Der iterative Teil von Array.prototype.includes() ist 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 zurückliegt, beträgt die zeitliche Komplexität O(N + (N - 1)). Durch die Verwendung der Big-O-Notation vereinfacht sich dies zu O(N) – da N den größten Einfluss bei wachsender Eingangsgröße hat.

Was die Speicherkomplexität betrifft, so ist ein zusätzliches Array erforderlich, dessen Länge das ursprüngliche Array widerspiegelt (minus eins, ja, aber das kann ignoriert werden), was zu einer räumlichen Komplexität von O(N) führt. Ein erhöhter Speicherbedarf gewährleistet dabei die maximale Effizienz des Algorithmus.

Ich hoffe, der Artikel ist für Sie als Ergänzung zum Video-Interview hilfreich. Er zeigt, dass eine einfache Aufgabe auf verschiedene Arten mit unterschiedlichen 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 zu PRO.

Quelle: habr.com