Exercices souvent proposés en test

C'est une chose assez commune de demander a des candidats de passer un petit test C/C++/Pseudo code pour vérifier les capacités de programmation (et voir comment un candidat résout un problème).

les entreprises ne demandent bien sur pas un code qui compile, mais juste de voir comment un candidat résout un problème, s'il emploie des solutions viables (pas d'algorithmes en n2/n3 pour des choses simples, pas 2000 lignes de code pour une fonction simple, pas d'oubli des cas particuliers, etc)

je voulais proposer ici quelques exercices (certains que je connais, d'autres que les autres utilisateurs ont surement passé/font passer) avec ce qu'on attend du résultat.

Ca peut etre interessant d'etudier ce genre de problemes pour s'entrainer, se préparer a un entretien (bien qu'en general ils ont des questions un peu différentes, enfin j'espere)

le premier exercice qu'on m'a posé :

Citation:

---

exercice : ecrire une fonction en C ou pascal ou pseudocode pour renverser une chaîne de caractères (le dernier caractère devient le premier, l'avant-dernier le second, etc)

---

le second :

Citation:

---

On a ecrit un lecteur multimédia (XMMS/WinAmp) et l'on souhaite implémenter la fonction "randomize". Ecrivez cette fonction en C/C++/Pseudo code; elle prend en entrée un tableau des chansons, et l'on peut appeler la fonction rand() qui renvoie un entier entre 1 et RAND_MAX

---

un exercice qui peut donner des résultats interessants :

Citation:

---

On a une liste simplement chainée l, non circulaire. On souhaite effacer le 5ème élément a partir de la fin. Comment ecrivez-vous ce code ?

---

Les 2 premiers exercices sont assez triviaux, mais le 3è, la liste est une simplement chainée, circulaire ou pas ?

Parce que si elle n'est pas circulaire, je ne vois pas comment on pourrait remonter à la tête... (par exemple si l'élément suivant le dernier est "null").

Parce que si elle est circulaire, ça devient trivial comme solution également.

C'est le genre de problèmes qu'on apprend à résoudre aux premiers cours d'algo quand même...

Edit: ou bien j'ai mal compris le problème et c'est l'élément size-5 qu'on veut supprimer, avec comme l pointant sur le 1er élément ? auquel cas c'est assez trivial comme solution aussi...

Les deux premiers exemple sont courant ... je me rends compte que je les ai eu. Ils sont faciles ( enfin avis personnel ).
Le troisième, je pense plus à faire du size - 5.

oui c'est non circulaire.
Pour le premier exercice, ce qu'on attend du candidat c'est de voir qu'il connait un peu le langage et quelques pieges pour ne pas faire un alog N^2. Pour le second, on attend de voir si il est capable de trouver une solution algorithmiquement acceptable (pas de N^2) et mathematiquement correcte (chaque elémenet a la meme probabilité de se retrouver partout)
evidemment, meme si ce n'est pas précisé, si il y a une fonction de la STL ou d'une bibliotheque qui sait le faire, ce n'est pas forcément ce qui est demandé.

pour le troisieme oui on souhaite enlever le 5eme élément a partir de la fin, soit l'élément a size-5

si vous avez quelques exercices vous pouvez les rajouter a la suite =)

Salut,

Ce n'était pas lors d'un entretien d'embauche, mais tous ce qui ressemble à la gestion des ruptures est parfois intéressant.

L'exercice que j'ai eu à l'époque était:

Citation:

---

Nous avons une entreprise internationnale qui dispose d'un fichier où sont repris les chiffres d'affaire de ses différentes agences sous la forme de

Code:

---

<continent> <pays> <province> <canton> <ville> <agence> <chiffre d'affaire>

---

trié dans cet ordre. (on considère, évidemment, que le chiffre d'affaire a déjà été converti en une monnaie unique)

Créez un programme qui calcule toutes les chiffres d'affaire intermédiaires (par continent, pays, province, canton, ville, agence) et le ainsi que le chiffre d'affaire global.

---

Cela n'a rien, à mon sens, de très difficile, mais il y a pas mal de gens qui préfèreraient laisser cela à d'autres :D

a propos il y a quand meme pour le troisieme (la liste simplement chainée) une solution beaucoup plus elegante que les autres, et pas si intuitive que ca.

Citation:

---

Envoyé par screetch

a propos il y a quand meme pour le troisieme (la liste simplement chainée) une solution beaucoup plus elegante que les autres, et pas si intuitive que ca.

---

Bah perso comme solutions, je vois:

utilisation de 6 pointeurs et itérer.
une fonction récursive avec un accumulateur.

La fonction récursive est plus jolie certes, mais pas plus performante pour autant, et si la liste est très longue (200k+ éléments), ça risque de pas l'faire.

Citation:

---

Envoyé par JulienDuSud

utilisation de 6 pointeurs et itérer.

---

2 suffisent.

Citation:

---

Envoyé par Jean-Marc.Bourguet

2 suffisent.

---

Pas faux ! :aie:

Pourquoi six, c'était une faute de frappe?

je pense que c'etait pour garder en memoire les 6 dernier itérateurs, pour pouvoir supprimmer le second

Citation:

---

Envoyé par screetch

je pense que c'etait pour garder en memoire les 6 dernier itérateurs, pour pouvoir supprimmer le second

---

Oui voilà, mais les 4 itérateurs du milieu sont complètement inutiles.

Je suis encore aux études, mais, si les exercices donnés en entretien sont comme ceux-là, je me réjouis :mouarf:

Citation:

---

Envoyé par screetch

un exercice qui peut donner des résultats interessants :

---

Une solution que j'ai fait, il faut déclarer 2 listes, 6e et 4e, faire avancer liste de 5, faire avancer les 3 listes en même temps jusqu'à la fin, et finalement remplacer le suivant de 6e par 4e :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

liste supprimer5emeFin(liste l) { liste sixieme, quartieme; sixieme = l; quatrieme = l.next.next; for(int i(0);i<5;i++) { l = l.next; } while(l.next != null) do { sixieme = sixieme.next; quatrieme = quatrieme.next; l = l.next; } sixieme.next = quatrieme; return sixieme; }

---

Bon courage is vous avez entretien chez Sogeti High Tech, moi c'est la semaine prochaine ;)

Oh le déterrage. Mais ça se tient.
Pour feu random_shuffle, je ne m'étais jamais posé la question de son implémentation.

Sinon, en ce moment, j'aime beaucoup faire discuter sur le code du premier exo là: https://www.x-formation.com/wp-conte...Developer1.pdf -- mais à réserver à des gens qui affirment un minimum de niveau de connaissance sur le C++ je dirai. C'est plus un sujet de conception en C++, où du recul sur les notions d'invariant et de contrat est nécessaire pour correctement appréhender tous les problèmes avec ce code.

Si t'as moins que 2 éléments, tu crash.
La solution à ce truc c'est pas juste de prendre le next en incrémentant un compteur et agir quand il atteint 5 ? :weird:
edit: si on peut pas la parcourir à reculons, la parcourir une première fois pour avoir sa taille, puis aller jusque taille-5.

Citation:

---

Envoyé par Luc Hermitte

Sinon, en ce moment, j'aime beaucoup faire discuter sur le code du premier exo là: https://www.x-formation.com/wp-conte...Developer1.pdf -- mais à réserver à des gens qui affirment un minimum de niveau de connaissance sur le C++ je dirai. C'est plus un sujet de conception en C++, où du recul sur les notions d'invariant et de contrat est nécessaire pour correctement appréhender tous les problèmes avec ce code.

---

Je suis un peu perplexe... En particulier, sur les bugs trouvés, j'ai du mal à écrire des cas de test puisqu'il s'agit de comportements indéfinis. Ou alors j'ai mal compris le terme "test case", et ce n'est pas à prendre au sens test unitaires automatisés, mais juste au sens cas qui font arriver le problème ?

C'est comme ça que je le prends: identifier les cas qui font tout planter. Ecrire des TU a un intérêt assez limité ici je trouve aussi.
Après, que je présente le code, je pose en ça en question assez ouverte: "qu'est-ce que ceci vous inspire?" Et éventuellement je rajoute: "pourriez-vous m'identifier des utilisations du code qui feraient tout planter?" avant de demander comment l'améliorer.

Je ne sais pas pour vous, mais ce genre de test algo à l'écrit, ça m'a toujours stressé.
J'ai toujours l'impression de rater l'astuce de génie que je cherche en vain, perdant un temps fou, alors qu'en fait, c'est souvent tout con.

Pour ton dernier problème, j'imagine que si j'instancie un Array de taille nulle, à la destruction de l'objet, ça plantera.
Et il y aura de toute façon des problèmes, quelle que soit la taille...

Il y a deux autres cas d'erreurs plus triviaux...

Citation:

---

Envoyé par Luc Hermitte

Sinon, en ce moment, j'aime beaucoup faire discuter sur le code du premier exo là: https://www.x-formation.com/wp-conte...Developer1.pdf -- mais à réserver à des gens qui affirment un minimum de niveau de connaissance sur le C++ je dirai. C'est plus un sujet de conception en C++, où du recul sur les notions d'invariant et de contrat est nécessaire pour correctement appréhender tous les problèmes avec ce code.

---

Par curiosité, les 4 bugs sont bien :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

{ Array<int> a(0); // m_pData non initialisé, erreur sur le delete }   while(true) { auto p = new Array(unsigned(0xffffffff)); // un jour le new (dans le ctor) echouerra p->Set(unsigned(0xfffffffe), 0); // et on écriera quelque part ou il ne faut pas }   // delete au lieu de delete[], ça peut se tester ?   // problèmes de copie / affectation { Array<int> a0(5); Array<int> a1(4); Array<int> a2(a0); // a2 pointe sur la même zone mémoire que a0. Bug ou par design ?   a1 = a0; // mémoire de a1 non libérée (bug) // a1 pointe sur la même zone mémoire que a0. Bug ou par design ?   // multiples deletes sur la même zone mémoire (bug) }

---

?
(Yen a d'autres ?)

Problèmes de design:
- réinventer la roue, std::vector existe, et fonctionne.
- getter non const.
- copie des éléments dans le getter, quelque soit leur taille ? Ça peut être assez catastrophique avec des gros éléments.
- vérification que des unsigned soient positifs : ça ne fait pas de mal en soit, mais c'est inutile.
- ctor a 1 argument non explicit : possible problème de cast.
- dtor virtuel ? Vouloir hériter d'un tableau semble bizarre.
- m_nSize pourrait être déclaré const.

Sinon, j'avais eu ce problème :
On a un tableau d'entiers, on cherche la paire des plus petits nombres uniques dans ce tableau. Même question pour la recherche d'un triplet.
Exemple: Dans [6, 2, 3, 4, 3, 9],
la paire des plus petits nombres uniques est [2, 4]
le triplet des plus petits nombres uniques est [2, 4, 6]

Pour le delete[], en formation, je le fais observer avec le sanatizer -> `CXX=clang++ CXXFLAGS="-fno-omit-frame-pointer -fsanitize=address,undefined -g" make array` (si le fichier s'appelle array.cpp).

Sinon c'est l'idée, je dirai que pratiquement l’essentiel des problèmes (profonds et non techniques) de ce code se résume à la question : "c'est quoi l'invariant de la classe ?". C'est des questions que l'auteur ne s'est pas posées (ou peut-être si justement si cela a été écrit exprès pour des tests d'évaluation/entretien). Du coup des cabrioles à coup de programmation défensive sont réalisées, et cela reste pourtant très bancal.

Il y a plus grave, je pense.
l'allocation dans le constructeur peut échouer, et la classe s'imagine quand même avoir les éléments à dispositions.

Plus subtile, delete accepte NULL, il n'y a pas lieu de le vérifier (dans le destructeur).
Plus grave, mais déjà vu: puisque get suppose que le tableau est alloué, le destructeur ne peut pas s'attendre à ce qu'il ne le soit pas.

Citation:

---

Envoyé par ternel

Il y a plus grave, je pense.
l'allocation dans le constructeur peut échouer, et la classe s'imagine quand même avoir les éléments à dispositions.

---

Invariant non maitrisé

La classe devrait avoir pour invariants:
- je suis responsable unique du buffer
- le buffer est un pointeur valide vers une zone de nb_elements elements.
- Et on peut se rajouter éventuellement le cas: ni nb_element ni buffer (redondant) ne peuvent être nuls -- à voir avec le déplacement, je ne sais pas encore trop sur quel pied danser.

Et comme tout invariants, ils sont garantis de la sortie des constructeurs à l'entrée du destructeur.

EDIT: après oui, tu as parfaitement raison. C'est juste que je range ça dans "1- spécifier l'invariant ; 2- s'assurer qu'aucun chemin ne le viole".