IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Mathématiques Discussion :

Exercice d'entretien d'embauche


Sujet :

Mathématiques

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre actif
    Homme Profil pro
    Architecte serveur
    Inscrit en
    Septembre 2011
    Messages
    64
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Architecte serveur
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2011
    Messages : 64
    Par défaut Exercice d'entretien d'embauche
    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.

  2. #2
    Membre très actif

    Profil pro
    Étudiant
    Inscrit en
    Décembre 2004
    Messages
    499
    Détails du profil
    Informations personnelles :
    Âge : 39
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Décembre 2004
    Messages : 499
    Par défaut
    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.

  3. #3
    Membre actif
    Homme Profil pro
    Architecte serveur
    Inscrit en
    Septembre 2011
    Messages
    64
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Architecte serveur
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2011
    Messages : 64
    Par défaut
    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é ^^).

  4. #4
    Membre très actif

    Profil pro
    Étudiant
    Inscrit en
    Décembre 2004
    Messages
    499
    Détails du profil
    Informations personnelles :
    Âge : 39
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Décembre 2004
    Messages : 499
    Par défaut
    non je n'ai pas oublié la complexité, je te laisses la détailler (si l'algo que je t'ai proposé te convient)

  5. #5
    Membre actif
    Homme Profil pro
    Architecte serveur
    Inscrit en
    Septembre 2011
    Messages
    64
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Architecte serveur
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2011
    Messages : 64
    Par défaut
    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.

  6. #6
    Membre très actif

    Profil pro
    Étudiant
    Inscrit en
    Décembre 2004
    Messages
    499
    Détails du profil
    Informations personnelles :
    Âge : 39
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Décembre 2004
    Messages : 499
    Par défaut
    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)

Discussions similaires

  1. Comment réussir un entretien d'embauche ?
    Par Melvine dans le forum Entretien
    Réponses: 80
    Dernier message: 18/11/2013, 14h40
  2. Conseils entretien d'embauche
    Par Toby77 dans le forum Entretien
    Réponses: 17
    Dernier message: 01/04/2009, 19h48
  3. [Conseils] Entretien d'embauche à la CPAM
    Par muse19 dans le forum Entretien
    Réponses: 20
    Dernier message: 23/04/2008, 01h07
  4. Réponses: 15
    Dernier message: 05/02/2007, 11h21
  5. entretien technique embauche developpeur php/mysql
    Par eyango dans le forum Entretien
    Réponses: 2
    Dernier message: 28/11/2006, 00h52

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo