cracking the coding interview

كسر حلول مقابلة الترميز باستخدام اختبارات الوحدة الآلية

• ✅ حلول لغة C++
• ✅ حلول بايثون
• ✅ اختبارات الوحدة الآلية
• ✅ التطوير النشط
• ✅ دعم الأنظمة الأساسية المتعددة: Mac وLinux وWindows

مقدمة

يحتوي هذا الريبو على حلول C++ وPython لـ Gayle Laakmann McDowell's Cracking the Coding Interview 6th Edition . من المسلم به أن هناك مستودعات GitHub أخرى تحتوي على حلول لهذا الكتاب. ولكن كيف تعرف أن الكود الخاص بهم صحيح بالفعل؟ إذا لم يتم اختباره، فأنت لا تفعل ذلك!

في هذا المشروع، يحتوي كل حل من حلول C++ على اختبارات وحدة باستخدام إطار عمل C++ Catch، وكل حل من حلول Python يحتوي على اختبارات وحدة باستخدام إطار عمل Python Unittest. نحن نفرض صحة الاختبار تلقائيًا باستخدام خوادم التكامل المستمر لضمان أن الحلول مصنوعة من تعليمات برمجية حية يتم تنفيذها واختبارها في كل التزام على حدة. على حد علمي، هذا هو مستودع الحلول الوحيد على الإنترنت الذي يتمتع بهذا المستوى من دقة الاختبار: > تغطية الاختبار الآلي بنسبة 90% تعني أنه يمكنك الرجوع إلى الحلول والمساهمة بها بثقة.

جدول المحتويات

حلول لغة C++:

0. اختبارات وحدة C++
1. الفصل 1 - المصفوفات والسلاسل: 9 / 9 كاملة.
2. الفصل الثاني - القوائم المرتبطة: 8 / 8 كاملة.
3. الفصل 3 - الأكوام وقوائم الانتظار: 4 / 6 مكتمل.
4. الفصل الرابع - الأشجار والرسوم البيانية: 11 / 12 كاملاً.
5. الفصل الخامس - معالجة البتات: 7 / 8 مكتمل.
6. الفصل 6 - الرياضيات والمنطق: 0 / 10 كامل.
7. الفصل السابع - التصميم الموجه للكائنات: 0 / 12 مكتمل.
8. الفصل 8 - العودية والبرمجة الديناميكية: 8 / 14 كامل.
9. الفصل 9 - تصميم النظام وقابلية التوسع: 0 / 8 مكتمل.
10. الفصل العاشر - الفرز والبحث: 10 / 11 مكتمل.
11. الفصل 11 - الاختبار: 0 / 6 كامل.
12. الفصل 12 - C وC++: 10 / 11
13. الفصل 13 - جافا: غير متاح
14. الفصل 14 - قواعد البيانات: 0 / 7 كاملة.
15. الفصل 15 - الخيوط والأقفال: 0 / 4 كامل.
16. الفصل 16 - معتدل: 11 / 26 كاملاً.
17. الفصل 17 - الصعب: 1 / 26 كامل.
18. تمارين متنوعة: 2 كاملة.

إجمالي C++: 81 حلًا مكتملًا.

حلول بايثون:

0. اختبارات وحدة بايثون
1. الفصل 1 - المصفوفات والسلاسل: 9 / 9 كاملة.
2. الفصل الثاني - القوائم المرتبطة: 8 / 8 كاملة.
3. الفصل 3 - الأكوام وقوائم الانتظار: 6 / 6 مكتمل.
4. الفصل الرابع - الأشجار والرسوم البيانية: 11 / 12 كاملاً.
5. الفصل الخامس - معالجة البتات: 7 / 8 مكتمل.
6. الفصل 6 - الرياضيات والمنطق: 0 / 10 كامل.
7. الفصل السابع - التصميم الموجه للكائنات: 0 / 12 مكتمل.
8. الفصل 8 - العودية والبرمجة الديناميكية: 11 / 14 كاملة.
9. الفصل 9 - تصميم النظام وقابلية التوسع: 0 / 8 مكتمل.
10. الفصل 10 - الفرز والبحث: 1 / 11 كامل.
11. الفصل 11 - الاختبار: 0 / 6 كامل.
12. الفصل 12 - C وC++: غير متاح
13. الفصل 13 - جافا: غير متاح
14. الفصل 14 - قواعد البيانات: 0 / 7 كاملة.
15. الفصل 15 - الخيوط والأقفال: غير متاح
16. الفصل 16 - المتوسط: 2 / 26 كاملاً.
17. الفصل 17 - الصعب: 3 / 26 كامل.

إجمالي بايثون: 58 حلًا مكتملًا.

المجموع الكلي: 139 حلاً فريدًا مكتملًا.

مبنى:

ماك:

يتطلب استخدام Mac تثبيت مديري الحزم Homebrew وPip الذي يتم إجراؤه لك في Makefile:

 git clone https://github.com/alexhagiopol/cracking-the-coding-interview.git ctci
cd ctci
make configure-mac

أوبونتو:

 git clone https://github.com/alexhagiopol/cracking-the-coding-interview.git
cd ctci
make configure-ubuntu

ويندوز:

بالنسبة لمستخدمي Windows، أوصي بتطوير هذا المشروع باستخدام ميزة Windows Subsystem for Linux (WSL) لنظام التشغيل Windows 10 ثم اتباع تعليمات بناء واختبار Ubuntu داخل WSL. ترجع هذه التوصية إلى استخدام أنظمة البناء والتنفيذ المستندة إلى Ubuntu وCMake وmakefile على الخوادم التي تختبر التغييرات التي تطرأ على التعليمات البرمجية تلقائيًا. لمعرفة المزيد حول تطوير Windows، راجع قسم Appendix في نهاية هذه الصفحة.

الاختبار:

الاختبار هو الجزء الأكثر أهمية في هذا المشروع: اختبارات الوحدة فقط هي التي تحدد المشكلة التي يتم حلها. في الدليل الجذر، قم بتنفيذ ما يلي لتشغيل جميع الاختبارات في Python وC++:

 make test

make test هو الأمر الذي أستخدمه كثيرًا أثناء تطوير هذا المشروع. يتبع سير العمل الخاص بي:

1. أقرأ المشكلة وأقوم بتشفير تعريف المشكلة من خلال تنفيذ اختبارات الوحدة الخاصة بها.
2. أقوم بإجراء make test لمعرفة مكان فشل المشروع في تلبية اختبارات الوحدة.
3. أقوم بإضافة حل المشكلة إلى التنفيذ حتى ينجح make test .

اختياري: إنشاء تقرير نسبة تغطية الاختبار محليًا (دعم بايثون فقط):

سيُظهر هذا بالضبط الخطوط التي لا تغطيها الاختبارات في كل ملف مصدر لـ Python:

 pip install coverage
make test_coverage

المساهمة

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

1. إصلاح الخلل؟.
2. حل أو تحسين حلول المشكلات في أي من اللغتين (راجع تقدم الإكمال في جدول المحتويات).
3. إضافة المزيد من اختبارات الوحدات لزيادة نسبة تغطية الاختبار.
4. تنفيذ قياس تغطية اختبار C++ الآلي باستخدام gcov.
5. دمج تقارير النسبة المئوية لتغطية الاختبار الآلي لكل من Python وC++ عبر Coveralls.
6. إضافة أوصاف حل نثرية للمشكلات التي لا تحتوي عليها.

إذا كان لديك أي مساهمات، يرجى تقديم علاقة عامة إلى الفرع master . لا تتردد في مراسلتي لتوضيح أي من البنود المذكورة أعلاه.

الملحق: تطوير ويندوز

على جهاز Windows الخاص بي، أقوم بالتطوير باستخدام CLion الذي يعمل أصلاً في Windows واختبار الكود باستخدام make test في نافذة طرفية WSL. بالنسبة للمستخدمين الذين لا يريدون استخدام WSL، قمت بتطوير منهجية البناء والاختبار أدناه:

مبنى

يمكن تطوير المشروع على نظام Windows فقط بدون WSL باستخدام Visual Studio 2017. قم أولاً باستنساخ الكود:

 git clone https://github.com/alexhagiopol/cracking-the-coding-interview.git
cd ctci
git submodule update --init

ثم قم بتثبيت Python3 وnumpy باستخدام الطريقة التي تختارها. أفضل تثبيت Python3 وpip3 من الموقع الرسمي ثم تثبيت numpy عبر النقطة:

 pip install numpy

ثم افتح المشروع في Visual Studio 2017 الذي يدعم CMake. لقد وجدت أن أفضل سير العمل هو استخدام Visual Studio لتحرير التعليمات البرمجية واستخدام وظيفة تصحيح الأخطاء. قبل إنشاء التعليمات البرمجية، يجب عليك اتباع هذه الإرشادات لإخبار Visual Studio بتنزيل PDBs التي يحتاجها. بالإضافة إلى ذلك، توضح هذه المقالة دعم Visual Studio CMake بمزيد من التفاصيل إذا كنت مهتمًا بذلك. يقوم ملف CMakeSettings.json الموجود في دليل المشروع الجذر بتعيين موقع مجلد إنشاء Visual Studio ليكون داخل المجلد الجذر للمشروع.

اختبار

من الأفضل إجراء الاختبارات ورؤية مخرجاتها من خلال نافذة PowerShell نظرًا لأن VisualStudio في وضع CMake لا يسمح لإخراج وحدة التحكم لملفات tests.exe و tests.py بالبقاء مرئيًا حتى عند الضغط على CTRL + F5 كما هو موضح في هذا المنشور والذي ينطبق على استخدام Visual Studio "العادي". أنا أراقب الوضع فيما يتعلق بـ Visual Studio، وعندما أجد حلولاً أفضل سأقوم بتنفيذها أو نشرها. إذا كنت تعرف شيئا أفضل، يرجى الاتصال بي.

في هذه الأثناء، من الدليل الجذر للمشروع، يمكنك تشغيل اختبارات بايثون باستخدام ...

 python tests.py

... ويمكنك تشغيل اختبارات C++ باستخدام ...

 .buildx64-Debugtests.exe