حل مشكلة من مقابلة Google في JavaScript: 4 طرق مختلفة

عندما كنت أدرس أداء الخوارزميات، صادفت هذا هذا فيديو لمقابلة وهمية من Google.. فهو لا يعطي فكرة عن كيفية إجراء المقابلات في شركات التكنولوجيا الكبرى فحسب، بل يسمح لك أيضًا بفهم كيفية حل المشكلات الخوارزمية بأكبر قدر ممكن من الكفاءة.

هذه المقالة هي نوع من المرافقة للفيديو. أقدم فيه تعليقات على جميع الحلول المعروضة، بالإضافة إلى نسختي الخاصة من الحل في JavaScript. وتناقش أيضًا الفروق الدقيقة في كل خوارزمية.

نذكر: لجميع قراء "Habr" - خصم 10 روبل عند التسجيل في أي دورة Skillbox باستخدام رمز "Habr" الترويجي.

يوصي Skillbox بما يلي: دورة عملية "Mobile Developer PRO".

صياغة المشكلة

لقد حصلنا على مصفوفة مرتبة وقيمة محددة. يُطلب بعد ذلك إنشاء دالة تُرجع صوابًا أو خطأً اعتمادًا على ما إذا كان مجموع أي رقمين في المصفوفة يمكن أن يساوي قيمة معينة.

بمعنى آخر، هل يوجد عددان صحيحان في المصفوفة، 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، لكننا في هذا الحل نجرب كلا الخيارين).

نظرًا لأن حلنا يستخدم زوجًا من حلقات for المتداخلة، فهو حل تربيعي مع تعقيد زمني O(N²).

الحل 2: البحث الثنائي

التعقيد الزمني: O(Nlog(N)).
تعقيد الفضاء: O(1).

وبما أن المصفوفات مرتبة، فيمكننا البحث عن حل باستخدام البحث الثنائي. هذه هي الخوارزمية الأكثر كفاءة للمصفوفات المرتبة. البحث الثنائي نفسه له وقت تشغيل قدره O(log(N)). ومع ذلك، لا تزال بحاجة إلى استخدام حلقة for للتحقق من كل عنصر مقابل جميع القيم الأخرى.

إليك ما قد يبدو عليه الحل. لتوضيح الأمور، نستخدم وظيفة منفصلة للتحكم في البحث الثنائي. وأيضًا وظيفة 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]. ثم يقوم بإنشاء نسخة من المصفوفة باستثناء الفهرس الأول ويستخدم البحث الثنائي لمعرفة ما إذا كان يمكن إضافة أي من القيم المتبقية إلى المصفوفة لإنتاج المجموع المطلوب. يتم تنفيذ هذا الإجراء مرة واحدة لكل عنصر في المصفوفة.

سيكون للحلقة for نفسها تعقيد زمني خطي قدره O(N)، ولكن داخل الحلقة for نقوم بإجراء بحث ثنائي، مما يعطي تعقيدًا زمنيًا إجماليًا قدره 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;
};

أساس الحل هو حلقة for، والتي، كما رأينا أعلاه، لها تعقيد زمني خطي قدره O(N).

الجزء التكراري الثاني من وظيفتنا هو Array.prototype.include()، وهي طريقة JavaScript ستعيد صوابًا أو خطأ اعتمادًا على ما إذا كان المصفوفة تحتوي على القيمة المحددة.

لمعرفة التعقيد الزمني لـ Array.prototype.includes()، يمكننا إلقاء نظرة على polyfill الذي توفره MDN (ومكتوب بلغة JavaScript) أو استخدام طريقة في الكود المصدري لمحرك JavaScript مثل 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() هو حلقة while في الخطوة 7 والتي (تقريبًا) تعبر كامل طول المصفوفة المحددة. وهذا يعني أن تعقيدها الزمني خطي أيضًا. حسنًا، نظرًا لأنه دائمًا ما يكون متأخرًا بخطوة واحدة عن المصفوفة الرئيسية، فإن التعقيد الزمني هو O (N + (N - 1)). باستخدام Big O Notation، نقوم بتبسيطها إلى O(N) - لأن N لها التأثير الأكبر عند زيادة حجم الإدخال.

فيما يتعلق بالتعقيد المكاني، هناك حاجة إلى مصفوفة إضافية يعكس طولها المصفوفة الأصلية (ناقص واحد، نعم، ولكن يمكن تجاهل ذلك)، مما يؤدي إلى التعقيد المكاني O(N). حسنًا، زيادة استخدام الذاكرة تضمن أقصى قدر من الكفاءة للخوارزمية.

أتمنى أن تجد المقالة مفيدة كملحق لمقابلة الفيديو الخاصة بك. يوضح أنه يمكن حل مشكلة بسيطة بعدة طرق مختلفة باستخدام كميات مختلفة من الموارد (الوقت والذاكرة).

يوصي Skillbox بما يلي:

• دورة تطبيقية عبر الإنترنت "محلل بيانات Python".
• دورة على شبكة الإنترنت "مهنة مطور الواجهة".
• دورة سنة عملية "مطور PHP من 0 إلى PRO".

المصدر: www.habr.com