জাভাস্ক্রিপ্টে একটি গুগল ইন্টারভিউ থেকে সমস্যা সমাধান করা: 4টি ভিন্ন উপায়

যখন আমি অ্যালগরিদমের কর্মক্ষমতা অধ্যয়ন করছিলাম, তখন আমি এটি জুড়ে এসেছি এটি একটি গুগল মক সাক্ষাৎকারের একটি ভিডিও।. এটি কেবল বড় প্রযুক্তি কর্পোরেশনগুলিতে কীভাবে সাক্ষাত্কার নেওয়া হয় তার একটি ধারণা দেয় না, তবে আপনাকে কীভাবে অ্যালগরিদমিক সমস্যাগুলি যতটা সম্ভব দক্ষতার সাথে সমাধান করা হয় তা বোঝার অনুমতি দেয়।

এই নিবন্ধটি ভিডিওটির এক ধরণের অনুষঙ্গ। এটিতে আমি দেখানো সমস্ত সমাধানের উপর মন্তব্য প্রদান করি, এবং জাভাস্ক্রিপ্টে সমাধানের আমার নিজস্ব সংস্করণ। প্রতিটি অ্যালগরিদমের সূক্ষ্মতাও আলোচনা করা হয়েছে।

আমরা মনে করিয়ে দিচ্ছি: "Habr"-এর সকল পাঠকদের জন্য - "Habr" প্রচারমূলক কোড ব্যবহার করে যেকোনো Skillbox কোর্সে নথিভুক্ত করার সময় 10 রুবেল ছাড়।

Skillbox সুপারিশ করে: ব্যবহারিক কোর্স "মোবাইল ডেভেলপার প্রো".

সমস্যা গঠন

আমাদের একটি অর্ডারকৃত অ্যারে এবং একটি নির্দিষ্ট মান দেওয়া হয়। তারপরে এটিকে একটি ফাংশন তৈরি করতে বলা হয় যা সত্য বা মিথ্যা ফেরত দেয় অ্যারের যেকোনো দুটি সংখ্যার যোগফল একটি প্রদত্ত মানের সমান হতে পারে কিনা তার উপর নির্ভর করে।

অন্য কথায়, অ্যারেতে কি দুটি পূর্ণসংখ্যা আছে, x এবং y, যেগুলি একসাথে যোগ করলে নির্দিষ্ট মান সমান হয়?

উদাহরণ A

যদি আমাদের একটি অ্যারে [1, 2, 4, 9] দেওয়া হয় এবং মান 8 হয়, তাহলে ফাংশনটি মিথ্যা ফেরত দেবে কারণ অ্যারেতে দুটি সংখ্যা 8 পর্যন্ত যোগ করতে পারে না।

উদাহরণ বি

কিন্তু যদি এটি একটি অ্যারে [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).

যেহেতু অ্যারেগুলি অর্ডার করা হয়েছে, আমরা বাইনারি অনুসন্ধান ব্যবহার করে একটি সমাধান অনুসন্ধান করতে পারি। অর্ডার করা অ্যারেগুলির জন্য এটি সবচেয়ে কার্যকর অ্যালগরিদম। বাইনারি অনুসন্ধানের একটি চলমান সময় রয়েছে O(log(N))। যাইহোক, আপনাকে এখনও অন্য সমস্ত মানের বিপরীতে প্রতিটি উপাদান পরীক্ষা করার জন্য একটি লুপ ব্যবহার করতে হবে।

একটি সমাধান দেখতে কেমন হতে পারে তা এখানে। জিনিসগুলি পরিষ্কার করার জন্য, আমরা বাইনারি অনুসন্ধান নিয়ন্ত্রণ করতে একটি পৃথক ফাংশন ব্যবহার করি। এবং এছাড়াও 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]। এটি তারপরে প্রথম সূচকটি বাদ দিয়ে অ্যারের একটি সংস্করণ তৈরি করে এবং বাইনারি অনুসন্ধান ব্যবহার করে দেখতে পারে যে পছন্দসই যোগফল তৈরি করতে অ্যারেতে অবশিষ্ট মানগুলি যোগ করা যেতে পারে কিনা। এই ক্রিয়াটি অ্যারের প্রতিটি উপাদানের জন্য একবার সঞ্চালিত হয়।

ফর লুপের মধ্যেই O(N) এর একটি রৈখিক সময়ের জটিলতা থাকবে, কিন্তু লুপের ভিতরে আমরা একটি বাইনারি অনুসন্ধান করি, যা O(Nlog(N)) এর সামগ্রিক সময়ের জটিলতা দেয়। এই সমাধানটি আগেরটির চেয়ে ভাল, তবে উন্নতির জন্য এখনও জায়গা রয়েছে।

সমাধান 3: রৈখিক সময়

সময়ের জটিলতা: O(N)।
স্থান জটিলতা: O(1)।

এখন আমরা সমস্যাটি সমাধান করব, মনে রাখবেন যে অ্যারেটি সাজানো হয়েছে। সমাধান হল দুটি সংখ্যা নিতে হবে: একটি শুরুতে এবং একটি শেষে। যদি ফলাফলটি প্রয়োজনীয় থেকে ভিন্ন হয়, তাহলে শুরু এবং শেষ বিন্দু পরিবর্তন করুন।

অবশেষে আমরা হয় কাঙ্খিত মান সম্মুখীন হব এবং সত্য ফিরে আসবে, অথবা শুরু এবং শেষ বিন্দু একত্রিত হবে এবং মিথ্যা ফিরে আসবে।

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)) এ পরিবর্তন করবে। এটি একটি unordered অ্যারের সঙ্গে একটি রৈখিক সমাধান খুঁজে বের করা সম্ভব?

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

সমাধানের ভিত্তি হল একটি লুপ, যা আমরা উপরে দেখেছি, O(N) এর একটি রৈখিক সময় জটিলতা রয়েছে।

আমাদের ফাংশনের দ্বিতীয় পুনরাবৃত্ত অংশটি হল Array.prototype.include(), একটি জাভাস্ক্রিপ্ট পদ্ধতি যা সত্য বা মিথ্যা ফেরত দেবে তার উপর নির্ভর করে যে অ্যারে প্রদত্ত মান রয়েছে।

Array.prototype.includes() এর সময় জটিলতা বের করার জন্য, আমরা MDN দ্বারা প্রদত্ত পলিফিল দেখতে পারি (এবং জাভাস্ক্রিপ্টে লেখা) অথবা একটি 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))। বিগ ও নোটেশন ব্যবহার করে, আমরা এটিকে O(N)-তে সরল করি - কারণ ইনপুট আকার বাড়ানোর সময় এটি N এর সবচেয়ে বেশি প্রভাব পড়ে।

স্থানিক জটিলতা সম্পর্কে, একটি অতিরিক্ত অ্যারের প্রয়োজন যার দৈর্ঘ্য মূল অ্যারের প্রতিফলন করে (মাইনাস ওয়ান, হ্যাঁ, তবে এটি উপেক্ষা করা যেতে পারে), যার ফলে O(N) স্থানিক জটিলতা হয়। ভাল, বর্ধিত মেমরি ব্যবহার অ্যালগরিদমের সর্বাধিক দক্ষতা নিশ্চিত করে।

আমি আশা করি আপনি নিবন্ধটি আপনার ভিডিও সাক্ষাৎকারের পরিপূরক হিসাবে দরকারী বলে মনে করেন। এটি দেখায় যে একটি সাধারণ সমস্যা বিভিন্ন পরিমাণে ব্যবহৃত সম্পদ (সময়, স্মৃতি) দিয়ে বিভিন্ন উপায়ে সমাধান করা যেতে পারে।

Skillbox সুপারিশ করে:

• অনলাইন কোর্সের আবেদন করা হয়েছে "পাইথন ডেটা বিশ্লেষক".
• অনলাইন কোর্স "পেশা ফ্রন্টএন্ড ডেভেলপার".
• ব্যবহারিক বছরের কোর্স "0 থেকে PRO পর্যন্ত পিএইচপি বিকাশকারী".

উত্স: www.habr.com