cracking the coding interview

Die Coding-Interview-Lösungen mit automatisierten Unit-Tests knacken

• ✅ C++-Lösungen
• ✅ Python-Lösungen
• ✅ Automatisierte Unit-Tests
• ✅ Aktive Entwicklung
• ✅ Multiplattform-Unterstützung: Mac, Linux und Windows

Einführung

Dieses Repo enthält C++- und Python-Lösungen für Gayle Laakmann McDowells Cracking the Coding Interview 6th Edition . Zugegebenermaßen gibt es auch andere GitHub-Repositories mit Lösungen für dieses Buch. Aber woher wissen Sie, dass ihr Code tatsächlich korrekt ist? Wenn es ungetestet ist, dann tun Sie es nicht!

In diesem Projekt verfügt jede C++-Lösung über Komponententests mit dem C++-Catch-Framework und jede Python-Lösung über Komponententests mit dem Python-Unittest-Framework. Wir erzwingen die Testkorrektheit automatisch mithilfe kontinuierlicher Integrationsserver und stellen sicher, dass die Lösungen aus lebendigem Code bestehen, der bei jedem einzelnen Commit ausgeführt und getestet wird. Meines Wissens ist dies das einzige Lösungs-Repository im Internet mit diesem Maß an Testgenauigkeit: Eine automatisierte Testabdeckung von über 90 % bedeutet, dass Sie vertrauensvoll auf Lösungen verweisen und diese beisteuern können.

Inhaltsverzeichnis

C++-Lösungen:

0. C++-Unit-Tests
1. Kapitel 1 – Arrays und Strings: 9 / 9 abgeschlossen.
2. Kapitel 2 – Verknüpfte Listen: 8 / 8 abgeschlossen.
3. Kapitel 3 – Stapel und Warteschlangen: 4 / 6 abgeschlossen.
4. Kapitel 4 – Bäume und Grafiken: 11 / 12 abgeschlossen.
5. Kapitel 5 – Bit-Manipulation: 7 / 8 abgeschlossen.
6. Kapitel 6 – Mathematik und Logik: 0 / 10 abgeschlossen.
7. Kapitel 7 – Objektorientiertes Design: 0 / 12 abgeschlossen.
8. Kapitel 8 – Rekursion und dynamische Programmierung: 8 / 14 abgeschlossen.
9. Kapitel 9 – Systemdesign und Skalierbarkeit: 0 / 8 abgeschlossen.
10. Kapitel 10 – Sortieren und Suchen: 10 / 11 abgeschlossen.
11. Kapitel 11 – Tests: 0 / 6 abgeschlossen.
12. Kapitel 12 – C und C++: 10 / 11
13. Kapitel 13 – Java: N/A
14. Kapitel 14 – Datenbanken: 0 / 7 abgeschlossen.
15. Kapitel 15 – Threads und Schlösser: 0 / 4 abgeschlossen.
16. Kapitel 16 – Mittel: 11 / 26 abgeschlossen.
17. Kapitel 17 – Schwer: 1 / 26 abgeschlossen.
18. Sonstige Übungen: 2 vollständig.

C++ Gesamt: 81 Lösungen abgeschlossen.

Python-Lösungen:

0. Python-Unit-Tests
1. Kapitel 1 – Arrays und Strings: 9 / 9 abgeschlossen.
2. Kapitel 2 – Verknüpfte Listen: 8 / 8 abgeschlossen.
3. Kapitel 3 – Stapel und Warteschlangen: 6 / 6 abgeschlossen.
4. Kapitel 4 – Bäume und Grafiken: 11 / 12 abgeschlossen.
5. Kapitel 5 – Bit-Manipulation: 7 / 8 abgeschlossen.
6. Kapitel 6 – Mathematik und Logik: 0 / 10 abgeschlossen.
7. Kapitel 7 – Objektorientiertes Design: 0 / 12 abgeschlossen.
8. Kapitel 8 – Rekursion und dynamische Programmierung: 11 / 14 abgeschlossen.
9. Kapitel 9 – Systemdesign und Skalierbarkeit: 0 / 8 abgeschlossen.
10. Kapitel 10 – Sortieren und Suchen: 1 / 11 abgeschlossen.
11. Kapitel 11 – Tests: 0 / 6 abgeschlossen.
12. Kapitel 12 – C und C++: N/A
13. Kapitel 13 – Java: N/A
14. Kapitel 14 – Datenbanken: 0 / 7 abgeschlossen.
15. Kapitel 15 – Gewinde und Schlösser: N/A
16. Kapitel 16 – Mittel: 2 / 26 abgeschlossen.
17. Kapitel 17 – Schwer: 3 / 26 abgeschlossen.

Python Total: 58 Lösungen abgeschlossen.

Gesamtsumme: 139 einzigartige Lösungen abgeschlossen.

Gebäude:

Mac:

Für die Mac-Nutzung ist die Installation der Paketmanager Homebrew und Pip erforderlich, was im Makefile für Sie erledigt wird:

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

Ubuntu:

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

Windows:

Für Windows-Benutzer empfehle ich, dieses Projekt mit der Windows-Subsystem-für-Linux-Funktion (WSL) von Windows 10 zu entwickeln und dann den Ubuntu-Build- und Testanweisungen in WSL zu folgen. Diese Empfehlung ist auf die Verwendung von Ubuntu, CMake und Makefile-basierten Build- und Ausführungssystemen auf den Servern zurückzuführen, die Änderungen am Code automatisch testen. Weitere Informationen zur Windows-Entwicklung finden Sie im Appendix am Ende dieser Seite.

Testen:

Das Testen ist der wichtigste Teil dieses Projekts: Nur die Unit-Tests definieren das zu lösende Problem. Führen Sie im Stammverzeichnis Folgendes aus, um alle Tests in Python und C++ auszuführen:

 make test

make test ist der Befehl, den ich bei der Entwicklung dieses Projekts am häufigsten verwende. Mein Arbeitsablauf ist wie folgt:

1. Ich lese ein Problem und kodiere die Problemdefinition, indem ich die zugehörigen Komponententests umsetze.
2. Ich führe make test aus, um zu sehen, wo das Projekt die Unit-Tests nicht erfüllt.
3. Ich füge die Implementierung der Problemlösung hinzu, bis make test erfolgreich ist.

Optional: Lokales Generieren eines Berichts zur Testabdeckung % (nur Python-Unterstützung):

Dadurch wird genau angezeigt, welche Zeilen in den einzelnen Python-Quelldateien nicht von Tests abgedeckt werden:

 pip install coverage
make test_coverage

Mitwirken

Ziel dieses Projekts ist es, für jedes Problem der 6. Auflage des Lehrbuchs eine getestete Python- und C++-Lösung zu schreiben. Ich brauche auf jeden Fall Hilfe, daher sind PRs willkommen. Es gibt viel zu tun, da jede Lösung zum Testen einen eigenen kleinen Datensatz und eine eigene Infrastruktur benötigt. Hier sind einige Möglichkeiten, wie Sie helfen können:

1. Fehler beheben?
2. Lösen oder Verbessern von Lösungen für Probleme in beiden Sprachen (siehe den Fertigstellungsfortschritt im Inhaltsverzeichnis).
3. Hinzufügen weiterer Komponententests, um die Testabdeckung in % zu erhöhen.
4. Implementierung einer automatisierten C++-Testabdeckungsmessung mit gcov.
5. Integration automatisierter Testabdeckungsprozentsatzberichte für Python und C++ über Coveralls.
6. Hinzufügen prosaischer Lösungsbeschreibungen für Probleme, bei denen diese nicht vorhanden sind.

Wenn Sie Beiträge haben, senden Sie bitte eine PR an die master -Zweigstelle. Zur Klärung der oben genannten Punkte können Sie mir gerne eine Nachricht senden.

Anhang: Windows-Entwicklung

Auf meinem eigenen Windows-Rechner entwickle ich mit CLion, das nativ in Windows läuft, und teste den Code mit make test in einem WSL-Terminalfenster. Für Benutzer, die WSL nicht verwenden möchten, habe ich die folgende Build- und Testmethodik entwickelt:

Gebäude

Das Projekt kann mit Visual Studio 2017 rein unter Windows ohne WSL entwickelt werden. Klonen Sie zunächst den Code:

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

Installieren Sie dann Python3 und Numpy mit der Methode Ihrer Wahl. Ich bevorzuge die Installation von Python3 und pip3 von der offiziellen Website als die Installation von numpy über pip:

 pip install numpy

Öffnen Sie dann das Projekt in Visual Studio 2017, das CMake-Unterstützung bietet. Ich habe festgestellt, dass der beste Arbeitsablauf darin besteht, Visual Studio zum Bearbeiten von Code und zur Nutzung der Debugging-Funktionalität zu verwenden. Bevor Sie den Code erstellen, müssen Sie diese Anweisungen befolgen, um Visual Studio anzuweisen, die benötigten PDBs herunterzuladen. Darüber hinaus wird in diesem Artikel die Unterstützung von Visual Studio CMake ausführlicher beschrieben, falls Sie interessiert sind. Eine CMakeSettings.json-Datei im Stammverzeichnis des Projekts legt den Speicherort des Visual Studio-Build-Ordners so fest, dass er sich im Stammordner des Projekts befindet.

Testen

Das Ausführen der Tests und das Anzeigen ihrer Ausgabe erfolgt am besten über ein PowerShell-Fenster, da VisualStudio im CMake-Modus nicht zulässt, dass die Konsolenausgabe der Dateien tests.exe und tests.py sichtbar bleibt, selbst wenn STRG + F5 gedrückt wird, wie in diesem Beitrag beschrieben gilt für die „normale“ Visual Studio-Nutzung. Ich beobachte die Situation in Bezug auf Visual Studio und wenn ich bessere Lösungen finde, werde ich sie implementieren oder veröffentlichen. Wenn Sie etwas Besseres wissen, kontaktieren Sie mich bitte.

In der Zwischenzeit können Sie im Stammverzeichnis des Projekts die Python-Tests mit ... ausführen.

 python tests.py

... und Sie können die C++-Tests ausführen mit ...

 .buildx64-Debugtests.exe