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

Kui uurisin algoritmide jõudlust, tuli mulle ette video Google'i simuleeritud intervjuust. See annab mitte ainult ülevaate, kuidas suured tehnoloogiafirmad intervjuude käiku korraldavad, vaid aitab ka mõista, kuidas algoritmilisi probleeme lahendada kõige tõhusamalt.

See artikkel on omamoodi nurgakivi videole. Anan selles kommentaare kõigi esitatud lahenduste kohta ja jagan oma versiooni lahendusest JavaScriptis. Samuti käsitletakse iga algoritmi nüansse.

Tuletame meelde: kõigile «Habra» lugejatele — 10 000 rubla soodustus, kui registreerite end Skillboxi mis tahes kursusele promokoodi «Habr» abil.

Skillbox soovitab: Praktiline kursus «Mobiilne arendaja PRO».

Ülesande seadmine

Meile antakse järjestatud massiiv ja teatud väärtus. Seejärel palutakse luua funktsioon, mis tagastab true või false, olenevalt sellest, kas mõne kahe arvu summa massiivist on võrdne antud väärtusega.

Teisisõnu, kas massiivis on kaks täisarvu x ja y, mis koos liites annavad antud väärtuse?

Näide A

Kui meile antakse massiiv [1, 2, 4, 9] ja väärtus 8, tagastab funktsioon false, sest milline kahe arvu summa massiivist ei saavuta 8.

Näide B

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

Lahendus 1. Brute force

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

Kõige ilmsem tähendus on kasutamine väheste pesatud tsüklite paaride abil.

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 nimetada efektiivseks, kuna see kontrollib iga võimalikku kahe elementi summat massiivis ja võrreldes iga indeksipaari kaks korda. (Näiteks, kui i = 1 ja j = 2 — see on tegelikult sama, mis võrrelda i = 2 ja j = 1, kuid selles lahenduses proovime mõlemat varianti).

Kuna meie lahendus kasutab väheste pesatud for-tsükleid, on see ruutjõudlusega ajakompleksus O (N²).

Lahendus 2. Binaarne otsing

Ajakompleksus: O(Nlog(N)).
Ruumiinne keerukus: O(1).

Kuna massiivid on järjestatud, saame otsida lahendust kasutades binaarset otsingut. See on kõige tõhusam algoritm järjestatud massiivide puhul. Binaarse otsingu enda aeg on O (log (N)). Siiski on ikkagi vajalik kasutada for-tsüklit, et kontrollida iga elementi ja kõiki teisi väärtusi.

Nii võib välja näha lahendus. Et kõik oleks selge, kasutame eraldi funktsiooni binaarse otsingu kontrollimiseks. Ja ka funktsiooni removeIndex(), mis tagastab massiivi versiooni, millest on arvesse võetud antud indeks.

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 alustab indeksist [0]. Seejärel loob ta massiivi versiooni, jättes välja esimese indeksi, ja kasutab binaarset otsingut, et kontrollida, kas mõne ülejäänud väärtuse lisamine massiivi annaks soovitud summa. See toiming viiakse läbi ühe korra iga massiivi elemendi jaoks.

Iseseisvalt on for-tsükli ajas keerukus O (N), kuid for-tsükli sees teeme me binaarset otsingut, mis annab koguni ajas keerukuse O (Nlog (N)). See lahendus on parem kui eelmine, kuid veel on, mida täiustada.

Lahendus 3. Lineaarne aeg

Ajas keerukus: O(N).
Ruumiinne keerukus: O(1).

Nüüd lahendame ülesande, pidades meeles, et massiiv on järjestatud. Lahendus seisneb kahe arvu võtmisest: üks alguses ja üks lõpus. Kui summa ei vasta nõutud väärtusele, muutame algus- ja lõpp-punkti.

Lõppkokkuvõttes kas kohtame soovitud väärtust ja tagastame true või algus- ja lõpp-punktid jõuavad 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 tundub olevat optimaalne. Aga kes annab garantii, et massiiv oli järjestatud?

Mis siis?

Esmapilgul oleksime võinud kõigepealt lihtsalt järjestada massiivi ja seejärel kasutada eelmist lahendust. Kuid kuidas see mõjutaks täitmisaega?

Parim algoritm on kiire sorteerimine, mille ajakulu on O(N log(N)). Kui kasutame seda meie optimaalses lahenduses, muutub selle jõudlus O(N) -lt O(N log(N)) -le. Kas on võimalik leida lineaarne lahendus sortimata massiivi jaoks?

Lahendus 4

Ajas keerukus: O(N).
Ruumi keerukus: O(N).

Jah, lineaarne lahendus eksisteerib, selleks tuleb luua uus massiiv, mis sisaldab otsitavate vasteid. Kompromiss on siin suurema mälu kasutamine: see on ainus lahendus, mille ruumi 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 näha, kas üks neist on meie väärtusega. Kui jah, siis 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 alus on for tsükkel, mille ajakulu on, nagu nägime, lineaarne O(N).

Teine iteratsiooniosa meie funktsioonist on Array.prototype.include(), JavaScripti meetod, mis tagastab true või false sõltuvalt sellest, kas massiiv sisaldab antud väärtust.

Kuna me tahame välja selgitada Array.prototype.includes() ajakompleksus, saame vaadata MDN-i pakutud polyfilli (kirjutatud JavaScriptis) või kasutada meetodit JavaScripti mootori lähtekoodis, näiteks 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() iteratsiooniosa while-tsükkel samm 7, mis (peaaegu) katab antud massiivi pikkuse. See tähendab, et selle ajakompleksus on samuti lineaarne. Kuna see on alati meie põhimassiivist ühe sammu tagapool, siis ajakompleksus on O(N + (N - 1)). Kasutades Big O Notationit, lihtsustame selle O(N) — sest just N mõjutab kõige rohkem sisendi suuruse suurenemise korral.

Kui rääkida ruumilisest keerukusest, siis on vajalik täiendav massiiv, mille pikkus peegeldab algset massiivi (kuigi see on miinus ühe võrra, aga seda saab ignoreerida), mis toob kaasa ruumilise keerukuse O(N). Suurenenud mälu kasutamine tagab algoritmi maksimaalse efektiivsuse.

Loodan, et artikkel osutub teile kasulikuks lisandina videointervjuule. See näitab, kuidas lihtne ülesanne võib olla lahendatud mitmel erineval viisil, kasutades erinevaid ressursse (aeg, mälu).

Skillbox soovitab:

• Rakenduslik veebikursus „Andmeanalüütik Pythonis“.
• Veebikursus „Frontend-arendaja amet“.
• Praktiline aastakursus „PHP arendaja algusest PRO-ni“.

Allikas: habr.com