Zgjidhim një detyrë nga intervista e Google në JavaScript: 4 mënyra të ndryshme

Kur kur isha duke studiuar performancën e algoritemeve, m'u ndodh ky video me një intervistë të simuluar Google. Ajo jo vetëm që ofron një ide se si zhvillohen intervistat në kompanitë teknologjike të mëdha, por gjithashtu ndihmon për të kuptuar se si zgjidhen problemet algoritmike në mënyrën më efikase.

Ky artikull është një lloj shoqëruesi për videon. Në të jap komente për të gjitha zgjidhjet e paraqitura, plus versionin tim të zgjidhjes në JavaScript. Gjithashtu diskutohen nuancat e secilit algoritëm.

Kujtojmë: për të gjithë lexuesit e "Habra" — zbritje prej 10,000 rublej për regjistrimin në çdo kurs Skillbox me kodin promocional "Habr".

Skillbox rekomandon: Kurs praktik «Programues i celularëve PRO».

Vendosja e detyrës

Na jepet një listë të renditur dhe një vlerë të caktuar. Pastaj kërkohet të krijojmë një funksion që kthen true ose false, në varësi të kësaj, a mundet shuma e cdo dy numrash në listë të jetë e barabartë me vlerën e dhënë.

Me fjalë të tjera, a ka në listë dy numra të plotë x dhe y, të cilët kur shikohen së bashku japin vlerën e caktuar?

Shembulli A

Nëse na jepet lista [1, 2, 4, 9] dhe vlera 8, funksioni do të kthejë false, sepse asnjë çift numrash nga lista nuk mund të japin 8 kur mblidhen.

Shembulli B

Por nëse kjo është lista [1, 2, 4, 4] dhe vlera 8, funksioni duhet të kthejë true, sepse 4 + 4 = 8.

Zgjidhja 1. Metoda brute-force

Kompleksiteti kohor: O(N²).
Kompleksiteti hapësinor: O(1).

Zgjidhja më e dukshme është përdorimi i një çifti ciklesh të përfshira.

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

Kjo zgjidhje nuk mund të quhet efikase, sepse ajo kontrollon çdo mundësi të sumës së dy elementeve në listë, dhe gjithashtu krahason çdo çift indekse dy herë. (Për shembull, kur i = 1 dhe j = 2 — kjo në fakt është e njëjta gjë si të krahasosh me i = 2 dhe j = 1, por në këtë zgjidhje provon të dy mundësitë).

Duke qenë se pala jonë e zgjidhjes përdor një çift ciklesh të përfshira, ajo është katëshe në kompleksitetin kohor O (N²).

Zgjidhja 2. Kërkimi binar

Kompleksiteti kohor: O(Nlog(N)).
Kompleksiteti hapësinor: O(1).

Duke marrë parasysh se listat janë të renditur, mund të kërkojmë një zgjidhje duke përdorur kërkimin binar. Ky është algoritmi më efikas për listat e renditura. Kërkimi binar ka vetë një kohë ekzekutimi O (log (N)). Megjithatë, ende duhet të përdorim një cikël for për të kontrolluar çdo element ndaj të gjitha vlerave të tjera.

Ja si mund të duket zgjidhja. Për të bërë gjithçka të qartë, ne përdorim një funksion të veçantë për të kontrolluar kërkimin binar. Po ashtu, një funksion removeIndex () që kthen versionin e listës përjashtuar indekset e dhëna.

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

Algoritmi fillon nga indeksi [0]. Pastaj krijon një version të listës që përjashton indekson e parë, dhe përdor kërkimin binar për të kontrolluar nëse ndonjë prej vlerave të mbetura mund të shtohet në listë për të arritur shumën dëshiruese. Ky veprim kryhet një herë për çdo element në listë.

Përveç kësaj, cikli for do të ketë kompleksitetin kohor linear O (N), por brenda ciklit for ne kryejmë kërkimin binar, çka na jep një kompleksitet të përgjithshëm O (Nlog (N)). Kjo zgjidhje është më e mirë se paraardhësi i saj, por ekosistem i cacë.

Zgjidhja 3. Koha lineare

Kompleksiteti kohor: O(N).
Kompleksiteti hapësinor: O(1).

Tani do të zgjidhim problemin, duke mbajtur mend se lista është e renditur. Zgjidhja është të marrim dy numra: një në fillim dhe një në fund. Nëse rezultati nuk është i barabartë me atë që kërkohet, ndërron fillimin dhe pikën përfundimtare.

Në fund, ne ose do të takojmë vlerën e dëshiruar dhe do të kthejmë true, ose fillimi dhe fundi do të takohen dhe do të kthejmë 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;
};

Tani është mirë, zgjidhja duket e optimizuar. Por kush jep garanci që lista ishte e renditur?

Atëherë, çfarë?

Në shikim të parë, mund të renditnim listën fillimisht dhe pastaj të përdorim zgjidhjen e mësipërme. Por si do të ndikonte kjo në kohën e ekzekutimit?

Algoritmi më i mirë është renditja e shpejtë me kompleksitetin kohor O (Nlog (N)). Nëse e përdorim atë në zgjidhjen tonë optimale, ajo do të ndryshonte performancën nga O (N) në O (Nlog (N)). A mund të gjendet një zgjidhje lineare me lista të pa renditura?

Zgjidhja 4

Kompleksiteti kohor: O(N).
Kompleksiteti hapësinor: O(N).

Po, ekziston një zgjidhje lineare; për këtë, duhet të krijojmë një varg të ri që përmban listën e përputhjeve që po kërkojmë. Kompromisi këtu qëndron në përdorimin më aktiv të memories: kjo është zgjidhja e vetme në artikull me kompleksitetin hapësinor që tejkalon O (1).

Nëse vlera e parë e këtij vargu është 1 dhe vlera e kërkuar është 8, mund ta shtojmë vlerën 7 në vargun 'vlerave të kërkimit'.

Pastaj, duke përpunuar çdo element të vargut, mund të kontrollojmë vargun 'vlerave të kërkimit' dhe të shohim nëse ndonjëra prej tyre është e barasvlershme me vlerën tonë. Nëse po, kthejmë 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;
};

Thelbi i zgjidhjes është një cikël for, i cili, siç e pamë më sipër, ka kompleksitetin e kohës O (N).

Pjesa e dytë iteruese e funksionit tonë është Array.prototype.include (), një metodë JavaScript që do të kthejë true ose false në varësi të faktit nëse vargu përmban vlerën e dhënë.

Për të zbuluar kompleksitetin e kohës së Array.prototype.includes (), mund të shqyrtojmë polyfill-in e ofruar nga MDN (dhe të shkruar në JavaScript) ose të përdorim metodën në kodin burimor të motorit JavaScript, si 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;
    }
  });
}

Këtu, pjesa iteruese e Array.prototype.include () është një cikël while në hapin 7, i cili (gati) mbulon gjithë gjatësi e këtij vargu. Kjo do të thotë që kompleksiteti i saj kohor gjithashtu është linear. Dhe, duke qenë se ajo është gjithmonë një hap prapa vargut tonë kryesor, atëherë kompleksiteti kohor është O (N + (N — 1)). Duke përdorur Notacionin Big O, e thjeshtojmë atë në O (N) — sepse N ka ndikimin më të madh kur rritet madhësia e hyrjes.

Sa i përket kompleksitetit hapësinor, na nevojitet një varg shtesë, gjatësia e të cilit reflekton vargun origjinal (minus një, po, por kjo mund të injorohet), që çon në kompleksitet hapësinor O (N). Dhe, rritja e përdorimit të memories siguron efikasitetin maksimal të algoritmit.

Shpresoj që artikulli të jetë i dobishëm për ju si një shtesë për intervistën video. Ai tregon se një detyrë e thjeshtë mund të zgjidhet në disa mënyra të ndryshme me sasi të ndryshme burimesh të përdorura (kohë, memorie).

Skillbox rekomandon:

• Kursi online i aplikimit «Analist i të dhënave Python».
• Kurs online «Profesionisti frontend zhvillues».
• Kurs praktik njëvjeçar «PHP zhvillues nga 0 në PRO».

Burimi: habr.com