J'ai assisté à de nombreuses interviews et j'étais des deux côtés de la confrontation. Il est maintenant temps de partager les puzzles les plus intéressants avec les autres. Les entretiens doivent être intéressants et mémorables, et non misérables et démotivants.
Quelques commentaires
- Toutes les tâches sur la logique et / ou la programmation. Aucune connotation psychologique et trappes rondes.
- La décision n'est pas rendue intentionnellement. Cependant, je vous assure que presque toutes les tâches ont une solution simple et belle. Profitez-en!
Les tâches
Les voici.
Miroir de chaînes en SQL
Supposons que nous ayons une table avec une colonne de chaînes et que nous voulons trouver des lignes similaires en fonction d'une condition (par exemple, il peut s'agir d'une recherche en texte intégral ou d'une fonction interne qui reçoit deux valeurs en entrée et renvoie vrai / faux). Ainsi, nous écrivons l'auto-jointure et, bien sûr, nous obtenons des doublons parmi les valeurs. Autrement dit, nous obtenons des paires de miroirs en conséquence et les valeurs totales sont exactement deux fois plus que nous le souhaiterions. Question: comment supprimer du résultat un élément de chaque paire de miroirs et y laisser uniquement des valeurs uniques jusqu'aux permutations?
Trucs et astuces- il existe une propriété non évidente de chaînes et d'instructions SQL de base que vous pouvez utiliser ...
- Ou vous pouvez le google, si la demande est correcte, la réponse sera dans le premier lien vers stackoverflow.
Recherche de trous avec SQL
Il s'agit d'une excellente tâche pour évaluer la connaissance de toutes les fonctionnalités de base de SQL.
Supposons que nous ayons une table avec une colonne int. Nous ne savons rien des valeurs minimales / maximales qu'il contient. De plus, nous ne savons rien du nombre de lignes dans le tableau et, en général, il varie et nous ne devons pas nous y fier. On sait également que parmi les valeurs il y a des omissions dont la longueur ne dépasse pas une. Par exemple, pour une table de 5 (cinq) éléments: 1, 2, 4, 6, 7. Question: écrire une seule requête SQL en utilisant uniquement les opérateurs de base (c'est-à-dire sans procédure et variables), qui renverra la valeur de tous les "trous". Pour l'exemple ci-dessus, le résultat doit être 3, 5. N'oubliez pas qu'il n'y a pas de valeurs NULL aux intervalles. Les valeurs 3 et 5 ne figurent pas physiquement dans le tableau.
Astuce- si le déplacement échoue, écrivez dans plusieurs requêtes ou utilisez pl / sql, puis, si votre idée est correcte, vous pouvez logiquement accéder à une requête.
Indice- la plus belle demande sera si la demande des conditions d'entrée ci-dessus renvoie non pas "3, 5", mais "3, 5, 8".
Boucles dans une liste liée individuellement
Il s'agit d'un problème d'algorithmes et de complexité.
Supposons que nous ayons une liste finie, simplement connectée. Nous savons qu'il a probablement un cycle. Autrement dit, l'un des éléments suivants fait référence à l'un des précédents. Il est nécessaire de décrire la méthode de recherche de cycles dans une telle structure en un temps fini. Vous devez également fournir une estimation du temps et de la mémoire requis pour exécuter l'algorithme proposé.
Continuation
Il est nécessaire de modifier le résultat pour que la complexité de la mémoire soit O (1). Autrement dit, de sorte que la consommation de mémoire ne dépend pas de la taille de la liste.
Indice- rappelez-vous que tout comme la masse peut être convertie en énergie, la complexité du temps l'est aussi, peut être convertie en consommation de mémoire et vice versa.
Stockage de valeurs-clés
Une autre tâche pour co-écrire du code et en discuter pendant l'écriture.
Écrivez le stockage de valeurs-clés dans la langue de votre choix. Ajoutez la fonction set_all , qui prend une valeur et la définit pour toutes les clés existantes. Estimez les coûts de temps et de mémoire pour l'implémentation résultante.
Faites maintenant set_all travailler pour O (1).
Et pouvez-vous vous assurer que la complexité des méthodes get et set reste au tout début et que set_all continue de fonctionner pour O (1)? Si oui, alors implémentez. Sinon, prouvez pourquoi cela n'est pas possible.
Sauver les gens
Et dans cette tâche, vous devez réfléchir et raisonner avec la personne interrogée. Et la mise en œuvre est une question de technologie et n'est pas particulièrement intéressante.
Imaginez que nous avons un groupe de personnes. La quantité n'a pas d'importance. L'ensemble du groupe est aligné à l'arrière de la tête et un chapeau noir ou blanc est placé sur chaque tête. Personne ne connaît la couleur du chapeau qu'il porte. Cependant, tout le monde voit ce qui se passe devant eux et entend ce qui se passe derrière eux. Après cela, un étranger avec un pistolet vient à l'arrière du dernier du groupe. Il demande, "de quelle couleur est ton chapeau?" La réponse ne peut être que noire ou blanche. Il ne peut y avoir aucun autre message. Si une personne a deviné, ils la laisseront partir. Sinon, un tir se produit et, dans tous les cas, le processus se répète avec le «nouveau» dernier membre de la file d'attente.
Une précision importante: avant de commencer cette expérience inhumaine, tous les membres du groupe peuvent se rencontrer et réfléchir à leur stratégie de survie.
Question: comment maximiser le nombre de survivants et existe-t-il une estimation précise du nombre de survivants en fonction de la taille du groupe?
Astuce- Vous pensez comment chaque membre peut collecter toutes les informations disponibles et les transmettre en un seul bit?
Indice- peut-être même / impair ou l'opérateur XOR peut vous aider?
C’est tout. Maintenant, c'est à votre tour de résoudre l'un des problèmes et de parler de votre sélection intéressante de s / pour les interviews.