JavaScript मधील Google मुलाखतीमधून समस्या सोडवणे: 4 भिन्न मार्ग

जेव्हा मी अल्गोरिदमच्या कामगिरीचा अभ्यास करत होतो, तेव्हा मला हे कळले गुगल मॉक इंटरव्ह्यूचा हा व्हिडिओ आहे.. हे केवळ मोठ्या तंत्रज्ञान कॉर्पोरेशनमध्ये मुलाखती कशा घेतल्या जातात याची कल्पना देत नाही तर अल्गोरिदमिक समस्या शक्य तितक्या कार्यक्षमतेने कशा सोडवल्या जातात हे देखील समजण्यास अनुमती देते.

हा लेख व्हिडिओला एक प्रकारची साथ आहे. त्यामध्ये मी दाखवलेल्या सर्व उपायांवर टिप्पण्या देतो, तसेच JavaScript मधील माझ्या स्वतःच्या सोल्यूशनची आवृत्ती. प्रत्येक अल्गोरिदमच्या बारकावे देखील चर्चा केल्या जातात.

आम्ही आठवण करून देतो: सर्व Habr वाचकांसाठी - Habr प्रोमो कोड वापरून कोणत्याही स्किलबॉक्स कोर्समध्ये नावनोंदणी करताना 10 रूबल सवलत.

स्किलबॉक्स शिफारस करतो: प्रॅक्टिकल कोर्स "मोबाइल डेव्हलपर प्रो".

समस्येची निर्मिती

आम्हाला ऑर्डर केलेला अॅरे आणि विशिष्ट मूल्य दिले जाते. त्यानंतर अ‍ॅरेमधील कोणत्याही दोन संख्यांची बेरीज दिलेल्या मूल्याच्या बरोबरीने असू शकते की नाही यावर अवलंबून खरे किंवा खोटे देणारे फंक्शन तयार करण्यास सांगितले जाते.

दुस-या शब्दात सांगायचे तर, अॅरेमध्ये x आणि y असे दोन पूर्णांक आहेत का, जे एकत्र जोडल्यावर निर्दिष्ट मूल्याच्या बरोबरीचे असतात?

उदाहरण ए

जर आपल्याला अॅरे [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)) मध्ये बदलेल. अक्रमित अॅरेसह रेखीय समाधान शोधणे शक्य आहे का?

समाधान 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(), एक 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)) आहे. बिग ओ नोटेशन वापरून, आम्ही ते O(N) वर सोपे करतो - कारण इनपुट आकार वाढवताना सर्वात जास्त परिणाम N चा होतो.

अवकाशीय जटिलतेच्या संदर्भात, अतिरिक्त अॅरे आवश्यक आहे ज्याची लांबी मूळ अॅरेला प्रतिबिंबित करते (वजा एक, होय, परंतु त्याकडे दुर्लक्ष केले जाऊ शकते), परिणामी O(N) अवकाशीय जटिलता येते. बरं, वाढीव मेमरी वापर अल्गोरिदमची जास्तीत जास्त कार्यक्षमता सुनिश्चित करते.

मला आशा आहे की तुम्हाला तुमच्या व्हिडिओ मुलाखतीला पूरक म्हणून लेख उपयुक्त वाटेल. हे दर्शविते की एक साधी समस्या वेगवेगळ्या प्रमाणात वापरल्या जाणार्‍या संसाधनांसह (वेळ, स्मृती) अनेक प्रकारे सोडवता येते.

स्किलबॉक्स शिफारस करतो:

• ऑनलाईन कोर्स लागू केला "पायथन डेटा विश्लेषक".
• ऑनलाईन कोर्स "प्रोफेशन फ्रंटएंड डेव्हलपर".
• एक वर्षाचा प्रॅक्टिकल कोर्स "PHP विकसक 0 ते PRO".

स्त्रोत: www.habr.com