cracking the coding interview

透過自動化單元測試破解程式設計面試解決方案

• ✅ C++ 解決方案
• ✅ Python 解決方案
• ✅ 自動化單元測試
• ✅ 積極發展
• ✅ 多平台支援：Mac、Linux 和 Windows

介紹

此儲存庫包含 Gayle Laakmann McDowell 的Cracking the Coding Interview 第 6 版的C++ 和 Python 解決方案。誠然，還有其他 GitHub 儲存庫提供了本書的解決方案。但你怎麼知道他們的程式碼其實是正確的呢？如果它未經測試，那麼你就不會！

在此專案中，每個 C++ 解決方案都有使用 C++ Catch 框架的單元測試，每個 Python 解決方案都具有使用 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 章 - Java：不適用
14. 第 14 章 - 資料庫： 0 / 7已完成。
15. 第 15 章 - 線程和鎖： 0 / 4已完成。
16. 第 16 章 - 中： 11 / 26完成。
17. 第 17 章 - 困難： 1 / 26完成。
18. 其他練習：完成2 。

C++ 總數：完成81解決方案。

Python 解決方案：

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 章 - Java：不適用
14. 第 14 章 - 資料庫： 0 / 7已完成。
15. 第 15 章 - 線程和鎖：不適用
16. 第 16 章 - 中： 2 / 26已完成。
17. 第 17 章 - 困難： 3 / 26已完成。

Python 總數：完成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 10 的 Windows Subsystem for Linux (WSL) 功能來開發此項目，然後按照 WSL 內的 Ubuntu 建置和測試說明進行操作。此建議是由於在自動測試程式碼變更的伺服器上使用了基於 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++ 解決方案。我確實需要幫助，所以歡迎 PR。有很多工作要做，因為每個解決方案都需要自己的小型資料集和基礎設施才能進行測試。以下是您可以提供幫助的一些方法：

1. 修復錯誤？
2. 使用任一語言解決或改進問題的解決方案（請參閱目錄中的完成進度）。
3. 增加更多單元測試以提高測試覆蓋率%。
4. 使用 gcov 實現自動化 C++ 測試覆蓋率測量。
5. 透過 Coveralls 整合 Python 和 C++ 的自動測試覆蓋率百分比報告。
6. 為沒有問題的問題添加散文解決方案描述。

如果您有任何貢獻，請向master分支進行 PR。請隨時給我發訊息以澄清上述任何事項。

附錄：Windows 開發

在我自己的 Windows 電腦上，我使用在 Windows 中本機運行的 CLion 進行開發，並在 WSL 終端機視窗中使用make test測試程式碼。對於不想使用 WSL 的用戶，我開發了以下建置和測試方法：

大樓

這個專案可以使用 Visual Studio 2017 在沒有 WSL 的情況下純粹在 Windows 上開發。

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

然後，使用您選擇的方法安裝 Python3 和 numpy。我更喜歡從官方網站安裝 Python3 和 pip3，然後透過 pip 安裝 numpy：

 pip install numpy

然後，在支援 CMake 的 Visual Studio 2017 中開啟該專案。我發現最好的工作流程是使用 Visual Studio 編輯程式碼並使用偵錯功能。在建立程式碼之前，您必須按照以下說明告訴 Visual Studio 下載它所需的 PDB。此外，如果您有興趣，本文也更詳細地介紹了 Visual Studio CMake 支援。根專案目錄中的 CMakeSettings.json 檔案將 Visual Studio 產生資料夾的位置設定為專案的根資料夾內。

測試

執行測試並查看其輸出最好從 PowerShell 視窗完成，因為 CMake 模式下的 VisualStudio不允許tests.exe和tests.py檔案的控制台輸出保持可見，即使按 CTRL + F5 也如此，如本文所述適用於「正常」Visual Studio 使用。我正在監視有關 Visual Studio 的情況，當我找到更好的解決方案時，我將實施它們或發布它們。如果您知道更好的，請與我聯繫。

同時，您可以從專案根目錄執行 Python 測試...

 python tests.py

...且您可以使用...執行 C++ 測試

 .buildx64-Debugtests.exe