जावास्क्रिप्ट पर एक Google साक्षात्कार से एक कार्य को हल करना: 4 अलग-अलग तरीके

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

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

हम आपको याद दिलाते हैं: "हैबर" के सभी पाठकों के लिए - "हैबर" प्रोमो कोड का उपयोग करके किसी भी स्किलबॉक्स कोर्स के लिए पंजीकरण करते समय 10,000 रूबल की छूट।

स्किलबॉक्स अनुशंसा करता है: व्यावहारिक पाठ्यक्रम "मोबाइल डेवलपर प्रो" ।

समस्या का बयान

हमें एक ऑर्डर किया गया सरणी और एक विशिष्ट मूल्य दिया जाता है। फिर वे एक फ़ंक्शन बनाने के लिए कहते हैं जो सही या गलत रिटर्न देता है, इस पर निर्भर करता है कि सरणी से किसी भी दो संख्याओं का योग दिए गए मूल्य के बराबर हो सकता है या नहीं।

दूसरे शब्दों में, क्या सरणी में दो पूर्णांक x और y हैं, जो जोड़े जाने पर, निर्दिष्ट मान के बराबर हैं?

उदाहरण ए

यदि हमें एक सरणी [1, 2, 4, 9] और 8 का मान दिया गया है, तो फ़ंक्शन गलत वापस आ जाएगा, क्योंकि सरणी से कोई भी दो संख्याएँ कुल 8 नहीं दे सकती हैं।

उदाहरण बी

लेकिन अगर यह एक सरणी [1, 2, 4, 4] है और मान 8 है, तो फ़ंक्शन को वापस लौटना चाहिए, क्योंकि 4 + 8 = 8।

समाधान 1. ब्रूटफोर्स

अस्थायी कठिनाई: O (N²)।
स्थानिक जटिलता: ओ (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 के साथ तुलना करने के समान है, लेकिन इस समाधान में हम दोनों विकल्पों की कोशिश करते हैं)।

चूंकि हमारा समाधान छोरों के लिए नेस्टेड की एक जोड़ी का उपयोग करता है, यह ओ (एन²) की समय जटिलता के साथ द्विघात है।


समाधान 2. बाइनरी (बाइनरी) खोज

टेम्पोरल कठिनाई: O (Nlog (N))।
स्थानिक जटिलता: ओ (1) ।

चूंकि सरणियों का आदेश दिया जाता है, हम द्विआधारी खोज का उपयोग करके समाधान की तलाश कर सकते हैं। ऑर्डर किए गए सरणियों के लिए यह सबसे कुशल एल्गोरिदम है। बाइनरी सर्च में स्वयं एक O (लॉग (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. रैखिक समय

अस्थायी कठिनाई: ओ (एन)।
स्थानिक जटिलता: ओ (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; }; 

अब सब कुछ ठीक है, समाधान इष्टतम लगता है। लेकिन कौन गारंटी देगा कि सरणी का आदेश दिया गया था?

फिर क्या?

पहली नज़र में, हम केवल पहले सरणी को सॉर्ट कर सकते हैं, और फिर ऊपर दिए गए समाधान का उपयोग कर सकते हैं। लेकिन यह रनटाइम को कैसे प्रभावित करेगा?

सर्वश्रेष्ठ एल्गोरिथ्म हे (Nlog (N)) समय जटिलता के साथ तेजी से छँटाई कर रहा है। यदि हम इसे अपने इष्टतम समाधान में उपयोग करते हैं, तो यह O (N) से O (Nlog (N)) में इसके प्रदर्शन को बदल देगा। क्या अनियंत्रित सरणी के साथ एक रैखिक समाधान खोजना संभव है?

निर्णय ४

अस्थायी कठिनाई: ओ (एन)।
स्थानिक जटिलता: ओ (एन)।

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

यदि इस सरणी का पहला मान 1 है और खोज मूल्य 8 है, तो हम मान को "खोज मान" के सरणी में जोड़ सकते हैं।

फिर, सरणी के प्रत्येक तत्व को संसाधित करते हुए, हम "खोज मान" के सरणी की जांच कर सकते हैं और देख सकते हैं कि उनमें से एक हमारे मूल्य के बराबर है या नहीं। यदि हाँ, तो सच लौटें।

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

समाधान का आधार लूप के लिए है, जो, जैसा कि हमने ऊपर देखा, में रैखिक समय जटिलता ओ (एन) है।

हमारे फ़ंक्शन का दूसरा पुनरावृति भाग Array.prototype.include () है, एक जावास्क्रिप्ट विधि जो सरणी को दिए गए मान के आधार पर सही या गलत लौटेगी।

Array.prototype.includes () के समय की जटिलता का पता लगाने के लिए, हम MDN द्वारा प्रदान की गई पॉलीफ़िल (और जावास्क्रिप्ट में लिखी गई) को देख सकते हैं, या Google V8 (C ++) जैसे जावास्क्रिप्ट इंजन के स्रोत कोड में एक विधि का उपयोग कर सकते हैं।

 // https://tc39.imtqy.com/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 में लूप है, जो दिए गए एरे की पूरी लंबाई का पता लगाता है। इसका मतलब है कि इसकी अस्थायी जटिलता रैखिक भी है। खैर, चूंकि यह हमेशा हमारे मुख्य सरणी से एक कदम पीछे है, समय की जटिलता हे (एन + (एन - 1))। बिग ओ नोटेशन का उपयोग करते हुए, हम इसे ओ (एन) के लिए सरल करते हैं - क्योंकि यह एन है जो बढ़ते इनपुट आकार के साथ सबसे बड़ा प्रभाव है।

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


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

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

• एप्लाइड पायथन डेटा विश्लेषक ऑनलाइन पाठ्यक्रम।
  
• ऑनलाइन कोर्स "प्रोफेशन फ्रंटेंड-डेवलपर । "
• व्यावहारिक वार्षिक पाठ्यक्रम "पीएचपी-डेवलपर 0 से प्रो तक" ।