Lahendame Google'i intervjuu ülesande JavaScriptis: 4 erinevat viisi

Kui ma uurisin algoritmide jõudlust, leidsin selle video Google'i simulatsioonintervjuudest. See annab mitte ainult ülevaate sellest, kuidas suured tehnoloogiaettevõtted vestlusi läbiviivad, vaid aitab ka mõista, kuidas algoritmilisi probleeme lahendada, tehes seda kõige tõhusamal viisil.

See artikkel on omamoodi video kaaslane. Selles annan kommentaare kõigi esitatud lahenduste kohta ning oma versiooni lahendusest JavaScriptis. Arutame ka iga algoritmi nüansse.

Tuletame meelde: kõigile «Habr» lugejatele – 10 000 rubla allahindlus igale Skillboxi kursusele, kasutades sooduskoodi «Habr».

Skillbox soovitab: Praktiline kursus «Mobiilne arendaja PRO».

Ülesande seadmine

Meile antakse järjestatud massiiv ja määratud väärtus. Seejärel palutakse luua funktsioon, mis tagastab true või false, sõltuvalt sellest, kas mis tahes kahe massiivi arvu summa võib olla võrdne määratud väärtusega.

Teisisõnu, kas massiivis on kaks täisarvu x ja y, mille summa on antud väärtus?

Näide A

Kui meile anti massiiv [1, 2, 4, 9] ja väärtus 8, tagastab funktsioon false, kuna kaks massiivi numbrit ei saa anda 8 summana.

Näide B

Kuid kui see on massiiv [1, 2, 4, 4] ja väärtus 8, peab funktsioon tagastama true, kuna 4 + 4 = 8.

Lahendus 1. Brute Force

Aja keerukus: O(N²).
Ruumiline keerukus: O(1).

Kõige ilmselgem lähenemine on kasutada paari sisemist tsüklit.

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

Seda lahendust ei saa pidada tõhusaks, kuna see kontrollib iga võimalikku kahe massiivi elemendi summat ja samuti võrdleb iga paari indekseid kaks korda. (Näiteks kipub i = 1 ja j = 2 olema sisuliselt sama, mis võrdlemine i = 2 ja j = 1, kuid see lahendus proovib mõlemat varianti).

Kuna meie lahendus kasutab kahte sisemist tsüklit for, on see ruutmeetriline ajakeerukus O(N²).

Lahendus 2. Binaarne otsing

Aja keerukus: O(Nlog(N)).
Ruumiline keerukus: O(1).

Kuna massiivid on järjestatud, saame otsida lahendust, kasutades binaarset otsimist. See on kõige tõhusam algoritm järjestatud massiivide jaoks. Binaarse otsimise enda täitmise aeg on O(log(N)). Siiski tuleb kasutada for-tsüklit, et kontrollida iga elementi kõigi muude väärtuste suhtes.

Nii võib välja näha lahendus. Et kõik oleks arusaadav, kasutame eraldi funktsiooni binaarse otsingu kontrollimiseks. Samuti funktsiooni removeIndex (), mis tagastab massiivi versiooni, milles on arvestatud kindlat indeksit.

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

Algoritm algab indeksist [0]. Siis loob ta versiooni massiivist, millel on välistatud esimene indeks, ja kasutab binaarset otsingut, et kontrollida, kas saab massiivi ühe ülejäänud väärtusega koos anda soovitud summa. Seda teavet tehakse kord igale massiivi elemendile.

Isegi for-tsükkel on lineaarse ajakompleksusega O (N), kuid for-tsükli sees sooritame binaarse otsingu, mis annab kogu ajakompleksuse O (Nlog (N)). See lahendus on parem kui eelmine, kuid veel on ruumi parandamiseks.

Lahendus 3. Liine aeg

Ajakompleksus: O(N).
Ruumiline keerukus: O(1).

Nüüd hakkame ülesannet lahendama, meeles pidades, et massiiv on sorteeritud. Lahendus seisneb kahe arvu võtmes: üks alguses ja üks lõpus. Kui tulemus ei vasta soovitule, siis vahetame algus- ja lõpp-punkti.

Lõpuks kohtume kas soovitud väärtusega ja tagastame true, või algus- ja lõpp-punktid satuvad kokku ja tagastame 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üüd on kõik hästi, lahendus näib olevat optimaalne. Kuid kes garanteerib, et massiiv on järjestatud?

Mis siis?

Esmapilgul oleksime võinud kõigepealt lihtsalt massiivi järjestada ja siis kasutada ülaltoodud lahendust. Kuid kuidas see mõjutab täitmise aega?

Parim algoritm on kiire sorteerimine, mille ajakompleksus on O (Nlog (N)). Kui kasutame seda meie optimaalses lahenduses, siis selle jõudlus muutub O (N) -lt O (Nlog (N)). Kas on võimalik leida lineaarne lahendus järjestamata massiivi puhul?

Lahendus 4

Ajakompleksus: O(N).
Ruumiline komplekssus: O(N).

Jah, lineaarne lahendus eksisteerib, selle jaoks tuleb luua uus massiiv, mis sisaldab loetelu kohtumistest, mida me otsime. Kompromiss siin on aktiivsem mälu kasutamine: see on ainus lahendus artiklis, mille ruumiline keerukus ületab O (1).

Kui selle massiivi esimene väärtus on 1 ja otsitav väärtus on 8, saame lisada väärtuse 7 „otsinguväärtuste” massiivi.

Seejärel, töötades läbi iga massiivi elemendi, saame kontrollida „otsinguväärtuste” massiivi ja vaadata, kas üks neist on meie väärtusega võrdne. Kui jah, tagastame 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;
};

Lahenduse põhialus on for-tsükkel, mis, nagu me eespool nägime, omab lineaarset ajakompleksust O (N).

Meie funktsiooni teine iteratiivne osa on Array.prototype.include(), JavaScripti meetod, mis tagastab true või false, olenevalt sellest, kas massiiv sisaldab antud väärtust.

Ajakompleksuse välja selgitamiseks Array.prototype.includes() osas saame vaadata MDN-i poolt pakutud polyfill'i (ja JavaScriptis kirjutatud) või kasutada meetodit, mis on kirjutatud JavaScripti mootori lähtekoodis, nagu 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;
    }
  });
}

Siin on Array.prototype.include() iteratiivne osa sammu 7 while-tsükkel, mis (peaaegu) katab antud massiivi pikkuse. See tähendab, et selle ajakompleksus on samuti lineaarne. Kuna see on alati meie peamisse massiivi üheni sammu võrra maas, siis ajakompleksus on O (N + (N — 1)). Big O notation'i kasutades lihtsustame selle O (N) — sest just N-l on suurim mõju sisendi suuruse suurenedes.

Ruumilise keerukuse osas on vajalik lisa massiiv, mille pikkus peegeldab algset massiivi (ühe võrra vähem, jah, kuid seda saab ignoreerida), mis viib ruumilise keerukuseni O (N). Suurenenud mälu kasutamine tagab aga algoritmi maksimaalse efektiivsuse.

Loodan, et artikkel osutub teile kasulikuks video intervjuu lisana. See näitab, et lihtne ülesanne saab lahendada mitmel erineval viisil erineva ressursikasutusega (aeg, mälu).

Skillbox soovitab:

• Rakenduslik veebikursus «Andmeanalüütik Pythonis».
• Veebikursus «Frontend-arendaja amet».
• Praktiline aastakursus «PHP-arendaja 0-st PRO-ni».

Allikas: habr.com