Problēmas atrisināšana no Google intervijas JavaScript: 4 dažādi veidi

Kad es pētīju algoritmu veiktspēju, es saskāros ar to Šis ir Google izspēles intervijas video.. Tas ne tikai sniedz priekšstatu par to, kā notiek intervijas lielajās tehnoloģiju korporācijās, bet arī ļauj saprast, kā pēc iespējas efektīvāk tiek risinātas algoritmiskās problēmas.

Šis raksts ir sava veida video pavadījums. Tajā es sniedzu komentārus par visiem parādītajiem risinājumiem, kā arī savu risinājuma versiju JavaScript. Tiek apspriestas arī katra algoritma nianses.

Atgādinām: visiem "Habr" lasītājiem - atlaide 10 000 rubļu, reģistrējoties jebkurā Skillbox kursā, izmantojot "Habr" reklāmas kodu.

Skillbox iesaka: Praktiskais kurss "Mobile Developer PRO".

Problēmas paziņojums

Mums tiek dots sakārtots masīvs un noteikta vērtība. Pēc tam tiek lūgts izveidot funkciju, kas atgriež patiesu vai nepatiesu atkarībā no tā, vai jebkuru divu skaitļu summa masīvā var būt vienāda ar doto vērtību.

Citiem vārdiem sakot, vai masīvā ir divi veseli skaitļi, x un y, kas, saskaitot kopā, ir vienādi ar norādīto vērtību?

Piemērs A

Ja mums tiek dots masīvs [1, 2, 4, 9] un vērtība ir 8, funkcija atgriezīs nepatiesu, jo neviens masīvs nevar pievienot 8.

B piemērs

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

1. risinājums: brutāls spēks

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

Acīmredzamākā nozīme ir izmantot ligzdotu cilpu pāri.

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

Šis risinājums nav efektīvs, jo pārbauda katru iespējamo divu elementu summu masīvā un arī salīdzina katru indeksu pāri divas reizes. (Piemēram, ja i = 1 un j = 2 patiesībā ir tas pats, kas salīdzināt ar i = 2 un j = 1, bet šajā risinājumā mēs izmēģinām abas iespējas).

Tā kā mūsu risinājumā tiek izmantots pāris ligzdotas cilpas, tas ir kvadrātveida ar O(N²) laika sarežģītību.

2. risinājums: binārā meklēšana

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

Tā kā masīvi ir sakārtoti, mēs varam meklēt risinājumu, izmantojot bināro meklēšanu. Šis ir visefektīvākais algoritms sakārtotiem masīviem. Binārās meklēšanas darbības laiks ir O(log(N)). Tomēr jums joprojām ir jāizmanto for cilpa, lai pārbaudītu katru elementu pret visām pārējām vērtībām.

Lūk, kā varētu izskatīties risinājums. Lai lietas būtu skaidras, mēs izmantojam atsevišķu funkciju, lai kontrolētu bināro meklēšanu. Un arī funkcija removeIndex(), kas atgriež masīva versiju mīnus doto indeksu.

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

Algoritms sākas ar indeksu [0]. Pēc tam tiek izveidota masīva versija, izņemot pirmo indeksu, un tiek izmantota binārā meklēšana, lai noskaidrotu, vai masīvam 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 masīva elementam.

Pašai for cilpai būs lineārā laika sarežģītība O(N), bet for cilpas iekšpusē mēs veicam bināro meklēšanu, kas nodrošina kopējo laika sarežģītību O(Nlog(N)). Šis risinājums ir labāks par iepriekšējo, taču vēl ir ko uzlabot.

3. risinājums: lineārais laiks

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

Tagad mēs atrisināsim problēmu, atceroties, ka masīvs ir sakārtots. Risinājums ir ņemt divus skaitļus: vienu sākumā un vienu beigās. Ja rezultāts atšķiras no nepieciešamā, mainiet sākuma un beigu punktu.

Galu galā mēs vai nu sastapsim vēlamo vērtību un atgriezīsimies ar patiesu vērtību, vai arī sākuma un beigu punkti saplūdīs un atgriezīsies false.

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

Tagad viss ir kārtībā, risinājums šķiet optimāls. Bet kurš var garantēt, ka masīvs tika pasūtīts?

Ko tad?

No pirmā acu uzmetiena mēs varējām vienkārši pasūtīt masīvu un pēc tam izmantot iepriekš minēto risinājumu. Bet kā tas ietekmēs izpildes laiku?

Labākais algoritms ir ātrā kārtošana ar laika sarežģītību O (Nlog (N)). Ja mēs to izmantosim mūsu optimālajā risinājumā, tas mainīs tā veiktspēju no O(N) uz O(Nlog(N)). Vai ir iespējams atrast lineāru risinājumu ar nesakārtotu masīvu?

4 risinājums

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

Jā, ir lineārs risinājums; lai to izdarītu, mums ir jāizveido jauns masīvs, kurā ir ietverts meklēto atbilstības saraksts. Kompromiss šeit ir lielāks atmiņas lietojums: tas ir vienīgais risinājums dokumentā, kura telpas sarežģītība ir lielāka par O(1).

Ja dotā masīva pirmā vērtība ir 1 un meklēšanas vērtība ir 8, mēs varam pievienot vērtību 7 masīvam "meklēšanas vērtības".

Pēc tam, apstrādājot katru masīva elementu, mēs varam pārbaudīt “meklēšanas vērtību” masīvu un noskaidrot, vai kāds no tiem ir vienāds ar mūsu vērtību. Ja jā, atgrieziet patieso.

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 pamatā ir for cilpa, kurai, kā redzējām iepriekš, ir O(N) lineārā laika sarežģītība.

Otrā mūsu funkcijas iteratīvā daļa ir Array.prototype.include(), JavaScript metode, kas atgriezīs patiesu vai nepatiesu atkarībā no tā, vai masīvā ir norādītā vērtība.

Lai noskaidrotu Array.prototype.includes() laika sarežģītību, mēs varam aplūkot MDN nodrošināto polifill (un rakstīts JavaScript valodā) vai izmantot metodi JavaScript dzinēja avota kodā, 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 cilpa 7. darbībā, kas (gandrīz) šķērso visu dotā masīva garumu. Tas nozīmē, ka arī tā laika sarežģītība ir lineāra. Tā kā tas vienmēr ir vienu soli aiz mūsu galvenā masīva, laika sarežģītība ir O (N + (N - 1)). Izmantojot lielo O apzīmējumu, mēs to vienkāršojam līdz O(N), jo tieši N ir vislielākā ietekme, palielinot ievades lielumu.

Attiecībā uz telpisko sarežģītību ir nepieciešams papildu masīvs, kura garums atspoguļo sākotnējo masīvu (mīnus viens, jā, bet to var ignorēt), kā rezultātā rodas O(N) telpiskā sarežģītība. Palielināts atmiņas lietojums nodrošina maksimālu algoritma efektivitāti.

Ceru, ka raksts jums noderēs kā papildinājums video intervijai. Tas parāda, ka vienkāršu problēmu var atrisināt vairākos dažādos veidos, izmantojot dažādus resursu (laika, atmiņas) apjomu.

Skillbox iesaka:

• Lietišķais tiešsaistes kurss "Python datu analītiķis".
• Tiešsaistes kurss "Profesijas priekšgala izstrādātājs".
• Praktiskā gada kurss "PHP izstrādātājs no 0 līdz PRO".

Avots: www.habr.com