Question d'entretien classant FizzBuzz (1), implémentant malloc (10) [clôturé]

J'aimerais avoir votre avis sur la difficulté de la question d'entretien suivante:

Trouvez le sous-tableau contigu avec la somme maximale dans un tableau d'entiers en temps O (n).

Ce problème de sondage trivial a été rendu célèbre par Jon Bentley dans ses Programming Pearls où il l'utilise pour démontrer les techniques de conception d'algorithmes.

Sur une échelle de 1 à 10, 1 étant le test FizzBuzz (ou HoppityHop ) et 10 étant implémentant la fonction C stdlib malloc (), comment classeriez-vous le problème ci-dessus?

Je pense que les personnes qui peuvent le mieux répondre à cette question sont celles qui ont lu Programming Pearls et qui ont essayé de résoudre ce problème par elles-mêmes. Pour motiver ceux qui ne l'ont pas fait, «Programming Pearls» apparaît plusieurs fois dans la liste des «10 meilleurs livres de programmation».

Quelques commentaires pourraient aider à obtenir une meilleure note:

• L'implémentation de malloc () n'est pas aussi formidable qu'il n'y paraît. Voir le langage de programmation C de K&R par exemple. Il est parfois demandé à Microsoft .

• Observation du CLRS sur la résolution de problèmes: il est souvent plus difficile de résoudre un problème à partir de zéro que de vérifier une solution clairement présentée, en particulier lorsque l'on travaille sous des contraintes de temps .

Cela dépend vraiment du développeur.

Si malloc avait 10 ans, j'évaluerais ce problème à 20. Mais là encore, j'ai déjà fait malloc et je pourrais probablement le faire à nouveau.

Quelqu'un qui a fait ce problème ou qui connaît l'algorithme approprié du haut de sa tête en fera un 5 et malloc () un 10.

Le problème avec ce type de question est que si vous les avez faites avant, elles sont faciles et c'est vraiment un test pour savoir si vous avez déjà vu cet algorithme auparavant. Je ne les aime donc pas pour les interviews.

Maintenant, pour les tests où vous donnez au développeur quelques jours, c'est un très bon test parce que s'ils ne connaissent pas l'algorithme, vous leur donnez la chance de faire la recherche et de se mettre à jour et c'est un test non seulement vos connaissances, mais votre capacité à acquérir de nouvelles connaissances.

Je suppose que la cote devrait être bidimensionnelle, au moins. FizzBuzz- mallocdécrit la gamme sur un axe, je l'appellerais "complexité technologique". Mais cette dimension unique n'est certainement pas suffisante pour décrire le problème. Pour résoudre le problème en question, le développeur doit penser plus que du code , tandis que la mise en œuvre mallocnécessite plus de discipline de codage que de créer des algorithmes complexes.

Voici donc comment j'organiserais ces problèmes:

Pour illustrer mon propos, j'ai ajouté un tri par fusion parallèle à l'intrigue, car je suppose que c'est un bon exemple de tâche sophistiquée à la fois technologiquement et algorithmiquement.

Je pense que c'est beaucoup plus difficile que FizzBuzz ou HoppityHop - ces deux-là ne sont rien de plus qu'un simple if-else ou un commutateur dans une boucle.

Le sous-tableau maximum nécessitera une analyse plus approfondie du problème sous-jacent - ce n'est pas quelque chose que vous vous attendez à voir dans une classe de programmation pour débutants car il nécessite des compétences mathématiques plus élevées qu'un problème de type FizzBuzz. Ce problème a une sensation similaire au problème du chemin le plus court, qui est résolu par l'algorithme de Dijkstra - c'est peut-être une spécialisation du problème du chemin le plus long .

Sur votre échelle de 1 à 10, je l'évaluerais probablement entre 3 et 5.

* Pendant que le serveur était en panne, j'ai trouvé que le problème de sous -réseau maximum avait sa propre page sur wikipedia.

Je lui donne un 3. Au-delà de la plupart des programmeurs que j'ai interviewés, mais un problème facile pour ceux que j'ai recommandés pour l'embauche.