cracking the coding interview

แคร็กโซลูชันการสัมภาษณ์การเข้ารหัสด้วยการทดสอบหน่วยอัตโนมัติ

• ✅ โซลูชั่น C++
• ✅ โซลูชั่นหลาม
• ✅ การทดสอบหน่วยอัตโนมัติ
• ✅ การพัฒนาเชิงรุก
• ✅ รองรับหลายแพลตฟอร์ม: Mac, Linux และ Windows

การแนะนำ

Repo นี้ประกอบด้วยโซลูชัน C++ และ Python สำหรับ Cracking the Coding Interview ฉบับที่ 6 ของ Gayle Laakmann McDowell เป็นที่ยอมรับว่ามีที่เก็บ GitHub อื่นพร้อมโซลูชันสำหรับหนังสือเล่มนี้ แต่คุณรู้ได้อย่างไรว่ารหัสของพวกเขาถูกต้องจริง ๆ ? หากยังไม่ทดลองแสดงว่าไม่!

ในโปรเจ็กต์นี้ โซลูชัน C++ ทุกตัวมีการทดสอบหน่วยโดยใช้เฟรมเวิร์ก C++ Catch และโซลูชัน Python ทุกตัวมีการทดสอบหน่วยโดยใช้เฟรมเวิร์ก Unittest ของ Python เราบังคับใช้การทดสอบความถูกต้องโดยอัตโนมัติโดยใช้เซิร์ฟเวอร์การรวมอย่างต่อเนื่อง เพื่อให้มั่นใจว่าโซลูชันนั้นทำจากโค้ด ที่มีชีวิต ซึ่งได้รับการดำเนินการและทดสอบในทุกคอมมิต ตามความรู้ของฉัน นี่เป็นพื้นที่เก็บข้อมูลโซลูชันแห่งเดียวบนอินเทอร์เน็ตที่มีความเข้มงวดในการทดสอบระดับนี้: ความครอบคลุมการทดสอบอัตโนมัติ >90% หมายความว่าคุณสามารถอ้างอิงและสนับสนุนโซลูชันด้วยความมั่นใจ

สารบัญ

โซลูชัน C ++:

0. การทดสอบหน่วย C ++
1. บทที่ 1 - อาร์เรย์และสตริง: 9 / 9 เสร็จสมบูรณ์
2. บทที่ 2 - รายการที่เชื่อมโยง: 8 / 8 เสร็จสมบูรณ์
3. บทที่ 3 - สแต็คและคิว: 4 / 6 เสร็จสมบูรณ์
4. บทที่ 4 - ต้นไม้และกราฟ: เสร็จสมบูรณ์ 11 / 12
5. บทที่ 5 - การจัดการบิต: 7 / 8 เสร็จสมบูรณ์
6. บทที่ 6 - คณิตศาสตร์และลอจิก: 0 / 10 เสร็จสมบูรณ์
7. บทที่ 7 - การออกแบบเชิงวัตถุ: 0 / 12 เสร็จสมบูรณ์
8. บทที่ 8 - การเรียกซ้ำและการเขียนโปรแกรมแบบไดนามิก: 8 / 14 เสร็จสมบูรณ์
9. บทที่ 9 - การออกแบบระบบและความสามารถในการปรับขนาด: 0 / 8 เสร็จสมบูรณ์
10. บทที่ 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. การทดสอบหน่วย Python
1. บทที่ 1 - อาร์เรย์และสตริง: 9 / 9 เสร็จสมบูรณ์
2. บทที่ 2 - รายการที่เชื่อมโยง: 8 / 8 เสร็จสมบูรณ์
3. บทที่ 3 - สแต็คและคิว: 6 / 6 เสร็จสมบูรณ์
4. บทที่ 4 - ต้นไม้และกราฟ: เสร็จสมบูรณ์ 11 / 12
5. บทที่ 5 - การจัดการบิต: 7 / 8 เสร็จสมบูรณ์
6. บทที่ 6 - คณิตศาสตร์และลอจิก: 0 / 10 เสร็จสมบูรณ์
7. บทที่ 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 เสร็จสมบูรณ์

Python Total: เสร็จสิ้น 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 เท่านั้น):

นี่จะแสดงอย่างชัดเจนว่าบรรทัดใดที่ไม่ครอบคลุมโดยการทดสอบในไฟล์ต้นฉบับ Python แต่ละไฟล์:

 pip install coverage
make test_coverage

มีส่วนร่วม

เป้าหมายของโปรเจ็กต์นี้คือการเขียนโซลูชัน Python และ C++ ที่ผ่านการทดสอบแล้วสำหรับทุกปัญหาในหนังสือเรียนฉบับที่ 6 ฉันต้องการความช่วยเหลืออย่างแน่นอน ดังนั้นจึงยินดีต้อนรับ PR มีอะไรให้ทำมากมายเพราะแต่ละโซลูชันต้องการชุดข้อมูลและโครงสร้างพื้นฐานขนาดเล็กของตัวเองเพื่อทำการทดสอบ ต่อไปนี้คือวิธีที่คุณสามารถช่วยได้:

1. แก้ไขข้อบกพร่อง ?.
2. การแก้ไขหรือปรับปรุงแนวทางแก้ไขปัญหาในภาษาใดภาษาหนึ่ง (ดูความคืบหน้าในสารบัญ)
3. เพิ่มการทดสอบหน่วยเพิ่มเติมเพื่อเพิ่ม % ความครอบคลุมของการทดสอบ
4. การใช้การวัดความครอบคลุมการทดสอบ C++ อัตโนมัติโดยใช้ gcov
5. การรวมการรายงาน % ความครอบคลุมการทดสอบอัตโนมัติสำหรับทั้ง Python และ C++ ผ่าน Coveralls
6. การเพิ่มคำอธิบายวิธีแก้ปัญหาร้อยแก้วสำหรับปัญหาที่ไม่มี

หากมีส่วนสนับสนุนกรุณาประชาสัมพันธ์สาขา master ด้วย โปรดส่งข้อความถึงฉันเพื่อขอคำชี้แจงเกี่ยวกับรายการข้างต้น

ภาคผนวก: การพัฒนา Windows

บนเครื่อง 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:

 pip install numpy

จากนั้น เปิดโปรเจ็กต์ใน Visual Studio 2017 ที่รองรับ CMake ฉันพบว่าขั้นตอนการทำงานที่ดีที่สุดคือการใช้ Visual Studio เพื่อแก้ไขโค้ดและใช้ฟังก์ชันการดีบัก ก่อนที่จะสร้างโค้ด คุณต้องปฏิบัติตามคำแนะนำเหล่านี้เพื่อบอก Visual Studio ให้ดาวน์โหลด PDB ที่ต้องการ นอกจากนี้ บทความนี้จะอธิบายการสนับสนุน Visual Studio CMake โดยละเอียดเพิ่มเติมหากคุณสนใจ ไฟล์ CMakeSettings.json ในไดเร็กทอรีโปรเจ็กต์รากจะตั้งค่าตำแหน่งของโฟลเดอร์บิลด์ Visual Studio ให้อยู่ภายในโฟลเดอร์รูทของโปรเจ็กต์

การทดสอบ

การเรียกใช้การทดสอบและการดูผลลัพธ์นั้นทำได้ดีที่สุดจากหน้าต่าง PowerShell เนื่องจาก VisualStudio ในโหมด CMake ไม่ อนุญาตให้เอาต์พุตคอนโซลของไฟล์ tests.exe และ tests.py ยังคงมองเห็นได้แม้ว่าจะกด CTRL + F5 ตามที่อธิบายไว้ในโพสต์นี้ ซึ่ง ใช้กับการใช้งาน Visual Studio "ปกติ" ฉันกำลังติดตามสถานการณ์อีกครั้ง: Visual Studio และเมื่อฉันพบวิธีแก้ปัญหาที่ดีกว่า ฉันจะนำไปใช้หรือโพสต์ไว้ หากคุณรู้อะไรที่ดีกว่าโปรดติดต่อฉัน

ในระหว่างนี้ จากไดเร็กทอรีรากของโปรเจ็กต์ คุณสามารถรันการทดสอบ Python โดยใช้ ...

 python tests.py

... และคุณสามารถรันการทดสอบ C++ ได้โดยใช้ ...

 .buildx64-Debugtests.exe