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)

[SuperBidi]

C'était pour être sûr. A titre informatif, je mets le code que j'ai fait.

Code java :

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
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
interface Dictionary
{
    public boolean wordExist(String word);
    public boolean wordBeginWith(String word);
}
 
public Vector<String> myMethod(Dictionary dictionary, char array[][])
{
    Vector <String> result = new Vector<String>();
    for (int i = 0; i < array.length; i++)
    {
        for (int j = 0; i < array[i].length; j ++)
        {
            result.addAll(recurseOnArray(dictionary, array, “”, i, j));
        }
    }
    return result;
}
 
public Vector<String> recurseOnArray(Dictionary dictionary, char array[][], String word, int i, int j)
{
    Vector<String> result = new Vector<String>();
 
    if (array[i][j] == “ “)
        return result;
    word = word + array[i][j];
    if (dictionary.wordExist(word))
        result.add(word);
    if (!dictionary.wordBeginWith(word))
        return result;
 
    if (i > 0)
        result.addAll(recurseOnArray(dictionary, array, word, i - 1, j);
    if (i < array.length - 1)
        result.addAll(recurseOnArray(dictionary, array, word, i + 1, j);
    if (j  >0)
        result.addAll(recurseOnArray(dictionary, array, word, i, j - 1);
    if (j < array[i].length - 1)
        result.addAll(recurseOnArray(dictionary, array, word, i, j + 1);
 
    return result;
}

Merci pour ton aide.
Ca m'ennuie quand même, parce qu'au final, je ne sais ce que j'ai raté durant l'entretien. C'est assez désagréable.

[acx01b]

Moi ça me parait bien !

Tu as dit que dictionnary était un arbre 26-n-aire ?

Et tu repasses par la même case plusieurs fois dans le même mot, c'est probablement ça qui les a dérangé ? Il faut un flag pour dire que tu es déjà passé par la case (tu peux écrire " " mais il faut remettre la lettre avant le return result)


Ensuite j'aurais remplacé public boolean wordBeginWith(String word); par

Code :

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

public Dictionnary GetSubDictionnaryBeginWith(char letter); // renvoie null si aucun sous-mot ne commence par letter

Pour la complexité ben c'est pas évident.
Si on note Nb(n) le nombre de débuts de mots à n lettres valides (GetSubDictionnaryBeginWith non nul) que l'on peut construire avec le tableau (le même début de mot peut être compté plusieurs fois), alors la fonction recurseOnArray récursif est appelée M = Nb(1)+Nb(2)+ Nb(3) .... fois, et c'est clairement ce nombre qui détermine le temps d'exécution de l'algo (algo qui peut être parallélisable dans ce cas on divise par le nombre de cœur).
On peut aussi majorer M par N! / (N-25)! < N^25 où N est le nombre du case du tableau, ou mieux par N 4^25, ce qui laisse entre que l'algo est en O(N), sauf que pour que ça soit "vrai" il faut que N soit beaucoup plus grand que 4^25 car sinon M est beaucoup plus petit que 4^25 et alors dire que M < N 4^25 devient peut intéressant.

[acx01b]

Ensuite viennent les heuristiques :

Après si le but est de trouver le mot le plus long,
on peut noter dans le dictionnaire pour chaque sous-arbre la taille du mot le plus long (le sous-arbre correspondant à "anticons" a une taille max de 25)
et on peut s'enfoncer dans l'arbre en priorité dans les sous-arbres qui ont une taille max maximum..
Si le but est de trouver le maximum de mots en un temps le plus courts possible, on peut noter dans le dico le nombre de mots de chaque sous-arbre, et s'enfoncer en priorité dans le sous-arbre avec le plus de mots.

[SuperBidi]

Comme annoncé dans l'énoncé, on ne s'occupe pas du dictionnaire. C'est toujours ce qui paraît le plus intéressant, mais le gars voulait pas.
Donc optimiser le dico n'a pas d'utilité ^^
Ensuite, comme indiqué dans l'énoncé, on a le droit de repasser par une case par laquelle on est déjà passé.

Et pour finir, la complexité est majorée par O(taille du tableau * 4 ^ longueur du mot le plus long dans le dico).
Ce qui équivaut à un O(taille du tableau), même si je trouve que 4 ^ 26 est bien grand pour être juste appelé C.