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

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

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-ի հետ, բայց այս լուծումում մենք փորձում ենք երկու տարբերակները):

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


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

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

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

Ահա թե ինչպիսին կարող է լինել լուծումը. Ամեն ինչ պարզ դարձնելու համար մենք օգտագործում ենք առանձին ֆունկցիա՝ երկուական որոնումը վերահսկելու համար: Եվ նաև 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 արժեքը «որոնման արժեքներ» զանգվածին։

Այնուհետև, երբ մենք մշակում ենք զանգվածի յուրաքանչյուր տարր, մենք կարող ենք ստուգել «որոնման արժեքների» զանգվածը և տեսնել, թե արդյոք դրանցից մեկը հավասար է մեր արժեքին: Եթե ​​այո, վերադարձրեք ճշմարիտ:

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 loop-ն է, որը, ինչպես տեսանք վերևում, ունի O(N) գծային ժամանակային բարդություն։

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

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

Source: www.habr.com

Добавить комментарий