جاوا اسڪرپٽ ۾ گوگل انٽرويو جو مسئلو حل ڪرڻ: 4 مختلف طريقا

جڏهن آئون الگورتھم جي ڪارڪردگي جو مطالعو ڪري رهيو هوس، مون کي هن ۾ آيو هي هڪ گوگل موڪ انٽرويو جي وڊيو آهي.. اهو نه رڳو اهو خيال ڏئي ٿو ته انٽرويو ڪيئن وڏي ٽيڪنالاجي ڪارپوريشنن تي منعقد ڪيا ويا آهن، پر توهان کي اهو سمجهڻ جي اجازت ڏئي ٿو ته ڪيئن الورورٿمڪ مسئلن کي ممڪن طور تي موثر طريقي سان حل ڪيو وڃي.

هي آرٽيڪل هڪ قسم جي وڊيو سان گڏ آهي. ان ۾ مان ڏيکاريل سڀني حلن تي تبصرا ڏيان ٿو، ۽ جاوا اسڪرپٽ ۾ حل جو منهنجو پنهنجو ورزن. هر الگورتھم جي nuances تي به بحث ڪيو ويو آهي.

اسان توهان کي ياد ڏياريون ٿا: "Habr" جي سڀني پڙهندڙن لاءِ - 10 روبل جي رعايت جڏهن "Habr" پروموشنل ڪوڊ استعمال ڪندي ڪنهن به اسڪل باڪس ڪورس ۾ داخلا.

Skillbox سفارش ڪري ٿو: عملي ڪورس "موبائل ڊولپر پرو".

مسئلو جي ترتيب

اسان کي هڪ ترتيب ڏنل صف ۽ هڪ مخصوص قدر ڏنو ويو آهي. ان کان پوء هڪ فنڪشن ٺاهڻ لاء چيو ويندو آهي جيڪو صحيح يا غلط واپسي تي منحصر ڪري ٿو ته ڇا صف ۾ ڪنهن به ٻن انگن جو مجموعو ڏنل قدر جي برابر ٿي سگهي ٿو.

ٻين لفظن ۾، ڇا صف ۾ ٻه عدد آهن، x ۽ y، جن کي گڏ ڪيو وڃي ته مقرر ڪيل قدر جي برابر؟

مثال A

جيڪڏهن اسان کي هڪ آري ڏني وئي آهي [1، 2، 4، 9] ۽ قيمت 8 آهي، فنڪشن غلط موٽندو ڇو ته ايري ۾ ٻه نمبر 8 تائين شامل نه ٿي سگهن.

مثال B

پر جيڪڏهن اهو هڪ صف آهي [1، 2، 4، 4] ۽ قيمت 8 آهي، فنڪشن کي صحيح موٽڻ گهرجي ڇاڪاڻ ته 4 + 4 = 8.

حل 1: وحشي قوت

وقت جي پيچيدگي: O(N²).
خلائي پيچيدگي: O(1).

سڀ کان وڌيڪ واضح مطلب آهي nested loops جو هڪ جوڙو استعمال ڪرڻ.

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 سان مقابلو ڪرڻ جي برابر آهي، پر هن حل ۾ اسان ٻنهي اختيارن جي ڪوشش ڪندا آهيون).

ڇاڪاڻ ته اسان جو حل لوپس لاءِ nested جو هڪ جوڙو استعمال ڪري ٿو، اهو 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;
};

هاڻي سڀ ڪجهه ٺيڪ آهي، حل بهتر لڳي ٿو. پر ڪير ضمانت ڏئي سگهي ٿو ته صف آرڊر ڪيو ويو هو؟

پوءِ ڇا؟

پهرين نظر ۾، اسان آساني سان ترتيب ڏئي سگهون ٿا پهرين صف کي ۽ پوءِ مٿي ڏنل حل استعمال ڪيو. پر اهو ڪيئن عمل جي وقت تي اثر انداز ڪندو؟

بهترين الگورتھم وقت جي پيچيدگي سان Quicksort 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;
};

حل جو بنياد هڪ لوپ آهي، جنهن کي، جيئن اسان مٿي ڏٺو، هڪ لڪير واري وقت جي پيچيدگي O (N) آهي.

اسان جي فنڪشن جو ٻيو ورهاڱي وارو حصو Array.prototype.include() آهي، هڪ جاوا اسڪرپٽ جو طريقو جيڪو واپس ڏيندو صحيح يا غلط ان تي منحصر آهي ته ڇا صف ۾ ڏنل قيمت شامل آهي.

Array.prototype.includes() جي وقت جي پيچيدگي کي معلوم ڪرڻ لاءِ، اسان MDN پاران مهيا ڪيل پولي فل کي ڏسي سگھون ٿا (۽ جاوا اسڪرپٽ ۾ لکيل آهي) يا جاوا اسڪرپٽ انجڻ جي سورس ڪوڊ ۾ طريقو استعمال ڪري سگهون ٿا جهڙوڪ گوگل 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 ۾ جڏهن لوپ آهي جيڪو (تقريبا) ڏنل صف جي پوري ڊگھائي کي پار ڪري ٿو. مطلب ته ان جي وقت جي پيچيدگي به لڪير آهي. خير، ڇاڪاڻ ته اهو هميشه اسان جي مکيه صف جي پويان هڪ قدم آهي، وقت جي پيچيدگي O (N + (N - 1)) آهي. Big O Notation استعمال ڪندي، اسان ان کي آسان ڪريون ٿا O (N) - ڇاڪاڻ ته اھو N آھي جيڪو ان پٽ جي سائيز کي وڌائڻ وقت تمام وڏو اثر رکي ٿو.

مقامي پيچيدگي جي حوالي سان، هڪ اضافي صف جي ضرورت آهي جنهن جي ڊيگهه اصل صف کي آئيني ڪري ٿي (مائنس هڪ، ها، پر ان کي نظر انداز ڪري سگهجي ٿو)، نتيجي ۾ O (N) فضائي پيچيدگي. خير، ميموري جي استعمال ۾ اضافو الورورٿم جي وڌ ۾ وڌ ڪارڪردگي کي يقيني بڻائي ٿو.

مون کي اميد آهي ته توهان مضمون کي توهان جي وڊيو انٽرويو جي اضافي طور مفيد ثابت ڪيو. اهو ڏيکاري ٿو ته هڪ سادي مسئلو ڪيترن ئي طريقن سان حل ڪري سگهجي ٿو مختلف وسيلن جي استعمال سان (وقت، ياداشت).

Skillbox سفارش ڪري ٿو:

• لاڳو ٿيل آن لائن ڪورس "Python ڊيٽا تجزيه نگار".
• آن لائين ڪورس "پروفيشنل فرنٽ اينڊ ڊولپر".
• عملي سال ڪورس "PHP ڊولپر 0 کان PRO تائين".

جو ذريعو: www.habr.com