Discussion :

[SuperBidi]

Bonjour à tous.
Je ne sais si je suis sur la bonne section, et si je peux me permettre de faire ça, mais voila :
J'ai eu dernièrement un entretien technique avec une grosse boîte d'informatique. Et manifestement, ça ne s'est pas très bien passé, vu que je n'ai pas été retenu. Sauf que la boîte n'a pas été claire sur la raison de son refus, et ça me travaille. Je me demande si c'est du à une erreur purement technique ou à une raison autre. Donc, je voulais vous présenter l'exercice principal de cette entrevue histoire de comparer notre manière de le résoudre. C'est un classique, donc je pense que vous devriez aisément trouver un algorithme pour le résoudre.

Donc, en entrée, on a un tableau de caractères. Exemple (pas facile à aligner, désolé) :
s
h
e d
lla
bo

Vous avez soit des lettres, soit des espaces. Le but est de faire des mots en parcourant le tableau (à la boggle). Par exemple, sur ce tableau au dessus, on peut faire hello, shell, all. En gros, on parcoure le tableau de case en case en haut, bas, droite ou gauche (pas de diagonales) sans passer par un espace jusqu'à ce que ça forme un mot. On a le droit de revenir sur une case par laquelle on est passé.
De même, on a un dictionnaire qui est donné. Donc, pas besoin de le coder, il suffit juste de préciser l'interface pour l'utiliser.
Le but est de coder l'algorithme qui permette de trouver tous les mots faisables, et d'en donner la complexité.

Donc, puis je vous demander de l'aide pour trouver le(s) meilleur(s) algo(s) pour le résoudre, et ainsi dissiper ce doute qui m'assaille ?

PS : S'il existe une section plus appropriée, n'hésitez pas à déplacer le sujet.

[acx01b]

salut, je le vois comme ça :

le dictionnaire est un arbre 26-n-aire

tu lui donnes une chaîne il te renvoie le sous-arbre des mots qui commencent par cette chaîne, ou il te dit simplement si ce sous-arbre est vide ou non

tu parcours ton tableau de caractères récursivement pour énumérer tous les mots, donc tu construis tes mots en commençant par la 1ère, 2ème lettre,etc., et à chaque fois que tu ajoutes une lettre tu demandes au dictionnaire s'il y a des mots qui commencent par ce début de mot

tu sauvegardes à chaque étape la racine du sous-arbre, et du demandes au dico de rechercher dans ce sous-arbre s'il y a un sous-arbre correspondant à la lettre que tu viens d'ajouter, ça permet d'économiser quelques opérations

pour les optimisations supplémentaires je ne vois pas trop, à part dire au dictionnaire dès le départ les lettres présentes dans le tableau, ce genre de truc, mais ça ne doit être utile que si ton tableau est très grand (c'est coûteux de pré-traiter le dictionnaire qui est a priori très grand).

Je le trouve pas mal cet exo parce que la solution que je propose se code en 20 lignes + 10 lignes pour le dictionnaire, mais prouver et se prouver que cette solution est bonne n'est pas si évident donc déstabilise forcément pas mal de candidats pas trop sûrs d'eux.

[SuperBidi]

Je trouve aussi que c'est un exo très classique. Du genre sympa à résoudre, et qui permet de tout de suite voir si un codeur maîtrise ses bases.
Par contre, tu as oublié la partie complexité (c'est la moitié de l'exo, la complexité ^^).

[acx01b]

non je n'ai pas oublié la complexité, je te laisses la détailler (si l'algo que je t'ai proposé te convient)

[SuperBidi]

En fait, je te demande la complexité pour comparer avec l'algo que j'ai proposé pendant l'entretien.
Parce que le coeur de l'algo, tu le résumes en 2 lignes : "tu parcours ton tableau de caractères récursivement pour énumérer tous les mots, donc tu construis tes mots en commençant par la 1ère, 2ème lettre,etc., et à chaque fois que tu ajoutes une lettre tu demandes au dictionnaire s'il y a des mots qui commencent par ce début de mot"
Ce qui laisse un minimum place à l'imagination ^^
Mais sinon, si le coup de la complexité t'ennuies, tu peux aussi mettre quelques lignes de pseudocode pour que je visualise mieux cette partie.

[acx01b]

tu parcours ton tableau de caractères récursivement pour énumérer tous les mots, donc tu construis tes mots en commençant par la 1ère, 2ème lettre,etc., et à chaque fois que tu ajoutes une lettre tu demandes au dictionnaire s'il y a des mots qui commencent par ce début de mot

Je ne vois pas ce que ça a d'ambigu comme description de l'algo.
- Clairement si le dictionnaire répond qu'il n'y a pas de mots qui commencent pas ce début de mot, on s'arrête (on remonte à l'appel récursif précédent qui a un début de mot différent).
- Le dictionnaire doit être organisé sous forme d'arbre 26-n-aire

ça ne te parle pas ?

Si on oublie le dictionnaire, tu sais la coder la fonction récursive qui énumère tous les mots du tableau (en respectant la règle des cases adjacentes) de disons max 8lettres ?

Code c :

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

1
2
3
4
5
6
7
8
9
10
11
12
char * tableau[6] = { /// tableau 6x6
   "abcdef",
   "ghijkl",
   "mnopqr",
   "abcdef",
   "ghijkl",
   "mnopqr"
};
 
int main() {
   EnumererRecursivement( ... );
}

l'exo c'est de coder EnumererRecursivement (qui fait des cout<< sur chaque mot construit avec la règle des cases adjacentes)