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 માં જ્યારે લૂપ છે જે (લગભગ) આપેલ એરેની સમગ્ર લંબાઈને પાર કરે છે. મતલબ કે તેની સમયની જટિલતા પણ રેખીય છે. ઠીક છે, કારણ કે તે હંમેશા અમારા મુખ્ય એરે પાછળ એક પગલું છે, સમય જટિલતા O (N + (N - 1)) છે. Big O નોટેશનનો ઉપયોગ કરીને, અમે તેને O(N) માં સરળ બનાવીએ છીએ - કારણ કે તે N છે જે ઇનપુટ કદમાં વધારો કરતી વખતે સૌથી વધુ અસર કરે છે.

અવકાશી જટિલતા અંગે, વધારાની એરેની જરૂર છે જેની લંબાઈ મૂળ એરેને પ્રતિબિંબિત કરે છે (માઈનસ વન, હા, પરંતુ તેને અવગણી શકાય છે), પરિણામે O(N) અવકાશી જટિલતા. ઠીક છે, મેમરીનો વધારો એલ્ગોરિધમની મહત્તમ કાર્યક્ષમતાને સુનિશ્ચિત કરે છે.

હું આશા રાખું છું કે તમને તમારા વિડિઓ ઇન્ટરવ્યુના પૂરક તરીકે લેખ ઉપયોગી લાગશે. તે બતાવે છે કે ઉપયોગમાં લેવાતા વિવિધ સંસાધનો (સમય, મેમરી) વડે એક સરળ સમસ્યાને વિવિધ રીતે ઉકેલી શકાય છે.

સ્કિલબોક્સ ભલામણ કરે છે:

• ઓનલાઈન કોર્સ લાગુ કર્યો "પાયથોન ડેટા એનાલિસ્ટ".
• ઓનલાઇન કોર્સ "પ્રોફેશન ફ્રન્ટ એન્ડ ડેવલપર".
• એક વર્ષનો પ્રેક્ટિકલ કોર્સ "0 થી PRO સુધી PHP વિકાસકર્તા".

સોર્સ: www.habr.com