Probleemi lahendamine Google'i intervjuust JavaScriptis: 4 erinevat viisi

Algoritmide toimivust uurides puutusin sellega kokku See on video Google'i näidisintervjuust.. See mitte ainult ei anna aimu sellest, kuidas suurtes tehnoloogiakorporatsioonides intervjuusid läbi viiakse, vaid võimaldab ka mõista, kuidas algoritmilisi probleeme võimalikult tõhusalt lahendatakse.

See artikkel on omamoodi kaas videole. Selles kommenteerin kõiki näidatud lahendusi ja oma JavaScripti lahendust. Arutatakse ka iga algoritmi nüansse.

Tuletame meelde: kõigile "Habr" lugejatele - allahindlus 10 000 rubla, kui registreerute mis tahes Skillboxi kursusele, kasutades sooduskoodi "Habr".

Skillbox soovitab: Praktiline kursus "Mobile Developer PRO".

Probleemi avaldus

Meile antakse järjestatud massiiv ja konkreetne väärtus. Seejärel palutakse luua funktsioon, mis tagastab tõese või väära sõltuvalt sellest, kas massiivi kahe arvu summa võib võrduda antud väärtusega.

Teisisõnu, kas massiivis on kaks täisarvu, x ja y, mis kokku liitmisel võrdub määratud väärtusega?

Näide A

Kui meile antakse massiiv [1, 2, 4, 9] ja väärtus on 8, tagastab funktsioon väärtuse Väär, kuna ükski massiiv ei saa anda 8-ni.

Näide B

Aga kui see on massiiv [1, 2, 4, 4] ja väärtus on 8, peaks funktsioon tagastama väärtuse tõene, kuna 4 + 4 = 8.

Lahendus 1: jõhker jõud

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

Kõige ilmsem tähendus on pesastatud silmuste paari kasutamine.

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

See lahendus ei ole tõhus, kuna see kontrollib massiivi kahe elemendi iga võimalikku summat ja võrdleb ka iga indeksi paari kaks korda. (Näiteks kui i = 1 ja j = 2 on tegelikult sama, mis i = 2 ja j = 1 võrdlemine, kuid selles lahenduses proovime mõlemat varianti).

Kuna meie lahendus kasutab ahelate jaoks pesastatud paari, on see ruutkeskne O(N²) aja keerukusega.

Lahendus 2: binaarne otsing

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

Kuna massiivid on järjestatud, saame lahendust otsida kahendotsingu abil. See on järjestatud massiivide jaoks kõige tõhusam algoritm. Binaarse otsingu enda tööaeg on O(log(N)). Siiski peate siiski kasutama for-tsüklit, et kontrollida iga elementi kõigi teiste väärtustega.

Siit saate teada, milline võib lahendus välja näha. Asjade selgeks tegemiseks kasutame binaarse otsingu juhtimiseks eraldi funktsiooni. Ja ka funktsioon removeIndex(), mis tagastab massiivi versiooni miinus antud indeks.

const findSum = (arr, val) => {
  for (let i = 0; i < arr.length; i++){
    if (binarySearch(removeIndex(arr, i), val - arr[i])) {
      return true;
    }
  };
  return false;
};
 
const removeIndex = (arr, 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]) {
      end = pivot - 1;
    } else 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]. Seejärel loob see massiivi versiooni, mis ei sisalda esimest indeksit, ja kasutab binaarset otsingut, et näha, kas soovitud summa saamiseks saab massiivile lisada mõnda ülejäänud väärtust. Seda toimingut tehakse üks kord iga massiivi elemendi jaoks.

For-silmuse enda lineaarne ajaline keerukus on O(N), kuid for-tsükli sees teostame binaarse otsingu, mis annab üldise aja keerukuse O(Nlog(N)). See lahendus on parem kui eelmine, kuid arenguruumi on veel.

Lahendus 3: lineaarne aeg

Aja keerukus: O(N).
Ruumi keerukus: O(1).

Nüüd lahendame probleemi, pidades meeles, et massiiv on sorteeritud. Lahenduseks on võtta kaks numbrit: üks alguses ja teine ​​lõpus. Kui tulemus erineb nõutavast, siis muutke algus- ja lõpp-punkti.

Lõpuks leiame soovitud väärtuse ja tagastame tõese või lähte- ja lõpp-punktid lähenevad ja tagastavad vale.

const findSum = (arr, val) => {
  let start = 0;
  let end = arr.length - 1;
  while (start < end) {
    let sum = arr[start] + arr[end];
    if (sum > val) {
      end -= 1;
    } else if (sum < val) {
      start += 1;
    } else {
      return true;
    };
  };
  return false;
};

Nüüd on kõik korras, lahendus tundub optimaalne. Aga kes saab garanteerida, et massiiv on tellitud?

Mis siis?

Esmapilgul oleksime võinud lihtsalt massiivi esmalt tellida ja seejärel kasutada ülaltoodud lahendust. Aga kuidas see täitmisaega mõjutab?

Parim algoritm on kiirsortimine ajalise keerukusega O (Nlog (N)). Kui kasutame seda oma optimaalses lahenduses, muudab see oma jõudlust O(N) asemel O(Nlog(N)). Kas järjestamata massiiviga on võimalik leida lineaarne lahendus?

4 lahendus

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

Jah, on olemas lineaarne lahendus; selleks peame looma uue massiivi, mis sisaldab otsitavate vastete loendit. Kompromiss on siin suurem mälukasutus: see on ainus lahendus paberil, mille ruumi keerukus on suurem kui O(1).

Kui antud massiivi esimene väärtus on 1 ja otsitav väärtus on 8, saame massiivile "otsinguväärtused" lisada väärtuse 7.

Seejärel saame massiivi iga elemendi töötlemisel kontrollida "otsinguväärtuste" massiivi ja näha, kas üks neist on võrdne meie väärtusega. Kui jah, tagasta tõene.

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 aluseks on for-silmus, mille lineaarne ajaline keerukus, nagu eespool nägime, on O(N).

Funktsiooni teine ​​iteratiivne osa on Array.prototype.include(), JavaScripti meetod, mis tagastab tõene või väär, sõltuvalt sellest, kas massiiv sisaldab antud väärtust.

Array.prototype.includes() ajalise keerukuse väljaselgitamiseks võime vaadata MDN-i pakutavat polütäitmist (ja kirjutatud JavaScriptis) või kasutada meetodit JavaScripti mootori, näiteks Google V8 (C++) lähtekoodis.

// 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 7. sammus while-tsükkel, mis (peaaegu) läbib antud massiivi kogu pikkuse. See tähendab, et ka selle ajaline keerukus on lineaarne. Noh, kuna see on alati meie põhimassiivist sammu võrra maas, on ajaline keerukus O (N + (N - 1)). Kasutades suurt O-tähistust, lihtsustame selle väärtuseks O(N), sest just N-l on sisendi suuruse suurendamisel suurim mõju.

Ruumilise keerukuse osas on vaja täiendavat massiivi, mille pikkus peegeldab algset massiivi (miinus üks, jah, kuid seda võib ignoreerida), mille tulemuseks on O(N) ruumiline keerukus. Suurem mälukasutus tagab algoritmi maksimaalse efektiivsuse.

Loodan, et artikkel on teile kasulik videointervjuu täiendusena. See näitab, et lihtsat probleemi saab lahendada mitmel erineval viisil, kasutades erinevaid ressursse (aeg, mälu).

Skillbox soovitab:

• Rakendatud veebikursus "Pythoni andmeanalüütik".
• Veebikursus "Elukutse eesprogrammi arendaja".
• Praktilise aasta kursus "PHP arendaja 0-st PRO-le".

Allikas: www.habr.com