जावास्क्रिप्ट में Google साक्षात्कार से किसी समस्या का समाधान: 4 अलग-अलग तरीके

जब मैं एल्गोरिदम के प्रदर्शन का अध्ययन कर रहा था, तो मुझे यह बात पता चली यह गूगल मॉक इंटरव्यू का वीडियो है।. यह न केवल इस बात का अंदाजा देता है कि बड़े प्रौद्योगिकी निगमों में साक्षात्कार कैसे आयोजित किए जाते हैं, बल्कि यह आपको यह समझने की भी अनुमति देता है कि एल्गोरिथम समस्याओं को यथासंभव कुशलतापूर्वक कैसे हल किया जाता है।

यह लेख एक प्रकार से वीडियो के साथ संगत है. इसमें मैं दिखाए गए सभी समाधानों पर टिप्पणियाँ प्रदान करता हूँ, साथ ही जावास्क्रिप्ट में समाधान का अपना संस्करण भी प्रदान करता हूँ। प्रत्येक एल्गोरिदम की बारीकियों पर भी चर्चा की गई है।

अनुस्मारक: "हैबर" के सभी पाठकों के लिए - "हैबर" प्रचार कोड का उपयोग करके किसी भी स्किलबॉक्स पाठ्यक्रम में नामांकन करते समय 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)) होता है। हालाँकि, आपको अभी भी प्रत्येक तत्व को अन्य सभी मानों के विरुद्ध जांचने के लिए लूप का उपयोग करने की आवश्यकता है।

यहां बताया गया है कि समाधान कैसा दिख सकता है. चीजों को स्पष्ट करने के लिए, हम बाइनरी खोज को नियंत्रित करने के लिए एक अलग फ़ंक्शन का उपयोग करते हैं। और रिमूवइंडेक्स() फ़ंक्शन भी, जो दिए गए इंडेक्स को घटाकर सरणी का संस्करण लौटाता है।

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(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(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 द्वारा प्रदान की गई पॉलीफ़िल (और जावास्क्रिप्ट में लिखी गई) को देख सकते हैं या 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)) है। बिग ओ नोटेशन का उपयोग करते हुए, हम इसे ओ (एन) तक सरल बनाते हैं - क्योंकि यह एन है जिसका इनपुट आकार बढ़ाते समय सबसे अधिक प्रभाव पड़ता है।

स्थानिक जटिलता के संबंध में, एक अतिरिक्त सरणी की आवश्यकता होती है जिसकी लंबाई मूल सरणी को प्रतिबिंबित करती है (शून्य से एक, हां, लेकिन इसे अनदेखा किया जा सकता है), जिसके परिणामस्वरूप ओ (एन) स्थानिक जटिलता होती है। खैर, बढ़ी हुई मेमोरी उपयोग एल्गोरिदम की अधिकतम दक्षता सुनिश्चित करती है।

मुझे आशा है कि आपको यह लेख आपके वीडियो साक्षात्कार के पूरक के रूप में उपयोगी लगेगा। यह दर्शाता है कि एक साधारण समस्या को विभिन्न मात्रा में उपयोग किए गए संसाधनों (समय, मेमोरी) के साथ कई अलग-अलग तरीकों से हल किया जा सकता है।

स्किलबॉक्स अनुशंसा करता है:

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

स्रोत: www.habr.com