La section algorithmique avec l'écriture de code sur un tableau noir ou du papier est l'une des étapes les plus importantes d'un entretien d'embauche pour les développeurs pour obtenir un emploi dans Yandex. Nous avons décidé de parler plus en détail de la façon dont ces sections sont organisées pour aider les futurs candidats à se préparer. De plus, j'espère que beaucoup de ceux qui n'osent pas venir à Yandex pour un entretien, craignant des tests trop difficiles, après cette histoire comprendront qu'en réalité tout n'est pas si effrayant!
Nous avons donc préparé pour vous les documents suivants:
- Un concours spécial contenant des tâches similaires à celles que nous donnons pour l'entretien.
- Ce poste . Il explique pourquoi vous devez effectuer de telles sections, ainsi que comprendre toutes les tâches du concours.
- Deux vidéos dans lesquelles les tâches du concours sont triées: dans la première - la tâche est plus simple, dans la seconde - deux tâches sont plus difficiles. À partir de ces vidéos, vous découvrirez les erreurs typiques commises lors du passage dans les sections algorithmiques et lors de l'écriture du code de production.
Comment nous interviewons les développeurs
Un entretien avec n'importe quel développeur comprend plusieurs étapes:
- section préliminaire avec un recruteur;
- entretien technique sur skype;
- plusieurs sections Ă temps plein;
- derniers entretiens avec les responsables du recrutement.
À la section préliminaire, le recruteur se familiarise avec le candidat, apprend ses intérêts et ses motivations afin de comprendre quels postes il est logique de le considérer. Un entretien technique sur skype est destiné à une évaluation préliminaire des compétences d'un candidat et élimine ceux qui ne seront certainement pas en mesure de faire face aux sections à temps plein.
Sections à plein temps - la scène principale. Ce sont des sections à temps plein qui répondent à la question de savoir ce qu'un candidat peut faire. La section algorithmique est l'une des sections techniques à temps plein. En plus de l'algorithmique, il existe d'autres tests en face à face: par exemple, les candidats aux développeurs seniors doivent passer par la section architecture, et les futurs leaders répondront également aux questions sur la gestion des équipes et des projets. En général, si un candidat possède une force dans un domaine spécifique (apprentissage automatique, optimisation de bas niveau, développement de systèmes très chargés, développement mobile, ou tout autre), nous organiserons une section avec un spécialiste spécialisé.
La section algorithmique vérifie si le candidat est capable de proposer des algorithmes pour résoudre des problèmes simples, évaluer la complexité de ces algorithmes et les implémenter sans erreurs, tout en maintenant un équilibre entre la qualité des tests et la vitesse de la solution.
Pourquoi Ă©crire du code sur un tableau noir ou du papier
Un état naturel pour un programmeur est la programmation dans un environnement de développement intégré avec coloration syntaxique et traçabilité. Par conséquent, l'idée lors d'une interview d'écrire du code sur un tableau noir ou du papier ne semble pas trop naturelle au départ. Cependant, cette méthode vous permet de vérifier deux propriétés très importantes pour chaque développeur.
Le premier d'entre eux est la capacité de traiter rapidement les performances du code "à l'oeil". Imaginez que lors de l'écriture de chaque cycle qui apparaît dans le programme, le développeur doit passer du temps à essayer de vérifier ses performances en traçant; ou que lorsqu'un service plante en production, il doit toujours exécuter le code sous le débogueur. Il est clair que l'écriture et le débogage de programmes même simples lui prendront un temps inacceptable. Bien sûr, il est utile de pouvoir lire le code avec des revues de code.
La deuxième propriété importante est la capacité de réfléchir à l'avance à un plan de solution et de le suivre. S'il n'y a pas de plan, cela entraînera un grand nombre de corrections, de barrages (sur papier) et de réécriture de gros morceaux de code. Dans la vraie vie, tout cela ralentit considérablement le développement, mais est partiellement masqué par la vitesse de travail dans l'éditeur de code. Le carton et le papier en ce sens sont des surfaces impitoyables.
Naturellement, nous prenons en compte que l'écriture manuelle du code n'est pas trop rapide. Par conséquent, nos tâches impliquent généralement de résoudre pas beaucoup plus d'une douzaine de lignes, et le nombre de tâches qui doivent être résolues dans une section est généralement de deux ou trois.
Sections algorithmiques et programmation sportive
La programmation sportive se développe chez le futur développeur, entre autres, et la possibilité d'implémenter rapidement et sans erreur des algorithmes simples selon un plan prédéterminé. Par conséquent, les candidats ayant de l'expérience en programmation sportive font vraiment du bon travail avec les sections algorithmiques des entretiens. Souvent, vous pouvez observer une situation où les futurs stagiaires peuvent facilement faire face à la section algorithmique, résoudre tous les problèmes en 15-20 minutes, tandis que les programmeurs plus expérimentés passent toute l'heure sur les mêmes tâches.
Dans le même temps, la section algorithmique avec l'écriture de code n'est qu'une des sections qui teste les compétences minimales nécessaires à tout développeur. Cette section sera gérée non seulement par les programmeurs de l'Olympiade, mais également par des développeurs industriels expérimentés. Le futur développeur senior ou chef d'équipe attend sûrement la section architecturale, dans laquelle il pourra révéler ses atouts; Bien sûr, cette section n'est jamais mise à la disposition des stagiaires et des développeurs juniors.
Concours de préparation à l'entrevue
Surtout pour que vous puissiez imaginer à peu près le contenu des tâches que nous donnons dans les sections algorithmiques, nous avons mis en place un concours qui peut être utilisé pour préparer les entretiens. Essayez de résoudre tous les problèmes sans exécuter le débogueur une fois; écrire une solution dans le Bloc-notes sans coloration syntaxique; trouver la solution la plus courte possible qui passera tous les tests; réfléchissez à l'avance à tous les problèmes possibles et passez la solution la première fois.
Le concours contient cinq tâches. Vous pouvez essayer de les résoudre vous-même, ou vous pouvez lire l'analyse à l'avance: elle sera toujours utile, car Vous serez en mesure de former vos compétences de codage sans erreur d'un algorithme précédemment connu.
Analyse des tâches du concoursTâche A. Pierres et bijoux
Deux lignes de caractères latins minuscules sont données: la chaîne J et la chaîne S. Les caractères inclus dans la chaîne J sont des «bijoux» et inclus dans la chaîne S sont des «pierres». Il est nécessaire de déterminer combien de personnages de S sont simultanément des «joyaux». Autrement dit, vous devez vérifier le nombre de caractères de S dans J.
Il s'agit d'une tâche d'échauffement très simple, qui comprend des solutions dans plusieurs langages de programmation, afin que les participants puissent s'habituer au système de test.
L'algorithme est assez simple: vous devez construire un ensemble à partir d'une ligne avec des "bijoux", puis suivre la ligne avec des "pierres" et vérifier chaque caractère pour l'inclure dans cet ensemble. Utiliser une telle implémentation de l'ensemble pour garantir la complexité linéaire de la solution résultante, malgré le fait que les lignes d'entrée sont très courtes et qu'il est donc possible de passer même un algorithme quadratique en complexité.
Problème B. Unités consécutives
Il est nécessaire de trouver la plus longue séquence d'unités dans le vecteur binaire et d'imprimer sa longueur.
L'algorithme de la solution est le suivant: parcourir tous les éléments du tableau; lorsque vous en rencontrez un, vous devez augmenter le compteur pour la longueur de la séquence actuelle, et lorsque vous rencontrez zéro, vous devez réinitialiser ce compteur. Au final, vous devez afficher le maximum des valeurs prises par le compteur.
Vérifiez que vous gérez la situation lorsque la matrice se termine avec la séquence d'unités souhaitée. Avec une mise en œuvre minutieuse, cette situation ne nécessite pas de traitement spécial.
Essayez d'utiliser uniquement la quantité constante de mémoire supplémentaire.
Tâche C. Suppression de doublons
Un tableau d'entiers 32 bits classés dans l'ordre non décroissant est donné. Il est nécessaire d'en supprimer toutes les répétitions.
L'algorithme correct traite séquentiellement les éléments du tableau, en les comparant avec la dernière sortie. Vous devez vous rappeler de mettre à jour la variable contenant le dernier élément affiché et, en outre, de ne pas faire d'erreur lors du traitement du dernier élément.
Pour résoudre ce problème, vous n'avez pas non plus besoin d'utiliser de mémoire supplémentaire.
Tâche D. Génération de séquences de parenthèses
Étant donné un entier . Il est nécessaire d'imprimer toutes les séquences de parenthèses correctes de longueur commandé lexicographiquement (voir https://ru.wikipedia.org/wiki/Lexographic_order ). Seules les parenthèses sont utilisées dans la tâche.
Ceci est un exemple d'un problème algorithmique relativement complexe. Nous allons générer une séquence d'un caractère; à chaque instant, on peut attribuer soit une parenthèse ouvrante soit une parenthèse fermante à la séquence courante. Vous pouvez ajouter une parenthèse ouvrante si moins de n parenthèses ouvrantes ont été ajoutées auparavant, et une parenthèse fermante si dans la séquence actuelle le nombre de parenthèses ouvrantes dépasse le nombre de parenthèses fermantes. Un tel algorithme, avec une mise en œuvre soignée, garantit automatiquement l'ordre lexicographique dans la réponse; travaille dans un temps proportionnel au produit du nombre d'éléments dans la réponse à n; cela nécessite une quantité linéaire de mémoire supplémentaire.
Un exemple d'algorithme inefficace serait le suivant: nous générons toutes les séquences de parenthèses possibles, puis nous ne sortons que celles qui s'avèrent être correctes. Dans le même temps, le volume de la réponse ne permettra pas de résoudre le problème plus rapidement que l'algorithme qui en résultera ci-dessus.
Problème E. Anagrammes
Cette tâche assez simple est un exemple typique d'un problème, pour la solution duquel il est nécessaire d'utiliser des tableaux associatifs. Lorsque vous décidez, vous devez considérer que les caractères peuvent être répétés, vous devez donc utiliser non pas des ensembles, mais des dictionnaires. Par conséquent, la solution sera la suivante: nous composons à partir de chaque ligne un dictionnaire, qui pour chaque caractère stockera le nombre de ses répétitions; puis comparez les dictionnaires résultants. S'ils coïncident, il est nécessaire d'imprimer une unité, sinon - zéro.
Solution alternative: triez les lignes d'entrée, puis comparez-les. Cette solution est pire en ce qu'elle s'exécute plus lentement et modifie également l'entrée. Mais cette solution n'utilise pas de mémoire supplémentaire.
Si lors de l'entretien vous avez eu plusieurs solutions qui diffèrent par leurs caractéristiques, parlez-nous-en. C'est toujours bien quand le développeur connaît plusieurs options pour résoudre le problème et peut parler de ses forces et de ses faiblesses.
Tâche F. Fusionner listes triées
Étant donné des tableaux d'entiers non négatifs triés par ordre non décroissant, dont chacun ne dépasse pas 100. Il est nécessaire de construire le résultat de leur fusion: un tableau trié par ordre non décroissant contenant tous les éléments de l'original tableaux. La longueur de chaque tableau ne dépasse pas 
.
Pour chaque tableau, créez un pointeur; au départ, chaque pointeur se situe au début du tableau correspondant. Nous placerons les éléments correspondant aux positions des pointeurs dans toute structure de données qui prend en charge l'extraction d'un minimum - il peut s'agir d'un multiset ou, par exemple, d'un tas. Ensuite, nous allons extraire l'élément minimum de cette structure, le mettre en réponse, déplacer la position du pointeur dans le tableau correspondant et placer l'élément suivant de ce tableau dans la structure de données.
Dans cette tâche, beaucoup ont des difficultés avec le format d'entrée. Veuillez noter que les premiers éléments des lignes ne décrivent pas les éléments des tableaux, ils décrivent les longueurs des tableaux!
FAQ du concours
R: J'ai certainement Ă©crit le bon code, mais les tests Ă©chouent; probablement une erreur en eux?
Q: Non, tous les tests sont corrects. Pensez: vous n'avez probablement pas prévu de situation inhabituelle.
R: J'écris en X, il faut définitivement plus de mémoire dans la tâche Y. Relevez les limites!
Q: Toutes les limites sont définies de manière à ce qu'une solution soit possible en utilisant l'une des langues disponibles. Essayez de vérifier si vous lisez accidentellement l'intégralité du fichier d'entrée dans des tâches avec des limites de mémoire strictes.
R: Certaines tâches peuvent être résolues beaucoup plus facilement en raison des limitations indiquées. Pourquoi tu fais ça?
Q: Nous avons spécifiquement simplifié la saisie dans certaines tâches, afin qu'il soit plus facile pour les participants de se concentrer sur la mise en œuvre de l'algorithme et de ne pas penser, par exemple, à la vitesse de téléchargement des données ou à d'autres choses importantes dans la programmation sportive. Essayez d'implémenter exactement les algorithmes que nous recommandons - ce n'est que dans cette situation que vous bénéficierez au maximum du concours.
R: Je ne veux pas réussir le concours. Je ne peux pas?
Q: bien sûr! Le concours ne lie pas tous les candidats. Cependant, je recommande toujours de le résoudre: il sera utile dans tous les cas.
R: Que recommanderiez-vous d'autre pour la préparation?
Q: Lisez nos conseils sur la page officielle sur les interviews dans Yandex: https://yandex.ru/jobs/ya-interview . J'ajouterai moi-même que la résolution de problèmes sur leetcode.com est extrêmement utile pour tout développeur pratiquant, qu'il envisage de subir une interview dans un proche avenir ou de participer à des compétitions de programmation. Même une petite quantité de pratique vous permet de vous sentir plus en confiance lorsque vous résolvez des tâches de travail.
Conclusion
J'assiste souvent à des conférences pour les développeurs et les responsables du développement, je suis membre de nombreux chats de développement, j'ai mené plusieurs centaines d'entretiens et embauché un grand nombre de développeurs sur Yandex. L'expérience suggère que les sections algorithmiques avec l'écriture de code sur un tableau ou un papier soulèvent souvent des questions. En conclusion, je répondrai aux plus populaires d'entre elles.
Pourquoi interviewer dans des conditions si différentes des conditions de travail réelles du développeur?
Cela vous permet de comprendre si le candidat est capable de trouver des problèmes dans les programmes sans démarrer le débogueur; s'il peut trouver à l'avance un plan de l'algorithme et le suivre avec précision; peut-il proposer un ensemble de tests petit mais suffisant, puis vérifier son implémentation par rapport à cet ensemble de tests.
Ces sections donnent-elles un avantage injuste aux programmeurs sportifs?
La programmation sportive développe des compétences très utiles chez les développeurs, donc les participants à la programmation des olympiades réussissent vraiment bien dans les sections algorithmiques. Il y a donc un avantage, mais c'est juste. La section algorithmique n'est que l'une des nombreuses, donc chaque candidat aura suffisamment d'occasions de montrer ses forces!
Pourquoi mener des sections algorithmiques si tous les algorithmes ont été implémentés depuis longtemps et que vous avez juste besoin de pouvoir rechercher leur implémentation dans des bibliothèques prêtes à l'emploi?
Dans les sections algorithmiques communes à tous les développeurs, nous testons uniquement les compétences minimales nécessaires: la capacité à trouver et sans erreurs pour implémenter un algorithme simple contenant des boucles, vérifier les conditions et nécessitant éventuellement l'utilisation de tableaux associatifs. Ce type de code est constamment écrit pour implémenter les services aux utilisateurs.
Quel est l'intérêt d'une section qui ne teste pas une énorme quantité de compétences de développeur?
En effet, la section algorithmique ne vérifie que l'ensemble minimal de compétences nécessaires à tout développeur. Nous testons d'autres compétences à l'aide d'autres sections.
Dirigez-vous des sections algorithmiques pour les développeurs de toutes les spécialités?
Oui Des sections algorithmiques sont destinées aux développeurs back-end, analystes, développeurs mobiles et front-end, développeurs d'infrastructure et de méthodes d'apprentissage automatique, etc.