حل مهمة من مقابلة Google على JavaScript: 4 طرق مختلفة

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

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

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

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

بيان المشكلة

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

بمعنى آخر ، هل هناك رقمان صحيحان x و y في الصفيف ، عند إضافتهما ، يساويان القيمة المحددة؟

مثال أ

إذا حصلنا على صفيف [1 ، 2 ، 4 ، 9] وقيمة 8 ، فستُرجع الدالة false ، لأنه لا يوجد رقمان من الصفيف يمكن أن يعطيا 8 في المجموع.

مثال ب

ولكن إذا كانت صفيفًا [1 ، 2 ، 4 ، 4] وكانت القيمة 8 ، فيجب أن ترجع الدالة true ، لأن 4 + 4 = 8.

الحل 1. Bruteforce

الصعوبة الزمنية: 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) .

نظرًا لأن المصفوفات مرتبة ، يمكننا البحث عن حل باستخدام البحث الثنائي. هذه هي الخوارزمية الأكثر كفاءة للصفائف المطلوبة. البحث الثنائي نفسه لديه وقت التشغيل (سجل (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) ، لكن داخل الحلبة for do نقوم بالبحث الثنائي ، مما يعطي إجمالي تعقيد الوقت لـ O (Nlog (N)). هذا الحل أفضل من الحل السابق ، لكن لا يزال هناك شيء بحاجة إلى تحسين.


الحل 3. الوقت الخطي

الصعوبة الزمنية: O (N).
التعقيد المكاني: O (1).

الآن سنحل المشكلة ، مع تذكر أن المجموعة مصنفة. الحل هو أخذ رقمين: واحد في البداية والآخر في النهاية. إذا كانت النتيجة مختلفة عن النتيجة المطلوبة ، فسنغير نقاط البداية والنهاية.

في النهاية ، إما أن نلتقي بالقيمة المطلوبة ونرجع القيمة true ، أو تتقارب نقاط البداية والنهاية وتعود كاذبة.

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

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

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


آمل أن تكون هذه المقالة مفيدة لك كمرفق بمقابلة بالفيديو. إنه يُظهر أنه يمكن حل مشكلة بسيطة بعدة طرق مختلفة بكميات مختلفة من الموارد المستخدمة (الوقت ، الذاكرة).

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

• تطبيق بيثون محلل البيانات بالطبع على الانترنت.
  
• دورة عبر الإنترنت "Profession frontend-developer . "
• الدورة السنوية العملية "PHP-developer من 0 إلى PRO" .