जाभास्क्रिप्टमा गुगल अन्तर्वार्ताबाट समस्या समाधान गर्दै: 4 फरक तरिकाहरू

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

यो लेख भिडियो संग संगत को एक प्रकार हो। यसमा म देखाइएका सबै समाधानहरूमा टिप्पणीहरू प्रदान गर्दछु, साथै JavaScript मा समाधानको मेरो आफ्नै संस्करण। प्रत्येक एल्गोरिथ्मको सूक्ष्मताहरू पनि छलफल गरिन्छ।

हामी सम्झाउँछौं: सबै Habr पाठकहरूका लागि - Habr प्रोमो कोड प्रयोग गरी कुनै पनि Skillbox पाठ्यक्रममा भर्ना गर्दा १०,००० रूबल छुट।

Skillbox सिफारिस गर्दछ: व्यावहारिक पाठ्यक्रम "मोबाइल विकासकर्ता प्रो".

समस्याको गठन

हामीलाई अर्डर गरिएको एरे र एक विशिष्ट मान दिइएको छ। त्यसपछि array मा कुनै पनि दुई संख्याको योगफल दिइएको मान बराबर हुन सक्छ कि छैन भन्ने आधारमा सही वा गलत फर्काउने प्रकार्य सिर्जना गर्न सोधिन्छ।

अर्को शब्दमा, के त्यहाँ एरेमा दुईवटा पूर्णाङ्कहरू छन्, x र y, जसलाई सँगै जोड्दा तोकिएको मान बराबर हुन्छ?

उदाहरण ए

यदि हामीलाई एरे [1, 2, 4, 9] दिइएको छ र मान 8 छ भने, प्रकार्यले गलत फर्काउँछ किनभने एरेमा कुनै पनि दुई संख्याहरू 8 सम्म थप्न सक्दैन।

उदाहरण B

तर यदि यो एरे [1, 2, 4, 4] हो र मान 8 हो भने, प्रकार्यले 4 + 4 = 8 को कारणले सही फर्काउनु पर्छ।

समाधान १: ब्रुट फोर्स

समय जटिलता: 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²) समय जटिलतासँग चतुर्भुज हो।

समाधान २: बाइनरी खोज

समय जटिलता: O(Nlog(N))।
अन्तरिक्ष जटिलता: O(1).

एरेहरू अर्डर भएकाले, हामी बाइनरी खोजी प्रयोग गरेर समाधान खोज्न सक्छौं। यो क्रमबद्ध arrays को लागि सबैभन्दा कुशल एल्गोरिथ्म हो। बाइनरी खोजमा O(log(N)) को चलिरहेको समय हुन्छ। यद्यपि, तपाईंले अझै पनि अन्य सबै मानहरू विरुद्ध प्रत्येक तत्व जाँच गर्नको लागि लुप प्रयोग गर्न आवश्यक छ।

यहाँ एक समाधान जस्तो देखिन सक्छ। चीजहरू स्पष्ट गर्न, हामी बाइनरी खोज नियन्त्रण गर्न छुट्टै प्रकार्य प्रयोग गर्छौं। र पनि removeIndex() प्रकार्य, जो दिइएको अनुक्रमणिका माइनस array को संस्करण फर्काउँछ।

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

एल्गोरिदम अनुक्रमणिका [०] बाट सुरु हुन्छ। यसले त्यसपछि पहिलो अनुक्रमणिका बाहेक एर्रेको संस्करण सिर्जना गर्दछ र बाइनरी खोजी प्रयोग गर्दछ कि इच्छित योगफल उत्पादन गर्न एरेमा बाँकी मानहरू थप्न सकिन्छ। यो कार्य एरेमा प्रत्येक तत्वको लागि एक पटक गरिन्छ।

लूपको लागि आफैमा 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 array संग एक रेखीय समाधान फेला पार्न सम्भव छ?

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 मा दिइएको मान समावेश छ कि छैन भन्ने आधारमा सही वा गलत फर्काउँछ।

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) स्थानिय जटिलता हुन्छ। ठीक छ, मेमोरी उपयोग बढ्यो एल्गोरिथ्मको अधिकतम दक्षता सुनिश्चित गर्दछ।

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

Skillbox सिफारिस गर्दछ:

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

स्रोत: www.habr.com