Dans une interview, est-il préférable de coder une solution brute-force à une question difficile, ou de passer l'entretien à examiner la question attentivement? [fermé]

14

Parfois, les questions d'entrevue sont difficiles, que l'enquêteur en ait l'intention ou non. Cela peut se résumer à choisir d'utiliser le temps d'entrevue limité pour coder une solution laide, inefficace et brutale, ou de passer le temps à comprendre chaque aspect du problème avec l'intervieweur.

Par exemple, le problème 91 du projet Euler peut être résolu par une solution de force brute pas si difficile de calculer tous les triangles possibles, d'écrire un test isRightTriangle () et de faire apparaître tous les triangles qui réussissent le test dans un ensemble. Mais les deux paires de coordonnées X / Y en font une solution O (x ^ 4) avec une valeur constante élevée. Un ami et moi venons de trouver une solution beaucoup plus élégante et efficace, mais nous y avons passé trois heures et dessiné des dizaines de diagrammes, testé plusieurs formules, examiné plusieurs approches, etc.

Toutes les questions d'entrevue ne sont pas justes. Ce qui est facile pour une personne peut aussi être difficile pour une autre. Si quelqu'un se débat avec une question, seriez-vous plus impressionné par une solution laide de force brute qui fonctionne? Ou excellente compréhension des problèmes et en route vers une solution élégante, mais pas de solution codée? Y a-t-il une règle comme après 20 minutes, vous devriez juste commencer à coder quoi qu'il arrive?

GlenPeterson
la source
10
Demandez-leur s'ils veulent une solution de force brute ou une solution nuancée.
Robert Harvey
S'ils avaient voulu une solution sans force brute, ils auraient posé une question qui ne peut pas être résolue par la force brute en premier lieu.
minSeven

Réponses:

9

Tout d'abord, une question qui prend trois heures à deux développeurs expérimentés pour être élégamment optimisée est un mauvais choix pour une question d'entrevue. Si vous le demandez, vous ne devriez pas vous attendre à des réponses parfaites.

D'un autre côté, parfois vous en apprenez le plus sur quelqu'un lorsque vous lui faites atteindre ses limites. C'est pourquoi de nombreux cours collégiaux augmentent la difficulté puis notent la courbe. Si tout le monde obtient un score de 100% à chaque examen, vous laissez beaucoup de potentiel d'apprentissage.

Mon candidat idéal ferait probablement d'abord le calcul de la complexité, en disant: «Oh, ce ne sont que 6 millions d'itérations, ce qui ne prendra pas très longtemps», puis j'écrirais rapidement la solution de force brute. Ensuite, ils discuteraient des approches qu'ils pourraient adopter pour l'optimiser, sans nécessairement les mettre en œuvre à moins que l'enquêteur ne le leur demande.

En partie, cela est dû au fait que la plupart des problèmes de type euler du projet qui surviennent dans le monde réel sont des problèmes ponctuels que vous devez résoudre une fois puis l'oublier. Je veux savoir qu'une personne que j'engage sera en mesure de reconnaître un algorithme de force brute qui prend 2 minutes pour écrire et 10 minutes pour exécuter est plus efficace qu'un algorithme qui prend 3 heures pour écrire et 10 secondes pour exécuter, si vous avez seulement besoin pour l'exécuter qu'une seule fois.

Karl Bielefeldt
la source
Très bonne réponse. Caleb a évoqué le concept de la force brute d'abord puis de l'optimisation, mais la vôtre est la seule réponse qui suggère de fournir la raison pour laquelle une solution de force brute est acceptable dans ce cas: "Cela ne représente que 6 millions d'itérations, ce qui ne prendra pas très long." C'est juste de l'or. Merci beaucoup!
GlenPeterson
14

En tant que responsable du recrutement, si je vous demande de résoudre un problème de code juste devant moi, je ne le fais pas tellement pour voir le code lui-même (bien que ce soit important) mais plutôt pour savoir comment et pourquoi tu as fait ce que tu as fait. L'une de ces choses que vous pourriez faire n'est pas de coder, et plutôt de m'interroger sur les aspects du problème lui-même, pour mieux le résoudre. C'est significatif pour moi, et généralement plus significatif que la solution présentée dans le code. Cependant, ce n'est pas ainsi que tout le monde le fait, ni ce que tout le monde veut voir (et en fait, je demande rarement aux gens de coder dans un cadre d'entrevue, mais je mets des problèmes sur la table et nous parlons à travers eux et parfois un pseudocode émerge , ce qui est tout aussi bon pour moi ).

Vous avez raison de dire que toutes les questions d'entrevue ne sont pas justes, et ce qui est facile pour quelqu'un est difficile pour une autre, dans ce contexte et avec ces contraintes, et c'est pourquoi les entretiens qui comprennent cela ne recherchent généralement pas la solution de code (bien que , encore une fois, cela joue un rôle important) mais plutôt le processus de solution .

"Y a-t-il une règle comme après 20 minutes, vous devriez juste commencer à coder quoi qu'il arrive?" Je répondrais à cela en disant qu'en très peu de temps pour réfléchir au problème, vous devriez au moins faire quelque chose - poser plus de questions, esquisser un cadre pour une solution, ou dire que vous ne pouvez pas le faire / Je ne sais pas par où commencer.

Si je mets un problème difficile devant vous et que la solution que vous avez fournie - compte tenu des contraintes de temps et qu'avez-vous - était la force brute et laide, je vous poserais alors une série de questions pour expliquer pourquoi c'était le cas, et qu'est-ce qui le changerait en quelque chose de plus élégant: plus d'informations? plus de temps? un environnement différent? Être conscient de soi et en contact avec le pourquoi de ce que vous avez fait et ce que vous n'avez pas fait, et être capable de l'expliquer rationnellement, est une grande étoile d'or dans mon livre, mais ce sont les types de développeurs que je chercher. Donc, "une excellente compréhension des problèmes et une solution élégante" fonctionneraient aussi pour moi, mais pas pour tout le monde.

jcmeloni
la source
6
Plus un million pour "Etre conscient de soi et en contact avec le pourquoi de ce que vous avez fait et de ce que vous n'avez pas fait, et être capable de l'expliquer rationnellement, est une grande étoile d'or dans mon livre" . Le nombre de personnes qui, lorsqu'on leur a demandé "Pourquoi?", Juste fondateur et ne peut pas répondre est incroyable. Lors de l'embauche, je préférerais presque toujours apprendre à quelqu'un à coder qui peut penser par lui-même plutôt que d'embaucher quelqu'un qui peut coder mais ne peut pas penser.
Ben
Merci. C'est perspicace. Ma tendance dans mon travail est d'analyser avant de toucher le clavier. Mais sous la pression d'une interview, je veux désespérément montrer une solution programmers.stackexchange.com/questions/178075/… Votre réponse fournit un joli contre-exemple à retenir.
GlenPeterson
4

Je voudrais les deux, mais ils peuvent afficher un "code qui fonctionne" dans une seule solution et éventuellement discuter des solutions potentielles pour améliorer l'un ou l'autre problème.

Si vous demandez à quelqu'un d'écrire du code et qu'il souhaite simplement parler de solutions possibles avec zéro code, ce serait une préoccupation.

Comme vous l'avez dit, quelqu'un peut avoir du mal avec le problème particulier pour une raison quelconque, mais vous devez apprendre comment il procède pour le résoudre. Ils pourraient avoir de la chance et ont déjà entendu parler d'une solution à un problème similaire. Ça arrive.

Regardez quelqu'un écrire assez de code et en discuter et vous pouvez déterminer s'il est approprié pour le travail.

JeffO
la source
1
Je suppose que je voudrais également savoir pourquoi la solution de force brute peut être un problème, comme dans la question ci-dessus.
Christopher Creutzig
@ChristopherCreutzig - J'ai supposé qu'il serait difficile d'offrir des améliorations sans au moins suggérer les problèmes de la solution actuelle.
JeffO
Vrai. Je suppose que je vais rayer ça.
Christopher Creutzig
3

Y a-t-il une règle comme après 20 minutes, vous devriez juste commencer à coder quoi qu'il arrive?

Non, mais si vous passez 20 minutes à analyser le problème avant de vous lancer dans les affaires, vous avez probablement déjà des ennuis. Un employeur qui vous pose une question comme celle que vous avez citée est principalement intéressé par la façon dont vous abordez un problème, mais s'il le pose comme un problème de codage, il voudra également voir du code. Parlez-leur de votre processus de réflexion ...

Eh bien, l'approche évidente ici est la force brute. Si j'avais un moyen de reconnaître un triangle rectangle étant donné les trois sommets, je pourrais parcourir toutes les combinaisons de deux points et l'origine à la recherche de triangles rectangles. Cela ne devrait pas être difficile - je peux écrire une fonction qui utilise le théorème de Pythagore pour identifier les triangles rectangles. Pour faciliter cela, je vais également écrire une fonction qui détermine la distance entre deux points en utilisant la formule de distance ...

L'écriture de ces fonctions devrait prendre environ trois minutes. Maintenant, après quelques minutes seulement, vous avez déjà montré que vous vous souvenez de la géométrie de base et que vous savez vraiment comment écrire du code. Cela vous donne également de quoi parler:

Ainsi, nous pourrions évidemment mettre la isRightTriangle(p1, p2, p3)fonction au milieu de quatre forboucles et parcourir tous les choix possibles pour chacun des deux points variables. Voyons voir ... le problème demande le nombre de triangles rectangles incluant l'origine sur une grille 50x50, donc l'utilisation de la méthode de la force brute nous fait vérifier 50 possibilités pour chaque coordonnée de chaque point. C'est 50 ^ 4 contrôles ... Je suis sûr que nous pouvons faire mieux, mais le code est évident, alors laissez-moi l'écrire ...

Alors maintenant, vous écrivez une fonction qui utilise des forboucles imbriquées et la isRightTriangle()fonction que vous venez d'écrire. Vous avez résolu le problème, mais vous avez également laissé l'intervieweur voir où vous allez. Si leur objectif était simplement de voir que vous pouvez écrire du code, ils pourraient vous dire d'arrêter. Plus probablement, ils sont heureux de parler à quelqu'un qui sait ce qu'ils font et ils voudront voir jusqu'où vous allez. Alors vous continuez ...

Il m'est venu à l'esprit pendant que j'écrivais que nous pouvons profiter de la symétrie. Nous pouvons refléter n'importe quel triangle rectangle donné autour de la ligne de 45 °, donc si nous choisissons de vérifier l'un des points uniquement d'un côté de cette ligne, nous pouvons simplement compter les triangles rectangles que nous trouvons deux fois ... une fois pour le triangle et une fois pour sa réflexion. Cela réduit de moitié le nombre de contrôles. De plus, en le regardant maintenant, nous prenons une racine carrée pour trouver la distance entre deux points, mais ensuite nous la remettons au carré dans isRightTriangle()...

Etc. Encore une fois, ils ne veulent généralement pas voir une solution parfaite, ils veulent voir comment vous obtenez une solution. Votre processus de réflexion ne doit pas nécessairement ressembler à celui ci-dessus - le simple fait d'avoir la confiance nécessaire pour penser à haute voix comptera beaucoup. Ne vous inquiétez pas si vous faites une erreur - dites simplement "hmmm, je pense que j'ai déraillé ici - laissez-moi revenir en arrière ..."

Caleb
la source
1
Très belle réponse. J'aime particulièrement: "Je suis sûr que nous pouvons faire mieux, mais le code est évident, alors laissez-moi le noter ..."
GlenPeterson
3

En tant que manager, si je vous demande de coder comme test, je suis surtout intéressé par:

  • Si vous pouvez écrire du code
  • Votre style de codage
  • L'algorithme que vous avez sélectionné
  • La tentative indique-t-elle que vous avez compris le problème
  • Si je suis vraiment passionné par une technologie spécifique, avez-vous démontré que vous la connaissiez plus ou moins.

Le premier élément peut sembler fou, mais vous seriez surpris ...

Style de codage - par cela, je ne veux pas seulement dire où vous mettez vos accolades, mais des choses comme:

  • Avez-vous choisi la composition ou l'héritage pour résoudre ce problème? Pourquoi?
  • Pour cette valeur, pourquoi avez-vous choisi d'utiliser une énumération par rapport à une chaîne par rapport à un int (ou toute autre permutation applicable)
  • Avez-vous utilisé des propriétés, des champs ou des méthodes get / set pour cette valeur? Pourquoi?
  • Comment avez-vous géré l'état dans vos cours?
  • Comprenez-vous comment l'héritage, les interfaces et les lambdas fonctionnent?
  • Comprenez-vous les conventions des paramètres du langage (qu'est-ce que par référence vs par valeur?)
  • Savez-vous comment écrire des tests unitaires?

Voici ce que je vraiment ne me soucie de:

  • Qu'il compile (en supposant que je viens de vous donner un bloc-notes et pas de compilateur)
  • Que vous connaissiez de mémoire l'ordre de ces 2 paramètres dans cette fonction
  • Que vous pouvez réciter une chaîne de connexion SQL Server ou Oracle par cœur
  • Que vous pouvez parfaitement coder pendant que je me tiens par-dessus votre épaule en regardant chaque erreur.

En toute honnêteté, je n'ai jamais été un grand fan des tests de codage - sauf en tant qu'outil d'analyse du style.

JMarsch
la source
1
Je ne suis pas non plus très fan des tests de codage. Les problèmes du projet Euler sont des casse-tête intéressants et un excellent moyen de développer des compétences en résolution de problèmes. Mais si vous écrivez principalement des applications CRUD, il est préférable de savoir si un candidat sait comment écrire de bonnes requêtes DB ou, si vous êtes dans le monde .NET comme moi, comment utiliser correctement des choses comme MVC, WCF, WPF et LINQ.
jfrankcarr
1
J'ajouterais à ce commentaire que même la sémantique n'a pas d'importance plutôt que de comprendre quel genre de problèmes ces choses résolvent, quand et où elles comptent et les inconvénients qu'elles entraînent.
Rig
@jfrankcarr - comment déterminez-vous si quelqu'un peut écrire sql sans un test quelconque?
JeffO
1
@JeffO - J'aime généralement le faire en ayant une conversation à ce sujet en fonction de leur CV ou de scénarios courants. Par exemple, "Avez-vous utilisé des variables de table ou des tables temporaires dans vos requêtes?" ou "Comment avez-vous intégré les requêtes de données héritées dans la conception de votre nouvelle application?" Je peux avoir recours à des tests si j'embauche un programmeur débutant, mais je préfère l'approche de conversation ouverte.
jfrankcarr
1

Dans ce cas, une avancée vers une solution élégante est meilleure qu'une solution pire mais complète. Les deux cas sont bons cependant. C'est tout à fait correct d'avoir écrit un pusdocode démontrant que vous comprenez le problème et comment vous comptez le résoudre même si vous n'avez pas eu le temps de coder le programme.

Tom Squires
la source
1

Je pense que vous posez une question pour laquelle il n'y a en fait pas de réponse, encore moins une «bonne» réponse. La raison pour laquelle je dis cela est que cela dépend entièrement de ce que la personne qui pose la question évalue.

Il est possible que l'intervieweur soit un pragmatiste inconditionnel qui cherche vraiment à faire en sorte que quelque chose fonctionne rapidement, puis à optimiser en tant qu'activité de moindre priorité si vous avez du temps. Il est également possible que l'intervieweur fasse sa meilleure impression des pratiques d'embauche de Google et ne s'intéresse à rien d'autre qu'à l'algorithme le plus sexy et le plus élégant et le prenne comme un signe de faiblesse que vous auriez jamais mis les mots "brute" et " force "à moins de 5 mots l'un de l'autre. Il est tout aussi possible que l'intervieweur ait recherché des «questions d'entrevue» sur Google et ait trouvé ce problème sur Internet 5 minutes avant votre arrivée et qu'il ne sache pas ce qu'il veut.

Dans tous les cas, votre meilleur pari est probablement de demander des éclaircissements, si vous ne pouvez pas déduire sur la base d'informations contextuelles ce que l'intervieweur veut. Vous avez raison de dire que toutes les questions d'entrevue ne sont pas justes et, en fait, toutes ne sont pas de bonnes questions ou même des questions qui ont du sens. Une entrevue est une activité intrinsèquement réductionniste, un peu comme le "speed dating" où vous passez une heure ou deux avec quelqu'un et que vous essayez de deviner, sur la base de cette heure, si vous travaillerez bien ensemble pour la prochaine 5 ans ou pas. Examiné de ce point de vue, j'espère que vous comprendrez plus clairement pourquoi je dis qu'il n'y a vraiment pas de réponse à votre question sur une «règle».

Quelqu'un vous pose une question qui, selon lui, vous donnera un aperçu de vos compétences et de sa compatibilité avec leur équipe. Vous devez regarder leur équipe, ce que vous savez à leur sujet, la personnalité de l'intervieweur et des dizaines d'autres facteurs, et faire une meilleure estimation des réponses, de l'approche et du processus qu'ils seraient susceptibles d'apprécier. Personnellement, je dirais que vous devriez l'aborder de la manière qui vous semble la meilleure. S'ils ne sont pas d'accord avec vous, cela pourrait ne pas être de toute façon un bon ajustement - plus facile à comprendre plus tôt que plus tard.

Erik Dietrich
la source
0

Les enquêteurs vous demanderont de toute façon d'améliorer votre solution.

Et l'approche «brute force solution first» a un avantage indiscutable: si vous n'arrivez pas à trouver une solution idéale, vous avez encore quelque chose à faire pour les montrer.

vortexwolf
la source
1
"Les enquêteurs vous demanderont de toute façon d'améliorer votre solution.". Cela me semble un pari.
Craige
1
@Craige: Pas vraiment. Mais s'ils n'en parlent pas. Dites qu'il s'agit d'une solution de force brute et que l'analyse peut être améliorée.
Martin York