🥇Kuthetsa vuto pafunso la Google mu JavaScript: Njira 4 zosiyanasiyana

Pamene ndimaphunzira machitidwe a ma algorithms, ndinapeza izi Iyi ndi kanema wa zokambirana zonyoza za Google.. Sizimangopereka lingaliro la momwe kuyankhulana kumachitikira m'mabungwe akuluakulu aukadaulo, komanso kumakupatsani mwayi womvetsetsa momwe mavuto a algorithmic amathetsedwera moyenera momwe mungathere.

Nkhaniyi ndi mtundu wotsatizana ndi kanema. M'menemo ndimapereka ndemanga pamayankho onse omwe akuwonetsedwa, kuphatikiza yankho langa mu JavaScript. Ma nuances a algorithm iliyonse amakambidwanso.

Tikukukumbutsani: kwa owerenga onse a Habr - kuchotsera ma ruble 10 polembetsa maphunziro aliwonse a Skillbox pogwiritsa ntchito nambala yotsatsira ya Habr.

Skillbox imalimbikitsa: Njira yothandiza "Mobile Developer PRO".

Kupanga kwa vuto

Timapatsidwa mndandanda wolamulidwa ndi mtengo wake. Kenako imafunsidwa kuti ipange ntchito yomwe imabweza zoona kapena zabodza malingana ndi kuchuluka kwa manambala awiri aliwonse mugululi angafanane ndi mtengo womwe wapatsidwa.

Mwa kuyankhula kwina, kodi pali mitundu iwiri ya chiwerengero, x ndi y, yomwe ikaphatikizidwa pamodzi imakhala yofanana ndi mtengo wotchulidwa?

Chitsanzo A

Ngati tipatsidwa mndandanda [1, 2, 4, 9] ndipo mtengo ndi 8, ntchitoyi idzabwerera zabodza chifukwa palibe nambala ziwiri pamndandanda zomwe zingawonjezere mpaka 8.

Chitsanzo B

Koma ngati ndi gulu [1, 2, 4, 4] ndipo mtengo ndi 8, ntchitoyo iyenera kubwerera chifukwa 4 + 4 = 8.

Yankho 1: Mphamvu zopanda mphamvu

Kuvuta kwa nthawi: O(N²).
Kuvuta kwa danga: O (1).

Tanthauzo lodziwikiratu ndikugwiritsa ntchito malupu okhala ndi zisa.

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

Yankho ili silothandiza chifukwa limayang'ana kuchuluka kwa zinthu ziwiri zomwe zingatheke pamndandanda ndikufaniziranso ma indices awiri. (Mwachitsanzo, pamene i = 1 ndi j = 2 ndizofanana ndikufanizira ndi i = 2 ndi j = 1, koma mu yankho ili timayesa zonse ziwiri).

Chifukwa yankho lathu limagwiritsa ntchito zisa zokhala ndi malupu, ndizovuta komanso zovuta za nthawi ya O(N²).

Yankho 2: Kusaka kwa Binary

Kuvuta kwa nthawi: O(Nlog(N)).
Kuvuta kwa danga: O(1).

Popeza maguluwo adalamulidwa, titha kusaka yankho pogwiritsa ntchito kusaka kwa binary. Iyi ndiye algorithm yothandiza kwambiri pamasanjidwe oyitanidwa. Kusaka kwa binary komwe kuli ndi nthawi yothamanga ya O(logi(N)). Komabe, mukufunikirabe kugwiritsa ntchito loop kuti muwone chilichonse motsutsana ndi zinthu zina zonse.

Nayi momwe yankho lingawonekere. Kuti zinthu ziwonekere, timagwiritsa ntchito ntchito yosiyana kuwongolera kusaka kwa binary. Komanso kuchotsaIndex() ntchito, yomwe imabweza mtundu wa mndandanda kuchotsa index yomwe wapatsidwa.

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

Algorithm imayambira pa index [0]. Kenako imapanga mtundu wamagulu osaphatikizapo index yoyamba ndikugwiritsa ntchito kusaka kwa binary kuti muwone ngati zina mwazinthu zomwe zatsala zitha kuwonjezeredwa pamndandanda kuti mupange ndalama zomwe mukufuna. Izi zimachitika kamodzi pa chinthu chilichonse chomwe chili pamndandanda.

The for loop palokha idzakhala ndi nthawi yovuta ya O(N), koma mkati mwa loop timasakasaka, zomwe zimapereka nthawi yovuta ya O(Nlog(N)). Njira yothetsera vutoli ndi yabwino kuposa yapitayi, komabe pali malo oti musinthe.

Yankho 3: Linear Time

Kuvuta kwa nthawi: O(N).
Kuvuta kwa danga: O (1).

Tsopano tidzathetsa vutoli, kukumbukira kuti gululi lasanjidwa. Njira yothetsera vutoli ndikutenga manambala awiri: imodzi poyambira ndi ina kumapeto. Ngati zotsatira zikusiyana ndi zomwe zimafunikira, sinthani zoyambira ndi zomaliza.

Pamapeto pake tidzakumana ndi mtengo womwe tikufuna ndikubwerera zoona, kapena zoyambira ndi zomaliza zidzalumikizana ndikubwerera zabodza.

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

Tsopano zonse zili bwino, yankho likuwoneka ngati labwino. Koma ndani angatsimikizire kuti gululo lalamulidwa?

Nanga bwanji?

Poyang'ana koyamba, tikadangoyitanitsa mndandanda woyamba kenako ndikugwiritsa ntchito yankho pamwambapa. Koma kodi izi zidzakhudza bwanji nthawi ya kuphedwa?

Algorithm yabwino kwambiri ndikusintha mwachangu ndi nthawi yovuta O (Nlog (N)). Tikaigwiritsa ntchito munjira yathu yabwino, isintha magwiridwe ake kuchoka ku O(N) kupita ku O(Nlog(N)). Kodi ndizotheka kupeza yankho la mzere wokhala ndi gulu losayendetsedwa?

Solution 4

Kuvuta kwa nthawi: O(N).
Kuvuta kwa danga: O(N).

Inde, pali yankho la mzere; kuti tichite izi, tifunika kupanga mndandanda watsopano wokhala ndi mndandanda wamasewera omwe tikufuna. Kusinthanitsa apa ndikugwiritsa ntchito kukumbukira kwambiri: ndiye yankho lokhalo pamapepala lomwe lili ndi zovuta zambiri kuposa O (1).

Ngati mtengo woyamba wa gulu loperekedwa ndi 1 ndipo mtengo wofufuzira ndi 8, titha kuwonjezera mtengo wa 7 pamndandanda wa "mafunso ofufuzira".

Kenaka, pamene tikukonza chinthu chilichonse chamagulu, tikhoza kuyang'ana mndandanda wa "zofufuza" ndikuwona ngati chimodzi mwa izo chiri chofanana ndi mtengo wathu. Ngati inde, bwererani zoona.

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

Maziko a yankho ndi a loop, omwe, monga tawonera pamwambapa, ali ndi nthawi yovuta ya O (N).

Gawo lachiwiri lobwerezabwereza la ntchito yathu ndi Array.prototype.include(), njira ya JavaScript yomwe idzabwerenso zoona kapena zabodza kutengera ngati gululo lili ndi mtengo womwe wapatsidwa.

Kuti tidziwe nthawi yovuta ya Array.prototype.includes(), tikhoza kuyang'ana polyfill yoperekedwa ndi MDN (ndi yolembedwa mu JavaScript) kapena kugwiritsa ntchito njira mu code source ya injini ya JavaScript monga 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;
    }
  });
}

Apa gawo lobwerezabwereza la Array.prototype.include() ndilo lopu mu sitepe 7 yomwe (pafupifupi) imadutsa utali wonse wa mndandanda woperekedwa. Izi zikutanthauza kuti zovuta zake za nthawi ndizofanana. Chabwino, popeza nthawi zonse ndi sitepe imodzi kumbuyo kwa gulu lathu lalikulu, zovuta za nthawi ndi O (N + (N - 1)). Pogwiritsa ntchito Big O Notation, timaifewetsa kukhala O(N) - chifukwa ndi N yomwe imakhala ndi mphamvu yayikulu pakuwonjezera kukula kwake.

Pankhani yakuvuta kwa malo, gulu lina lowonjezera limafunikira lomwe kutalika kwake kumawonetsa gulu loyambirira (kuchotsa wamodzi, inde, koma izi zitha kunyalanyazidwa), zomwe zimapangitsa kuti O(N) ikhale yovuta. Chabwino, kugwiritsa ntchito kukumbukira kumapangitsa kuti ma algorithm azichita bwino.

Ndikukhulupirira kuti nkhaniyi ndi yothandiza ngati chowonjezera pazokambirana zanu zamakanema. Zimasonyeza kuti vuto losavuta likhoza kuthetsedwa m'njira zingapo zosiyana ndi zinthu zosiyanasiyana zomwe zimagwiritsidwa ntchito (nthawi, kukumbukira).

Skillbox imalimbikitsa:

Maphunzirowa amaperekedwa pa intaneti "Python Data Analyst".

Njira yapaintaneti "Professional frontend developer".

Maphunziro othandiza a chaka chimodzi "Wopanga PHP kuchokera ku 0 kupita ku PRO".

Source: www.habr.com

Kuthetsa vuto kuchokera ku kuyankhulana kwa Google mu JavaScript: 4 njira zosiyanasiyana

Kupanga kwa vuto

Nanga bwanji?

Kuwonjezera ndemanga kuletsa reply