Risinām Google intervijas uzdevumu JavaScript: 4 dažādi veidi

Risinām Google intervijas uzdevumu JavaScript: 4 dažādi veidi

Kad es studēju algoritmu veiktspēju, es sastapu šo video par Google simulāciju. Tas ne tikai sniedz priekšstatu par to, kā notiek intervijas lielās tehnoloģiju korporācijās, bet arī palīdz saprast, kā tiek risināti algoritmiskie uzdevumi, un to iespējami efektīvāk.

Šis raksts ir savdabīgs papildinājums video. Tajā sniedzu komentārus par visiem rādītajiem risinājumiem, kā arī savu risinājumu JavaScript. Tiek apspriestas katra algoritma nianses.

Atgādinām: visiem «Habr» lasītājiem — atlaide 10 000 rubļu reģistrējoties jebkurā Skillbox kursā ar promo kodu «Habr».

Skillbox iesaka: Praktiskais kurss «Mobilais izstrādātājs PRO».

Uzdevuma formulēšana

Mums tiek doti šķirots masīvs un noteikta vērtība. Pēc tam tiek lūgts izveidot funkciju, kas atgriež true vai false, atkarībā no tā, vai divu skaitļu summa masīvā var būt vienāda ar norādīto vērtību.

Citiem vārdiem sakot, vai masīvā ir divi veselie skaitļi x un y, kuru summa ir vienāda ar norādīto vērtību?

Piemērs A

Ja mums ir masīvā [1, 2, 4, 9] un vērtība 8, funkcija atgriezīs false, jo divu skaitļu summa no masīva nevar dot 8.

Piemērs B

Bet, ja tas ir masīvs [1, 2, 4, 4] un vērtība 8, funkcijai jāatgriež true, jo 4 + 4 = 8.

Risinājums 1. Brutāla spēka metode

Laika sarežģītība: O(N²).
Telpas sarežģītība: O(1).

Acīmredzamā vērtība ir izmantot pāra ieliktus ciklus.

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

Šo risinājumu nevar uzskatīt par efektīvu, jo tas pārbauda katru iespējamo divu elementu summu masīvā, kā arī salīdzina katru indeksu pāri divreiz. (Piemēram, kad i = 1 un j = 2 — tas būtībā ir tas pats, kas salīdzināt ar i = 2 un j = 1, taču šajā risinājumā mēs pārbaudām abus variantus).

Tā kā mūsu risinājums izmanto pāra ieliktus for ciklus, tas ir kvadrātisks ar laika sarežģītību O(N²).


Risinājums 2. Binārā meklēšana

Laika sarežģītība: O(Nlog(N)).
Telpas sarežģītība: O(1)
.

Tā kā masīvi ir šķiroti, mēs varam meklēt risinājumu, izmantojot bināro meklēšanu. Tas ir visefektīvākais algoritms šķirotiem masīviem. Pats par sevi binārajai meklēšanai ir izpildes laiks O(log(N)). Tomēr joprojām ir nepieciešams izmantot for ciklu, lai pārbaudītu katru elementu attiecībā pret visām citām vērtībām.

Tā varētu izskatīties risinājums. Lai viss būtu skaidrs, mēs izmantojam atsevišķu funkciju binārās meklēšanas kontrolei. Tāpat izmantojam funkciju removeIndex(), kas atgriež masīva versiju, izņemot norādīto indeksu.

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

Algoritms sākas ar indeksu [0]. Pēc tam tas izveido masīva versiju, izņemot pirmo indeksu, un izmanto bināro meklēšanu, lai pārbaudītu, vai pie masīva var pievienot kādu no atlikušajām vērtībām, lai iegūtu vēlamo summu. Šī darbība tiek veikta vienu reizi katram elementam masīvā.

Pats par sevi for cikls radīs lineāro laika sarežģītību O(N), bet cikla iekšienē mēs veicam bināro meklēšanu, kas dod kopējo laika sarežģītību O(N log(N)). Šis risinājums ir labāks par iepriekšējo, bet vēl ir, ko uzlabot.


Risinājums 3. Lineārs laiks

Laika sarežģītība: O(N).
Telpas sarežģītība: O(1).

Tagad mēs atrisināsim uzdevumu, atceroties, ka masīvs ir sakārtots. Risinājums ir ņemt divus skaitļus: vienu sākumā un otru beigās. Ja rezultāts atšķiras no prasītā, tad mēs mainām sākuma un beigu punktu.

Galu galā mēs vai nu sastapsim vēlamo vērtību un atgriezīsim true, vai arī sākuma un beigu punkti saskarsies un atgriezīs 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;
};


Tagad viss ir labi, risinājums šķiet optimāls. Bet kas garantēs, ka masīvs bija kārtots?

Ko tad?

Pirmā acu uzmetiena, mēs varētu vispirms vienkārši sakārtot masīvu un pēc tam izmantot iepriekšējo risinājumu. Bet kā tas ietekmēs izpildes laiku?

Labākais algoritms ir ātrā kārtošana ar laika sarežģītību O(N log(N)). Ja mēs to izmantojam savā optimālajā risinājumā, tā veiktspēja mainīsies no O(N) uz O(N log(N)). Vai ir iespējams atrast lineāru risinājumu ar sakārtotu masīvu?

Risinājums 4

Laika sarežģītība: O(N).
Telpas sarežģītība: O(N).

Jā, lineārs risinājums eksistē; lai to iegūtu, ir jāizveido jauns masīvs, kas satur meklējamo sakritību sarakstu. Kompromiss šeit ir aktīvāka atmiņas izmantošana: tas ir vienīgais risinājums rakstā ar telpisko sarežģītību, kas pārsniedz O (1).

Ja šī masīva pirmais elements ir 1, un meklētais elements ir 8, mēs varam pievienot vērtību 7 meklēto vērtību masīvam.

Pēc tam, apstrādājot katru masīva elementu, varam pārbaudīt meklēto vērtību masīvu un redzēt, vai kāds no tiem ir vienāds ar mūsu vērtību. Ja jā, atgriežam 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;
};

Risinājuma pamats ir for cikls, kas, kā mēs jau iepriekš redzējām, ir lineārs laika sarežģītības līmenī O (N).

Otrā mūsu funkcijas iteratīvā daļa ir Array.prototype.include (), JavaScript metode, kas atgriezīs true vai false atkarībā no tā, vai masīvs satur noteikto vērtību.

Lai uzzinātu Array.prototype.includes () laika sarežģītību, mēs varam aplūkot polyfill, ko nodrošina MDN (un kas rakstīts JavaScript), vai izmantot metodi no JavaScript dzinēja avota koda, piemēram, 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;
    }
  });
}

Šeit Array.prototype.include () iteratīvā daļa ir while cikls 7. solī, kas (gandrīz) šķērso visu dotā masīva garumu. Tas nozīmē, ka tā laika sarežģītība ir arī lineāra. Tā kā tā vienmēr ir par vienu soli aiz mūsu pamatmasīva, tā laika sarežģītība ir O (N + (N — 1)). Izmantojot Big O notation, mēs to vienkāršojam līdz O (N) — jo tieši N ir vislielākā ietekme, pieaugot ievades lielumam.

Attiecībā uz telpisko sarežģītību ir nepieciešams papildus masīvs, kura garums atspoguļo sākotnējo masīvu (minus viens, jā, bet to var ignorēt), kas noved pie telpiskās sarežģītības O (N). Palielināta atmiņas izmantošana nodrošina maksimālu algoritma efektivitāti.


Ceru, ka šis raksts jums būs noderīgs kā pielikums video intervijai. Tas parāda, ka vienkāršu uzdevumu var risināt vairākiem dažādiem veidiem ar atšķirīgu izmantoto resursu (laika, atmiņas) apjomu.

Skillbox iesaka:

Avots: habr.com

Iegādājieties uzticamu tīmekļa hostingu ar DDoS aizsardzību, VPS VDS serveriem 🔥 Iegādājieties uzticamu tīmekļa hostingu ar DDoS aizsardzību, VPS VDS serveriem | ProHoster