🥇Løs et intervjuoppgave fra Google på JavaScript: 4 forskjellige metoder

Da jeg studerede algoritmers ydeevne, stødte jeg på denne video med et mock-interview fra Google. Den giver ikke kun indsigt i, hvordan interviewene foregår i store teknologivirksomheder, men den hjælper også med at forstå, hvordan algoritmiske problemer løses så effektivt som muligt.

Denne artikel fungerer som et supplement til videoen. Her giver jeg kommentarer til alle de viste løsninger samt min egen version af løsningen på JavaScript. Derudover diskuteres nuancerne ved hver algoritme.

Vi minner om: for alle lesere av «Habr» — 10 000 rubler rabatt ved påmelding til hvilket som helst Skillbox-kurs med kampanjekoden «Habr».

Skillbox anbefaler: Praktisk kursus «Mobiludvikler PRO».

Definering av oppgaven

Vi får en sorteret liste og en bestemt værdi. Derefter bliver vi bedt om at oprette en funktion, der returnerer true eller false, afhængigt af om summen af to tal fra listen kan være lig med den angivne værdi.

Med andre ord, findes der to heltal x og y i listen, hvis sum er lig med den angivne værdi?

Eksempel A

Hvis vi fik listen [1, 2, 4, 9] og værdien 8, vil funktionen returnere false, fordi ingen to tal i listen kan give 8 ved addition.

Eksempel B

Men hvis det er listen [1, 2, 4, 4] og værdien 8, så skal funktionen returnere true, fordi 4 + 4 = 8.

Løsning 1. Brute force

Tidskompleksitet: O(N²).
Pladskompleksitet: O(1).

Den mest indlysende tilgang er brugen af et par indlejrede løkker.

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;
};

Denne løsning kan ikke kaldes effektiv, da den tjekker hver mulig sum af to elementer i listen og sammenligner hvert indekspar to gange. (For eksempel, når i = 1 og j = 2 — det er faktisk det samme som at sammenligne med i = 2 og j = 1, men i denne løsning prøver vi begge muligheder).

Da vores løsning bruger et par indlejrede for-løkker, er den kvadratisk med en tidskompleksitet på O(N²).

Løsning 2. Binær søgning

Tidskompleksitet: O(Nlog(N)).
Pladskompleksitet: O(1).

Siden arrayene er sortert, kan vi se etter en løsning ved hjelp av binær søk. Dette er den mest effektive algoritmen for sorterte arrays. Binær søk har en kjøretid på O(log(N)). Likevel må vi bruke en for-løkke for å sjekke hvert element opp mot alle de andre verdiene.

Slik kan en løsning se ut. For å gjøre alt klart, bruker vi en egen funksjon for å kontrollere binær søk. Vi bruker også funksjonen removeIndex(), som returnerer en versjon av arrayet uten den angitte indeksen.

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;
};

Algoritmen starter med indeks [0]. Deretter lager den en versjon av arrayet som ekskluderer den første indeksen, og bruker binær søk for å sjekke om det er mulig å legge til noen av de gjenværende verdiene i arrayet for å oppnå ønsket sum. Denne handlingen gjentas én gang for hvert element i arrayet.

Selv om for-løkka har en lineær tidskompleksitet på O(N), utfører vi en binær søk inne i for-løkka, noe som gir en total tidskompleksitet på O(Nlog(N)). Denne løsningen er bedre enn den forrige, men det er fortsatt rom for forbedringer.

Løsning 3. Lineær tid

Tidskompleksitet: O(N).
Pladskompleksitet: O(1).

Nå skal vi løse oppgaven, vel vitende om at arrayet er sortert. Løsningen er å ta to tall: ett i begynnelsen og ett på slutten. Hvis resultatet er forskjellig fra det som kreves, bytter vi start- og sluttpunkt.

Til slutt møter vi enten den ønskede verdien og returnerer true, ellers vil start- og sluttpunktene møtes og vi returnerer false.

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;
};

Nå er alt bra, løsningen ser ut til å være optimal. Men hvem kan garantere at arrayet var sortert?

Hva da?

Ved første øjekast kunne vi måske have ordnet arrayet først og derefter brugt den ovenstående løsning. Men hvordan vil det påvirke køretiden?

Den bedste algoritme er hurtig sortering med en tidskompleksitet på O(Nlog(N)). Hvis vi anvender den i vores optimale løsning, vil dens ydeevne ændre sig fra O(N) til O(Nlog(N)). Er det muligt at finde en lineær løsning med et usorteret array?

Løsning 4

Tidskompleksitet: O(N).
Plads kompleksitet: O(N).

Ja, en lineær løsning findes; for dette skal der oprettes et nyt array, der indeholder listen over de matches, vi søger. Kompromiset her er en mere aktiv brug af hukommelse: det er den eneste løsning i artiklen med en plads kompleksitet, der overstiger O(1).

Hvis den første værdi i dette array er 1, og den værdi, vi søger, er 8, kan vi tilføje værdien 7 til 'søgeværdier'-arrayet.

Derefter, når vi behandler hvert element i arrayet, kan vi kontrollere 'søgeværdier'-arrayet for at se, om et af dem er lig med vores værdi. Hvis ja, returnerer vi true.

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;
};

Grundlaget for løsningen er en for-løkke, der som vi har set ovenfor har lineær tidskompleksitet O(N).

Den anden iterative del af vores funktion er Array.prototype.include(), en JavaScript-metode, der returnerer true eller false afhængigt af om arrayet indeholder den angivne værdi.

For at finde ud af tidskompleksiteten for Array.prototype.includes() kan vi se på polyfill'en, der leveres af MDN (og skrevet i JavaScript), eller vi kan se på metoden i kildekoden til en JavaScript-motor, som Google V8 (C++).

// 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;
    }
  });
}

Her er den iterative del af Array.prototype.include() en while-løkke, der på trin 7 (næsten) krydser hele længden af det pågældende array. Det betyder, at dens tidskompleksitet også er lineær. Og da det altid ligger et skridt bag vores hovedarray, er tidskompleksiteten lig med O(N + (N - 1)). Ved at bruge Big O Notation forenkler vi det til O(N) — fordi det er N, der har den største indflydelse ved stigende inputstørrelse.

Når det gjelder romlig kompleksitet, kreves det et ekstra array, hvis lengde gjenspeiler det opprinnelige arrayet (minus én, ja, men dette kan ignoreres), noe som resulterer i romlig kompleksitet O(N). Den økte minnebruken gir maksimal effektivitet for algoritmen.

Jeg håper artikkelen vil være nyttig for deg som et supplement til videointervjuet. Den viser at en enkel oppgave kan løses på flere forskjellige måter med varierende ressurser (tid, minne).

Skillbox anbefaler:

Praktisk nettbasert kurs «Python Data Analyst».

Nettkurs «Frontend-utvikler».

Praktisk ettårig kurs «PHP-utvikler fra 0 til PRO».

Kilde: habr.com

Løser et Google-interviewproblem på JavaScript: 4 forskellige metoder

Definering av oppgaven

Hva da?