Discussion :

[screetch]

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)

[screetch]

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

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)

[screetch]

le second :

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

[screetch]

un exercice qui peut donner des résultats interessants :

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 ?

[JulienDuSud]

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...

[LittleWhite]

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.

[screetch]

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 =)

[koala01]

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:

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

<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

[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.

[JulienDuSud]

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.

[Jean-Marc.Bourguet]

utilisation de 6 pointeurs et itérer.

2 suffisent.

[JulienDuSud]

2 suffisent.

Pas faux !

[Goten]

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

[screetch]

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

[JulienDuSud]

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

[adelallave]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Luc Hermitte]

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.

[Bousk]

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 ?
edit: si on peut pas la parcourir à reculons, la parcourir une première fois pour avoir sa taille, puis aller jusque taille-5.

[JolyLoic]

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 ?

[Luc Hermitte]

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.