cracking the coding interview

Décrypter les solutions d'entretien de codage avec des tests unitaires automatisés

• ✅Solutions C++
• ✅Solutions Python
• ✅ Tests unitaires automatisés
• ✅ Développement actif
• ✅ Prise en charge multiplateforme : Mac, Linux et Windows

Introduction

Ce dépôt contient des solutions C++ et Python pour Cracking the Coding Interview 6th Edition de Gayle Laakmann McDowell. Certes, il existe d'autres référentiels GitHub proposant des solutions pour ce livre. Mais comment savoir si leur code est réellement correct ? Si ce n’est pas testé, alors vous ne le faites pas !

Dans ce projet, chaque solution C++ dispose de tests unitaires utilisant le framework C++ Catch, et chaque solution Python dispose de tests unitaires utilisant le framework Python unittest. Nous appliquons automatiquement l'exactitude des tests à l'aide de serveurs d'intégration continue, garantissant que les solutions sont constituées de code évolutif qui est exécuté et testé à chaque validation. À ma connaissance, il s'agit du seul référentiel de solutions sur Internet offrant ce niveau de rigueur en matière de tests : une couverture de tests automatisés >90 % signifie que vous pouvez référencer et contribuer à des solutions en toute confiance.

Table des matières

Solutions C++ :

0. Tests unitaires C++
1. Chapitre 1 - Tableaux et chaînes : 9 / 9 terminé.
2. Chapitre 2 - Listes chaînées : 8 / 8 terminées.
3. Chapitre 3 - Piles et files d'attente : 4 / 6 terminé.
4. Chapitre 4 - Arbres et graphiques : 11 / 12 terminé.
5. Chapitre 5 - Manipulation des bits : 7 / 8 terminé.
6. Chapitre 6 - Mathématiques et logique : 0 / 10 terminé.
7. Chapitre 7 - Conception orientée objet : 0 / 12 terminé.
8. Chapitre 8 - Récursivité et programmation dynamique : 8 / 14 terminé.
9. Chapitre 9 - Conception et évolutivité du système : 0 / 8 terminé.
10. Chapitre 10 - Tri et recherche : 10 / 11 terminé.
11. Chapitre 11 - Tests : 0 / 6 terminé.
12. Chapitre 12 - C et C++ : 10 / 11
13. Chapitre 13 - Java : N/A
14. Chapitre 14 - Bases de données : 0 / 7 terminé.
15. Chapitre 15 - Threads et verrous : 0 / 4 terminé.
16. Chapitre 16 – Modéré : 11 / 26 terminé.
17. Chapitre 17 – Difficile : 1 / 26 terminé.
18. Exercices divers : 2 complets.

C++ Total : 81 solutions terminées.

Solutions Python :

0. Tests unitaires Python
1. Chapitre 1 - Tableaux et chaînes : 9 / 9 terminé.
2. Chapitre 2 - Listes chaînées : 8 / 8 terminées.
3. Chapitre 3 - Piles et files d'attente : 6 / 6 terminé.
4. Chapitre 4 - Arbres et graphiques : 11 / 12 terminé.
5. Chapitre 5 - Manipulation des bits : 7 / 8 terminé.
6. Chapitre 6 - Mathématiques et logique : 0 / 10 terminé.
7. Chapitre 7 - Conception orientée objet : 0 / 12 terminé.
8. Chapitre 8 - Récursivité et programmation dynamique : 11 / 14 terminé.
9. Chapitre 9 - Conception et évolutivité du système : 0 / 8 terminé.
10. Chapitre 10 - Tri et recherche : 1 / 11 terminé.
11. Chapitre 11 - Tests : 0 / 6 terminé.
12. Chapitre 12 - C et C++ : N/A
13. Chapitre 13 - Java : N/A
14. Chapitre 14 - Bases de données : 0 / 7 terminé.
15. Chapitre 15 - Threads et verrous : N/A
16. Chapitre 16 – Modéré : 2 / 26 terminé.
17. Chapitre 17 – Difficile : 3 / 26 terminé.

Python Total : 58 solutions terminées.

Grand Total : 139 solutions uniques complètes.

Bâtiment:

Mac :

L'utilisation sur Mac nécessite l'installation des gestionnaires de packages Homebrew et Pip qui se fait pour vous dans le Makefile :

 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

Fenêtres :

Pour les utilisateurs Windows, je recommande de développer ce projet à l'aide de la fonctionnalité Windows Subsystem for Linux (WSL) de Windows 10, puis de suivre les instructions de construction et de test d'Ubuntu dans WSL. Cette recommandation est due à l'utilisation de systèmes de construction et d'exécution basés sur Ubuntu, CMake et makefile sur les serveurs qui testent automatiquement les modifications apportées au code. Pour en savoir plus sur le développement Windows, consultez la section Appendix à la fin de cette page.

Essai:

Les tests sont la partie la plus importante de ce projet : seuls les tests unitaires définissent le problème à résoudre. Dans le répertoire racine, exécutez ce qui suit pour exécuter tous les tests en Python et C++ :

 make test

make test est la commande que j'utilise le plus lors du développement de ce projet. Mon flux de travail suit :

1. Je lis un problème et code la définition du problème en implémentant ses tests unitaires.
2. J'exécute make test pour voir où le projet ne parvient pas à satisfaire les tests unitaires.
3. J'ajoute à la mise en œuvre de la solution au problème jusqu'à ce que make test réussisse.

Facultatif : génération locale d'un rapport sur le pourcentage de couverture des tests (prise en charge Python uniquement) :

Cela montrera exactement quelles lignes ne sont pas couvertes par les tests dans chaque fichier source Python :

 pip install coverage
make test_coverage

Contribuer

L'objectif de ce projet est d'écrire une solution Python et C++ testée pour chaque problème de la 6e édition du manuel. J'ai vraiment besoin d'aide, donc les PR sont les bienvenus. Il y a beaucoup à faire car chaque solution a besoin de son propre petit ensemble de données et de sa propre infrastructure pour être testée. Voici quelques façons dont vous pouvez aider :

1. Correction de bugs ?.
2. Résoudre ou améliorer des solutions à des problèmes dans l'une ou l'autre langue (voir la progression dans la table des matières).
3. Ajout de plus de tests unitaires pour augmenter le % de couverture des tests.
4. Implémentation d'une mesure automatisée de la couverture des tests C++ à l'aide de gcov.
5. Intégration du rapport automatisé sur le pourcentage de couverture des tests pour Python et C++ via Coveralls.
6. Ajout de descriptions de solutions en prose pour les problèmes qui n'en ont pas.

Si vous avez des contributions, veuillez faire un PR à la branche master . N'hésitez pas à m'envoyer un message pour obtenir des éclaircissements sur l'un des éléments ci-dessus.

Annexe : Développement Windows

Sur ma propre machine Windows, je développe à l'aide de CLion fonctionnant nativement sous Windows et teste le code à l'aide de make test dans une fenêtre de terminal WSL. Pour les utilisateurs qui ne souhaitent pas utiliser WSL, j'ai développé la méthodologie de build et de test ci-dessous :

Bâtiment

Le projet peut être développé uniquement sous Windows sans WSL en utilisant Visual Studio 2017. Clonez d'abord le code :

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

Ensuite, installez Python3 et numpy en utilisant la méthode de votre choix. Je préfère installer Python3 et pip3 depuis le site officiel puis installer numpy via pip :

 pip install numpy

Ensuite, ouvrez le projet dans Visual Studio 2017 qui prend en charge CMake. J'ai trouvé que le meilleur flux de travail consiste à utiliser Visual Studio pour modifier le code et utiliser la fonctionnalité de débogage. Avant de créer le code, vous devez suivre ces instructions pour indiquer à Visual Studio de télécharger les PDB dont il a besoin. De plus, cet article décrit plus en détail la prise en charge de Visual Studio CMake si vous êtes intéressé. Un fichier CMakeSettings.json dans le répertoire racine du projet définit l'emplacement du dossier de génération de Visual Studio dans le dossier racine du projet.

Essai

Il est préférable d'exécuter les tests et de voir leur sortie à partir d'une fenêtre PowerShell, car VisualStudio en mode CMake ne permet pas à la sortie console des fichiers tests.exe et tests.py de rester visible même en appuyant sur CTRL + F5 comme décrit dans cet article qui s'applique à une utilisation "normale" de Visual Studio. Je surveille la situation concernant Visual Studio, et lorsque je trouverai de meilleures solutions, je les implémenterai ou les publierai. Si vous connaissez quelque chose de mieux, contactez-moi.

En attendant, depuis le répertoire racine du projet, vous pouvez exécuter les tests Python en utilisant...

 python tests.py

... et vous pouvez exécuter les tests C++ en utilisant ...

 .buildx64-Debugtests.exe