Hash Funktion Challenge

Aufgabe:

Du schreibst ein Programm für Film-Streaming in Flugzeugen.

Gäste auf längeren Flügen schauen gerne einen zweiten Film, wenn der erste endet. Sie beschweren sich aber, dass das Flugzeug normalerweise landet, bevor sie das Ende sehen können.

Du baust also eine Funktion zur Auswahl von zwei Filmen, deren Gesamtlaufzeit genau der Fluglänge entspricht.

Schreib eine Funktion, die eine ganze Zahl flightLength (in Minuten) und ein Array von ganzen Zahlen movieLengths (in Minuten) aufnimmt und einen booleschen Wert zurückgibt.

Der boolsche Wert gibt an, ob es zwei Zahlen gibt, deren Summe flightLength entspricht.

Beachte:

  • Geh davon aus, dass die Passagiere genau zwei Filme ansehen werden.
  • Zwinge deine Passagiere nicht denselben Film zweimal anzuschauen.
  • Optimiere für die Laufzeit und nicht für den Speicher.

Lösung:

function canTwoMoviesFillFlight(movieLengths, flightLength) {

  // Bisher gesehene Filmlängen
  const movieLengthsSeen = new Set();

  for (let i = 0; i < movieLengths.length; i++) {
    const firstMovieLength = movieLengths[i];

    const matchingMovieLength = flightLength - firstMovieLength;
    if (movieLengthsSeen.has(matchingMovieLength)) {
      return true;
    }

    movieLengthsSeen.add(firstMovieLength);
  }

  // Nie eine Übereinstimmung gefunden
  return false;
}

Zeile für Zeile:

function canTwoMoviesFillFlight(movieLengths, flightLength) {

  const movieLengthsSeen = new Set();

}


Vielleicht hattest du als erstes die Idee mit zwei for-Loops die Filmlängen miteinander zu vergleichen. Diese Berechnungszeit würde so mit O(n2) wachsen, was ein zu schnelles Wachstum ist.
Gibt es eine Lösung mit linearem Wachstum O(n)?

Welche Datenstruktur hat eine konstante Zeit für den Aufruf ohne Hash? Ein Set.
Mit einem Set können wir has() nutzen, um den Inhalt von einem Item ohne aufwändige Loops zu überprüfen.


function canTwoMoviesFillFlight(movieLengths, flightLength) {

  const movieLengthsSeen = new Set();

  for (let i = 0; i < movieLengths.length; i++) {

  }

}

Wir führen den Inhalt des Loops für alle Filmlängen aus.
Da der Loop bereits bei null beginnt, muss der letzte Durchlauf bei der Gesamtzahl - 1 das letzte Mal ausgeführt werden.


function canTwoMoviesFillFlight(movieLengths, flightLength) {

  const movieLengthsSeen = new Set();

  for (let i = 0; i < movieLengths.length; i++) {
      
    const firstMovieLength = movieLengths[i];
 
  }

}


Dieser Schritt ist für die Leserlichkeit gedacht. Da der reine Zugriff auf das movieLenghts Array in unserem Kontext eine impliziten Bedeutung hat, schreiben wir diese explizit hin.


function canTwoMoviesFillFlight(movieLengths, flightLength) {

  // Bisher gesehene Filmlängen
  const movieLengthsSeen = new Set();

  for (let i = 0; i < movieLengths.length; i++) {
    const firstMovieLength = movieLengths[i];

    const matchingMovieLength = flightLength - firstMovieLength;

  }

}

Da beide Filmlängen genau der Fluglänge entsprechen müssen, können wir diese Addition nach der zweiten Filmlänge auflösen.


function canTwoMoviesFillFlight(movieLengths, flightLength) {

  const movieLengthsSeen = new Set();

  for (let i = 0; i < movieLengths.length; i++) {
    const firstMovieLength = movieLengths[i];

    const matchingMovieLength = flightLength - firstMovieLength;

    if (movieLengthsSeen.has(matchingMovieLength) {
      return true; 
    }  

  }

}

Nun können wir die has() methode vom Set brauchen, um direkt die Existenz derselben Filmlänge zu bestimmen.
Sobald wir die passende zweite Filmlänge gefunden haben, ist die Suche zu Ende und wir geben true zurück.


function canTwoMoviesFillFlight(movieLengths, flightLength) {

  const movieLengthsSeen = new Set();

  for (let i = 0; i < movieLengths.length; i++) {
    const firstMovieLength = movieLengths[i];

    const matchingMovieLength = flightLength - firstMovieLength;

    if (movieLengthsSeen.has(matchingMovieLength) {
      return true; 
    } else {
      movieLengthsSeen.add(firstMovieLength);
    }
  }

}

Falls diese Filmlänge keine passende zweite Filmlänge hat, um die Flugzeit exakt zu füllen, nehmen wir die Filmlänge in unser Set auf.
Wir können so auch ausschliessen, dass ein Fluggast denselben Film doppelt sieht, weil wir Überprüfung vor dem Hinzufügen in das Set durchführen.


function canTwoMoviesFillFlight(movieLengths, flightLength) {

  const movieLengthsSeen = new Set();

  for (let i = 0; i < movieLengths.length; i++) {
    const firstMovieLength = movieLengths[i];

    const matchingMovieLength = flightLength - firstMovieLength;

    if (movieLengthsSeen.has(matchingMovieLength) {
      return true; 
    } else {
      movieLengthsSeen.add(firstMovieLength);
    }
  }
    
  return false;

}

Mit jedem Durchgang in der for-Schlaufe haben wir eine Filmlänge mehr zum Vergleich bis wir im Falle keiner passenden zweiten Filmlänge false zurückgeben.


Komplexität

Wir haben bezüglich der Zeit optimiert. Die Rechenzeit wächst nun mit O(n) anstatt O(n2) mit wachsendem Input. Jedoch wächst der Arbeitsspeicherplatz auch mit O(n), was wir zugunsten der verkürzten Zeit in Kauf nehmen.


Bonus-Challenges

  1. Was wenn der Film mit einer Toleranz von 20 Minuten vor oder nach der Flugzeit enden könnte?
function canTwoMoviesFillFlight(movieLengths, flightLength) {

  const movieLengthsSeen = new Set();

  for (let i = 0; i < movieLengths.length; i++) {
    // Math.round()
    const firstMovieLength = Math.round(movieLengths[i]);

    const matchingMovieLength = flightLength - firstMovieLength;

    if (movieLengthsSeen.has(matchingMovieLength) {
      return true; 
    } else {
      movieLengthsSeen.add(firstMovieLength);
    }
  }
    
  return false;

}

Math.round() rundet die jeweils >= 0.5 aufwärts und > 0.5 abwärts. Wir können auf diese Weise eine simple Toleranz um das Flugende generieren.