Google-ի հարցազրույցից խնդրի լուծում JavaScript-ով. 4 տարբեր եղանակներ

Երբ ես ուսումնասիրում էի ալգորիթմների աշխատանքը, հանդիպեցի սրան սա Google-ի մոդելային հարցազրույցի տեսանյութ էԱյն ոչ միայն պատկերացում է տալիս, թե ինչպես են հարցազրույցները անցկացվում խոշոր տեխնոլոգիական կորպորացիաներում, այլև թույլ է տալիս հասկանալ, թե ինչպես են լուծվում ալգորիթմական խնդիրները, և ամենաարդյունավետ ձևով։

Այս հոդվածը տեսանյութին կից յուրատեսակ լրացում է։ Այնտեղ ես մեկնաբանություններ եմ տալիս ներկայացված բոլոր լուծումների, գումարած JavaScript-ով լուծման իմ սեփական տարբերակի վերաբերյալ։ Քննարկվում են նաև յուրաքանչյուր ալգորիթմի նրբությունները։

Հիշեցում. «Habr»-ի բոլոր ընթերցողների համար՝ 10 ռուբլի զեղչ «Habr» գովազդային կոդով Skillbox-ի ցանկացած դասընթացին գրանցվելիս:

Skillbox-ը խորհուրդ է տալիս. Գործնական դասընթաց «Mobile Developer PRO».

Խնդրի ձևակերպում

Մեզ տրվում է կարգավորված զանգված և որոշակի արժեք։ Այնուհետև մեզ խնդրվում է ստեղծել մի ֆունկցիա, որը կվերադարձնի true կամ false՝ կախված նրանից, թե զանգվածում ցանկացած երկու թվերի գումարը կարող է հավասար լինել տրված արժեքին, թե ոչ։

Այլ կերպ ասած, զանգվածում կա՞ն երկու ամբողջ թվեր՝ x և y, որոնք գումարելիս հավասար են նշված արժեքին։

Օրինակ Ա

Եթե ​​մեզ տրված է [1, 2, 4, 9] զանգվածը և 8 արժեքը, ֆունկցիան կվերադարձնի false, քանի որ զանգվածում ոչ մի երկու թիվ չի կարող գումարվել 8-ի։

Օրինակ Բ

Բայց եթե դա զանգված է [1, 2, 4, 4] և արժեքը 8 է, ֆունկցիան պետք է վերադարձնի true, քանի որ 4 + 4 = 8։

Լուծում 1. Բռնի ուժ

Ժամանակային բարդություն՝ O(N²):
Տարածության բարդությունը՝ O(1):

Ամենաակնհայտ իմաստը ներդրված օղակների զույգի օգտագործումն է։

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

Այս լուծումը արդյունավետ չէ, քանի որ այն ստուգում է զանգվածի երկու տարրերի բոլոր հնարավոր գումարները, ինչպես նաև համեմատում է ինդեքսների յուրաքանչյուր զույգը երկու անգամ։ (Օրինակ, երբ i = 1 և j = 2 է, սա գործնականում նույնն է, ինչ համեմատել i = 2 և j = 1 դեպքում, բայց այս լուծման մեջ մենք փորձում ենք երկու տարբերակներն էլ):

Քանի որ մեր լուծումը օգտագործում է ներդրված for ցիկլերի զույգ, այն քառակուսային է՝ O(N²) ժամանակային բարդությամբ։

Լուծում 2. Երկուական որոնում

Ժամանակային բարդություն՝ O(Nlog(N)):
Տարածության բարդությունը՝ O(1).

Քանի որ զանգվածները դասավորված են, մենք կարող ենք լուծում փնտրել՝ օգտագործելով երկուական որոնում: Սա դասավորված զանգվածների համար ամենաարդյունավետ ալգորիթմն է: Երկուական որոնումն ինքնին ունի O(log(N)) աշխատանքային ժամանակ: Այնուամենայնիվ, մենք դեռ պետք է օգտագործենք for ցիկլ՝ յուրաքանչյուր տարրը մյուս բոլոր արժեքների համեմատ ստուգելու համար:

Ահա թե ինչ տեսք կարող է ունենալ լուծումը։ Որպեսզի ամեն ինչ ավելի պարզ լինի, մենք օգտագործում ենք առանձին ֆունկցիա՝ երկուական որոնումը կառավարելու համար։ Եվ removeIndex() ֆունկցիա, որը վերադարձնում է զանգվածի տարբերակը՝ հանած տրված ինդեքսը։

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

Ալգորիթմը սկսվում է [0] ինդեքսից։ Այնուհետև այն ստեղծում է զանգվածի մի տարբերակ՝ բացառելով առաջին ինդեքսը, և օգտագործում է երկուական որոնում՝ տեսնելու համար, թե արդյոք մնացած արժեքներից որևէ մեկը կարող է ավելացվել զանգվածին՝ ցանկալի գումարը ստանալու համար։ Սա արվում է մեկ անգամ զանգվածի յուրաքանչյուր տարրի համար։

for ցիկլն ինքնին կունենա O(N) գծային ժամանակային բարդություն, բայց for ցիկլի ներսում մենք կատարում ենք երկուական որոնում, որը տալիս է O(Nlog(N)) ընդհանուր ժամանակային բարդություն։ Այս լուծումն ավելի լավն է, քան նախորդը, բայց դեռ կա կատարելագործման տեղ։

Լուծում 3. Գծային ժամանակ

Ժամանակային բարդություն՝ O(N):
Տարածության բարդությունը՝ O(1):

Հիմա մենք կլուծենք խնդիրը՝ հիշելով, որ զանգվածը տեսակավորված է։ Լուծումը երկու թիվ վերցնելն է՝ մեկը սկզբում, մյուսը՝ վերջում։ Եթե արդյունքը տարբերվում է պահանջվողից, ապա մենք փոխում ենք սկզբնական և վերջավոր կետերը։

Ի վերջո մենք կամ կհանդիպենք ցանկալի արժեքին և կվերադարձնենք true, կամ սկզբնական և վերջնակետերը կզուգամիտեն և կվերադարձնեն 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;
};

Հիմա ամեն ինչ լավ է, լուծումը, կարծես, օպտիմալ է։ Բայց ո՞վ կերաշխավորի, որ զանգվածը պատվիրված է։

Ուրեմն ինչ?

Առաջին հայացքից, մենք կարող էինք պարզապես նախ տեսակավորել զանգվածը, ապա օգտագործել վերևում նշված լուծումը։ Բայց ինչպե՞ս դա կազդի կատարման ժամանակի վրա։

Լավագույն ալգորիթմը արագ տեսակավորումն է՝ ժամանակային բարդությամբ O(Nlog(N)): Եթե մենք այն օգտագործենք մեր օպտիմալ լուծման մեջ, այն կփոխի իր կատարողականությունը O(N)-ից մինչև O(Nlog(N)): Հնարավո՞ր է գտնել գծային լուծում՝ չդասակարգված զանգվածով:

4 լուծում

Ժամանակային բարդություն՝ O(N):
Տարածության բարդությունը՝ O(N):

Այո, կա գծային լուծում, որը պահանջում է ստեղծել նոր զանգված, որը պարունակում է մեր որոնած համընկնումների ցանկը։ Այստեղ փոխզիջումն այն է, որ այն ավելի շատ հիշողություն է պահանջում. սա հոդվածում միակ լուծումն է, որի տարածական բարդությունը մեծ է O(1)-ից։

Եթե ​​տրված զանգվածի առաջին արժեքը 1 է, իսկ որոնման արժեքը՝ 8, մենք կարող ենք 7 արժեքը ավելացնել «որոնման արժեքներ» զանգվածին։

Այնուհետև, զանգվածի յուրաքանչյուր տարրը մշակելիս, կարող ենք ստուգել «որոնման արժեքների» զանգվածը և տեսնել, թե արդյոք դրանցից մեկը հավասար է մեր արժեքին։ Եթե այո, ապա վերադարձնում ենք 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;
};

Լուծման միջուկը for ցիկլն է, որը, ինչպես տեսանք վերևում, ունի O(N) գծային ժամանակային բարդություն։

Մեր ֆունկցիայի երկրորդ իտերացիոն մասը Array.prototype.include()-ն է, որը JavaScript մեթոդ է, որը կվերադարձնի true կամ false՝ կախված նրանից, թե զանգվածը պարունակում է տրված արժեքը, թե ոչ։

Array.prototype.includes()-ի ժամանակային բարդությունը պարզելու համար կարող ենք դիտարկել MDN-ի կողմից տրամադրված (և JavaScript-ով գրված) polyfill-ը կամ օգտագործել մեթոդը JavaScript շարժիչի, ինչպիսին է 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;
    }
  });
}

Այստեղ Array.prototype.include() ֆունկցիայի իտերացիոն մասը 7-րդ քայլում գտնվող while ցիկլն է, որը (գրեթե) հատում է տրված զանգվածի ամբողջ երկարությունը։ Սա նշանակում է, որ դրա ժամանակային բարդությունը նույնպես գծային է։ Եվ քանի որ այն միշտ մեկ քայլով հետ է մնում մեր հիմնական զանգվածից, ժամանակային բարդությունը O(N + (N - 1)) է։ Օգտագործելով Big O նշագրությունը, մենք սա պարզեցնում ենք O(N)-ի, քանի որ N-ն ամենամեծ ազդեցությունն ունի մուտքային չափի մեծացմանը զուգընթաց։

Ինչ վերաբերում է տարածական բարդությանը, ապա անհրաժեշտ է լրացուցիչ զանգված, որի երկարությունը արտացոլում է սկզբնական զանգվածը (հանած մեկը, այո, բայց սա կարելի է անտեսել), ինչը հանգեցնում է O(N) տարածական բարդության։ Իսկ հիշողության օգտագործման ավելացումը ապահովում է ալգորիթմի առավելագույն արդյունավետությունը։

Հուսով եմ՝ այս հոդվածը օգտակար կլինի ձեզ համար որպես տեսազրույցի լրացում։ Այն ցույց է տալիս, որ պարզ խնդիրը կարելի է լուծել մի քանի տարբեր եղանակներով՝ տարբեր քանակությամբ ռեսուրսներով (ժամանակ, հիշողություն)։

Skillbox-ը խորհուրդ է տալիս.

• Կիրառական առցանց դասընթաց «Python Data Analyst».
• Առցանց դասընթաց «Մասնագիտություն ֆրոնտենդ ծրագրավորող».
• Գործնական տարվա դասընթաց «PHP ծրագրավորող 0-ից մինչև PRO».

Source: www.habr.com