ජාවාස්ක්‍රිප්ට් හි ගූගල් සම්මුඛ සාකච්ඡාවකින් ගැටලුවක් විසඳීම: විවිධ ක්‍රම 4 ක්

මම ඇල්ගොරිතම වල ක්‍රියාකාරිත්වය අධ්‍යයනය කරන විට, මට මෙය හමු විය මේ Google mock interview එකක වීඩියෝවක්.. එය විශාල තාක්‍ෂණ සමාගම්වල සම්මුඛ සාකච්ඡා පවත්වන ආකාරය පිළිබඳ අදහසක් ලබා දෙනවා පමණක් නොව, ඇල්ගොරිතම ගැටළු හැකි තරම් කාර්යක්ෂමව විසඳන්නේ කෙසේද යන්න තේරුම් ගැනීමට ද ඔබට ඉඩ සලසයි.

මෙම ලිපිය වීඩියෝ පටයට එක් ආකාරයක සහායකයකි. එහි මම පෙන්වා දී ඇති සියලුම විසඳුම් සහ ජාවාස්ක්‍රිප්ට් හි විසඳුමේ මගේම අනුවාදය පිළිබඳ අදහස් ලබා දෙමි. එක් එක් ඇල්ගොරිතමයේ සූක්ෂ්මතාවයන් ද සාකච්ඡා කෙරේ.

අපි ඔබට මතක් කරමු: "Habr" හි සියලුම පාඨකයින් සඳහා - "Habr" ප්‍රවර්ධන කේතය භාවිතයෙන් ඕනෑම Skillbox පාඨමාලාවකට ලියාපදිංචි වන විට රූබල් 10 ක වට්ටමක්.

Skillbox නිර්දේශ කරයි: ප්රායෝගික පාඨමාලාව "ජංගම සංවර්ධක PRO".

ගැටලුව ප්රකාශ කිරීම

අපට ඇණවුම් කළ අරාවක් සහ නිශ්චිත අගයක් ලබා දී ඇත. අරාවේ ඇති කිසියම් සංඛ්‍යා දෙකක එකතුවක් දී ඇති අගයකට සමාන විය හැකිද යන්න මත පදනම්ව සත්‍ය හෝ අසත්‍ය ලෙස ආපසු ලැබෙන ශ්‍රිතයක් සෑදීමට එය අසනු ලැබේ.

වෙනත් වචන වලින් කිවහොත්, අරාව තුළ නිඛිල දෙකක් තිබේද, x සහ y, එකට එකතු කළ විට නිශ්චිත අගයට සමාන වේ ද?

උදාහරණය A

අපට array එකක් [1, 2, 4, 9] ලබා දී එහි අගය 8 නම්, එම ශ්‍රිතය අසත්‍ය බවට හැරේ, මන්ද array හි ඇති කිසිදු සංඛ්‍යා දෙකකට 8 දක්වා එකතු කළ නොහැක.

උදාහරණය B

නමුත් එය අරාවක් [1, 2, 4, 4] නම් සහ අගය 8 නම්, 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).

arrays ඇණවුම් කර ඇති බැවින්, binary search භාවිතා කර විසඳුමක් සෙවිය හැක. ඇණවුම් කළ අරා සඳහා වඩාත්ම කාර්යක්ෂම ඇල්ගොරිතම මෙයයි. ද්විමය සෙවුමටම 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 loop එකටම O(N) හි රේඛීය කාල සංකීර්ණතාවයක් ඇත, නමුත් for loop එක තුල අපි ද්විමය සෙවුමක් සිදු කරන අතර එය O(Nlog(N)) හි සමස්ත කාල සංකීර්ණතාවයක් ලබා දෙයි. මෙම විසඳුම පෙර එකට වඩා හොඳයි, නමුත් වැඩිදියුණු කිරීම සඳහා තවමත් ඉඩ තිබේ.

විසඳුම 3: රේඛීය කාලය

කාල සංකීර්ණත්වය: O(N).
අභ්යවකාශ සංකීර්ණත්වය: O(1).

දැන් අපි ගැටලුව විසඳන්නෙමු, අරාව වර්ග කර ඇති බව මතක තබා ගන්න. විසඳුම වන්නේ අංක දෙකක් ගැනීමයි: එකක් ආරම්භයේ සහ අවසානයේ එකක්. ප්‍රති result ලය අවශ්‍ය ප්‍රමාණයට වඩා වෙනස් නම්, ආරම්භක සහ අවසන් ස්ථාන වෙනස් කරන්න.

අවසානයේ අපට අවශ්‍ය අගය හමු වී සත්‍ය ලබා දෙනු ඇත, නැතහොත් ආරම්භක සහ අවසාන ලක්ෂ්‍ය අභිසාරී වී අසත්‍ය ලෙස ලබා දෙනු ඇත.

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 ක්‍රමයකි.

Array.prototype.includes() හි කාල සංකීර්ණතාව සොයා ගැනීමට, අපට MDN (සහ JavaScript වලින් ලියා ඇති) විසින් සපයන ලද බහු පිරවුම දෙස බැලීමට හෝ Google V8 (C++) වැනි JavaScript එන්ජිමක ප්‍රභව කේතයේ ක්‍රමයක් භාවිතා කළ හැක.

// 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 නිර්දේශ කරයි:

• මාර්ගගත පාඨමාලාවට අයදුම් කර ඇත "පයිතන් දත්ත විශ්ලේෂක".
• මාර්ගගත පාඨමාලාව "වෘත්තීය ඉදිරිපස සංවර්ධක".
• ප්‍රායෝගික වසර පාඨමාලාව "0 සිට PRO දක්වා PHP සංවර්ධකයා".

මූලාශ්රය: www.habr.com