Algorithm / Data Structure Design Questions d’entretien

J’apprécie le classique “Quelle est la différence entre une LinkedList et une ArrayList (ou entre une liste liée et un tableau / vecteur) et pourquoi choisiriez-vous l’une ou l’autre?”

Le type de réponse que j’espère est celui qui comprend la discussion de:

• performance d’insertion
• performance d’itération
• Impact de l’allocation / réallocation de la mémoire
• impact de la suppression d’éléments du début / milieu / fin
• Comment savoir (ou ne pas savoir) la taille maximale de la liste peut affecter la décision

Une fois quand j’interviewais pour Microsoft au collège, le gars m’a demandé comment détecter un cycle dans une liste chaînée.

Après avoir discuté en classe la semaine précédente de la solution optimale au problème, j’ai commencé à lui dire.

Il m’a dit: “Non, non, tout le monde me donne cette solution. Donnez-moi une autre solution.”

J’ai soutenu que ma solution était optimale. Il a dit: “Je sais que c’est optimal. Donnez-moi un sous-optimal.”

En même temps, c’est un très bon problème.

Lors d’interviews récentes, on m’a souvent demandé d’implémenter une structure de données, généralement LinkedList ou HashMap. Les deux sont assez faciles à faire en peu de temps et assez difficiles à éliminer.

Cela ne concerne pas nécessairement les capacités de la POO, mais lors de notre dernière série d’entretiens, nous avons utilisé une sélection de codes de bug de la liste Bug of the Month . Regarder les candidats trouver les bugs montre leurs capacités d’parsing, montre le savoir interpréter le code de quelqu’un

1. Écrivez une méthode qui prend une chaîne et renvoie true si cette chaîne est un nombre (tout ce qui correspond à regex est la réponse la plus efficace pour une interview)
2. Veuillez écrire une méthode de fabrique abstraite, qui ne contient pas de commutateur et renvoie les types avec le type de base “X”. (À la recherche de motifs, à la recherche de reflection, à leur recherche de pas de côté et à utiliser un if else if)
3. Veuillez séparer la chaîne “every; thing |; | else |; | in |; | he; re” par le jeton “|; |”. (Les jetons multi-caractères ne sont pas autorisés au moins dans .net, la meilleure solution est un hack total)

Les graphes sont difficiles, car la plupart des problèmes de graphismes non sortingviaux ont tendance à exiger une quantité décente de code à implémenter, si plus qu’une esquisse d’algorithme est requirejse. Une grande partie a tendance à se résumer à savoir si le candidat connaît ou non le chemin le plus court et les algorithmes de parcours graphique, s’il est familiarisé avec les types de cycles et la détection, et s’il connaît les limites de complexité. Je pense que beaucoup de questions sur ce sujet se résument à des questions plus que sur la capacité de reflection créative sur le terrain.

Je pense que les problèmes liés aux arbres ont tendance à couvrir la plupart des difficultés des questions sur les graphiques, mais sans la complexité du code.

J’aime le problème du projet Euler qui demande de trouver le chemin le plus cher dans un arbre (16/67); ancêtre commun est un bon échauffement, mais beaucoup de gens l’ont vu. Demander à quelqu’un de concevoir une classe d’arborescence, d’effectuer des parcours et de déterminer à partir de quelles traversées ils pourraient reconstruire une arborescence donne également un aperçu de la structure des données et de l’implémentation des algorithmes. Le défi de la programmation Stern-Brocot est également intéressant et rapide à développer sur un tableau ( http://online-judge.uva.es/p/v100/10077.html ).

J’aime revoir un code que la personne a réellement écrit et leur demander de m’expliquer.

Suivez toute question comme celle-ci avec: “Comment pourriez-vous améliorer ce code pour que le développeur qui le gère puisse comprendre comment cela fonctionne facilement?”

Implémenter une fonction qui, étant donné une liste liée qui peut être circulaire, permute les deux premiers éléments, le troisième avec le quasortingème, etc.

Une chose sortingviale est de leur demander de coder une recherche complète d’un arbre à partir de zéro. Oui, si vous savez ce que vous faites, c’est sortingvial. Mais beaucoup de programmeurs ne savent pas comment s’y prendre.

Celui que je trouve plus utile encore est le suivant. Je l’ai donné dans un certain nombre de langues, voici une version Perl. Je leur donne d’abord l’exemple de code suivant:

# @a and @b are two arrays which are already populated. my @int; OUTER: for my $x (@a) { for my $y (@b) { if ($x eq $y) { push @int, $x; next OUTER; } } } 

Ensuite, je leur pose les questions suivantes. Je leur demande lentement, donne aux gens le temps de réfléchir et je suis prêt à leur donner un coup de pouce:

1. Qu’est-ce qui est dans @int quand ce code est fait?
2. Ce code est mis en production et il existe un problème de performance qui est retracé dans ce code. Expliquez le problème potentiel de performance. (S’ils ont des difficultés, je demanderai combien de comparaisons cela prend si @a et @b ont chacun 100 000 éléments. Je ne cherche pas une terminologie spécifique, juste un retour de l’estimation de l’enveloppe.)
3. Sans code, suggérez de rendre cela plus rapide. (S’ils proposent une direction facile à coder, je leur demanderai de la coder. S’ils pensent à une solution qui entraînera le changement de @int de quelque manière que ce soit (par exemple, une commande en commun), je vous demanderai s’ils réalisent qu’ils ne devraient pas coder le correctif avant de vérifier si cela est important.)

S’ils présentent une solution légèrement (ou très) erronée, le jeu de données idiot suivant trouvera la plupart des erreurs rencontrées:

 @a = qw( hello world hello goodbye earthlings ); @b = qw( earthlings say hello earthlings ); 

J’imagine qu’environ 2/3 des candidats échouent à cette question. Je n’ai pas encore rencontré un programmeur compétent qui avait des problèmes avec lui. J’ai constaté que les personnes ayant un bon sens commun et peu de connaissances en programmation réussissent mieux que les programmeurs ordinaires ayant quelques années d’expérience.

Je suggère d’utiliser ces questions comme filtres. N’embauchez pas quelqu’un parce qu’il peut y répondre. Mais s’ils ne peuvent pas répondre à ces questions, ne les engagez pas.

En leur demandant d’écrire un algorithme récursif pour une solution itérative bien connue (par exemple, Fibonacci, etc., nous leur donnons une fonction itérative si nécessaire) et leur demandons ensuite de calculer le temps d’exécution.

La fonction récursive implique souvent une structure de données arborescente. Le nombre de fois que la personne n’a pas reconnu ce qui me déconcerte. Il devient légèrement difficile de calculer le temps d’exécution jusqu’à ce que vous puissiez voir que c’est une structure en arbre …

Je trouve que ce problème couvre de nombreux domaines. A savoir, leur capacité de lecture de code (si on leur atsortingbue une fonction itérative), leur capacité d’écriture de code (puisqu’ils écrivent une fonction récursive), leur algorithme, leur structure de données (pour l’exécution) …