Suivez ces étapes pour résoudre tout problème d'entretien de programmation dynamique

Malgré une expérience significative dans la création de produits logiciels, de nombreux ingénieurs se sentent nerveux à l'idée de passer par une interview de codage axée sur les algorithmes. J'ai interviewé des centaines d'ingénieurs chez Refdash, Google et dans des startups auxquelles j'ai participé, et certaines des questions les plus courantes qui inquiètent les ingénieurs sont celles qui impliquent la programmation dynamique (DP).

De nombreuses entreprises technologiques aiment poser des questions aux DP dans leurs entretiens. Bien que nous puissions débattre de leur efficacité dans l'évaluation de la capacité d'une personne à jouer un rôle d'ingénieur, DP continue d'être un domaine qui incite les ingénieurs à trouver un emploi qu'ils aiment.

Programmation dynamique - prévisible et préparable

L'une des raisons pour lesquelles je pense personnellement que les questions DP ne sont peut-être pas le meilleur moyen de tester les capacités d'ingénierie est qu'elles sont prévisibles et faciles à mettre en correspondance. Ils nous permettent de filtrer beaucoup plus pour la préparation que pour la capacité d'ingénierie.

Ces questions semblent généralement assez complexes à l'extérieur et peuvent vous donner l'impression qu'une personne qui les résout est très bonne en algorithmes. De même, les personnes qui ne sont peut-être pas en mesure de surmonter certains concepts décevants de DP peuvent sembler assez faibles dans leur connaissance des algorithmes.

La réalité est différente et le facteur le plus important de leur performance est la préparation. Alors assurons-nous que tout le monde y est préparé. Une fois pour toutes.

7 étapes pour résoudre un problème de programmation dynamique

Dans le reste de cet article, je vais passer en revue une recette que vous pouvez suivre pour déterminer si un problème est un «problème DP», ainsi que pour trouver une solution à un tel problème. Plus précisément, je passerai par les étapes suivantes:

  1. Comment reconnaître un problème DP
  2. Identifier les variables problématiques
  3. Exprimer clairement la relation de récurrence
  4. Identifier les cas de base
  5. Décidez si vous souhaitez l'implémenter de manière itérative ou récursive
  6. Ajouter une mémorisation
  7. Déterminer la complexité temporelle

Exemple de problème DP

Dans le but d'avoir un exemple d'abstractions que je vais faire, permettez-moi de présenter un exemple de problème. Dans chacune des sections, je ferai référence au problème, mais vous pouvez également lire les sections indépendamment du problème.

Énoncé du problème:

Dans ce problème, nous sommes sur une balle sautante folle, essayant de s'arrêter, tout en évitant les pointes en cours de route.

Voici les règles:

1) On vous donne une piste plate avec un tas de pointes. La piste est représentée par un tableau booléen qui indique si un point particulier (discret) est exempt de pointes. C'est vrai pour clair et faux pour pas clair.

Exemple de représentation de tableau:

2) On vous donne une vitesse de départ S. S est un entier non négatif à un point donné, et il indique combien vous avancerez avec le prochain saut.

3) Chaque fois que vous atterrissez sur un endroit, vous pouvez ajuster votre vitesse jusqu'à 1 unité avant le prochain saut.

4) Vous voulez vous arrêter en toute sécurité n'importe où le long de la piste (il n'est pas nécessaire d'être à la fin du réseau). Vous vous arrêtez lorsque votre vitesse devient 0. Cependant, si vous atterrissez sur un pic à tout moment, votre balle rebondissante folle éclate et la partie est terminée.

La sortie de votre fonction doit être un booléen indiquant si nous pouvons nous arrêter en toute sécurité n'importe où le long de la piste.

Étape 1: Comment reconnaître un problème de programmation dynamique

Tout d'abord, précisons que DP n'est essentiellement qu'une technique d'optimisation. DP est une méthode pour résoudre des problèmes en les décomposant en un ensemble de sous-problèmes plus simples, en résolvant chacun de ces sous-problèmes une seule fois et en stockant leurs solutions. La prochaine fois que le même sous-problème se produit, au lieu de recalculer sa solution, vous recherchez simplement la solution précédemment calculée. Cela permet d'économiser du temps de calcul au détriment d'une dépense (espérons-le) modeste en espace de stockage.

Reconnaître qu'un problème peut être résolu à l'aide de DP est la première étape et souvent la plus difficile pour le résoudre. Ce que vous voulez vous demander, c'est si la solution de votre problème peut être exprimée en fonction de solutions à des problèmes similaires plus petits.

Dans le cas de notre exemple de problème, étant donné un point sur la piste, une vitesse et la piste devant nous, nous pourrions déterminer les endroits où nous pourrions sauter ensuite. En outre, il semble que la possibilité de s'arrêter à partir du point actuel avec la vitesse actuelle dépend uniquement de la possibilité de s'arrêter à partir du point que nous choisissons d'aller au suivant.

C'est une bonne chose, car en avançant, nous raccourcissons la piste devant nous et réduisons notre problème. Nous devrions être en mesure de répéter ce processus jusqu'au bout jusqu'à ce que nous arrivions à un point où il est évident que nous pouvons nous arrêter.

Reconnaître un problème de programmation dynamique est souvent l'étape la plus difficile pour le résoudre. La solution du problème peut-elle être exprimée en fonction de solutions à des problèmes similaires plus petits?

Étape 2: Identifiez les variables du problème

Nous avons maintenant établi qu'il existe une structure récursive entre nos sous-problèmes. Ensuite, nous devons exprimer le problème en termes de paramètres de fonction et voir lesquels de ces paramètres changent.

En général, dans les entretiens, vous aurez un ou deux paramètres changeants, mais techniquement, cela pourrait être n'importe quel nombre. Un exemple classique d'un problème à un paramètre changeant est «déterminer un n-ième nombre de Fibonacci». Un tel exemple pour un problème à deux paramètres changeants est «Calculer la distance d'édition entre les chaînes». Si vous n'êtes pas familier avec ces problèmes, ne vous inquiétez pas.

Une façon de déterminer le nombre de paramètres changeants est de lister des exemples de plusieurs sous-problèmes et de comparer les paramètres. Compter le nombre de paramètres changeants est précieux pour déterminer le nombre de sous-problèmes que nous devons résoudre. Il est également important en soi pour nous aider à renforcer la compréhension de la relation de récurrence de l'étape 1.

Dans notre exemple, les deux paramètres qui pourraient changer pour chaque sous-problème sont:

  1. Position du tableau (P)
  2. Vitesse (S)

On pourrait dire que la piste en avant change également, mais ce serait redondant étant donné que toute la piste non changeante et la position (P) portent déjà cette information.

Maintenant, avec ces 2 paramètres changeants et d'autres paramètres statiques, nous avons la description complète de nos sous-problèmes.

Identifiez les paramètres changeants et déterminez le nombre de sous-problèmes.

Étape 3: exprimer clairement la relation de récurrence

C'est une étape importante que beaucoup franchissent pour se lancer dans le codage. Exprimer la relation de récurrence aussi clairement que possible renforcera votre compréhension du problème et rendra tout le reste beaucoup plus facile.

Une fois que vous avez compris que la relation de récurrence existe et que vous spécifiez les problèmes en termes de paramètres, cela devrait être une étape naturelle. Comment les problèmes sont-ils liés les uns aux autres? En d'autres termes, supposons que vous ayez calculé les sous-problèmes. Comment calculeriez-vous le problème principal?

Voici comment nous y pensons dans notre exemple de problème:

Parce que vous pouvez ajuster votre vitesse jusqu'à 1 avant de sauter à la position suivante, il n'y a que 3 vitesses possibles, et donc 3 endroits où nous pourrions être les prochains.

Plus formellement, si notre vitesse est S, position P, nous pourrions passer de (S, P) à:

  1. (S, P + S) ; # si on ne change pas la vitesse
  2. (S - 1, P + S - 1) ; # si on change la vitesse de -1
  3. (S + 1, P + S + 1) ; # si on change la vitesse de +1

Si nous pouvons trouver un moyen de nous arrêter dans l'un des sous-problèmes ci-dessus, nous pouvons également nous arrêter à partir de (S, P). C'est parce que nous pouvons passer de (S, P) à l'une des trois options ci-dessus.

Il s'agit généralement d'un bon niveau de compréhension du problème (explication en anglais simple), mais vous voudrez parfois aussi exprimer la relation mathématiquement. Appelons une fonction que nous essayons de calculer canStop. Ensuite:

canStop (S, P) = canStop (S, P + S) || canStop (S - 1, P + S - 1) || canStop (S + 1, P + S + 1)

Woohoo, il semble que nous ayons notre relation de récurrence!

Relation de récurrence: en supposant que vous ayez calculé les sous-problèmes, comment calculeriez-vous le problème principal?

Étape 4: Identifiez les cas de base

Un cas de base est un sous-problème qui ne dépend d'aucun autre sous-problème. Afin de trouver de tels sous-problèmes, vous voulez généralement essayer quelques exemples, voir comment votre problème se simplifie en sous-problèmes plus petits et identifier à quel point il ne peut pas être simplifié davantage.

La raison pour laquelle un problème ne peut pas être simplifié davantage est que l'un des paramètres deviendrait une valeur qui n'est pas possible compte tenu des contraintes du problème.

Dans notre exemple de problème, nous avons deux paramètres changeants, S et P. Pensons aux valeurs possibles de S et P qui pourraient ne pas être légales:

  1. P doit être dans les limites de la piste donnée
  2. P ne peut pas être tel que la piste [P] soit fausse car cela signifierait que nous nous tenons sur une pointe
  3. S ne peut pas être négatif, et un S == 0 indique que nous avons terminé

Parfois, il peut être un peu difficile de convertir les assertions que nous faisons sur les paramètres en cas de base programmables. En effet, en plus de lister les assertions si vous voulez rendre votre code concis et ne pas vérifier les conditions inutiles, vous devez également réfléchir à laquelle de ces conditions est même possible.

Dans notre exemple:

  1. P <0 || P> = la longueur de la piste semble être la bonne chose à faire. Une autre solution pourrait consister à considérer m aking la fin de P de la piste d'un cas de base. Cependant, il est possible qu'un problème se scinde en un sous-problème qui dépasse la fin de la piste, nous devons donc vraiment vérifier les inégalités.
  2. Cela semble assez évident. Nous pouvons simplement vérifier si la piste [P] est fausse .
  3. Semblable à # 1, nous pourrions simplement vérifier S <0 et S == 0. Cependant, ici nous pouvons raisonner qu'il est impossible que S soit <0 car S diminue d'au plus 1, donc il faudrait passer par S == 0 cas au préalable. Par conséquent, S == 0 est un cas de base suffisant pour le paramètre S.

Étape 5: Décidez si vous souhaitez l'implémenter de manière itérative ou récursive

La façon dont nous avons parlé des étapes jusqu'à présent pourrait vous amener à penser que nous devrions mettre en œuvre le problème de manière récursive. Cependant, tout ce dont nous avons parlé jusqu'à présent est totalement indépendant du fait que vous décidiez d'implémenter le problème de manière récursive ou itérative. Dans les deux approches, vous devrez déterminer la relation de récurrence et les cas de base.

Pour décider de procéder de manière itérative ou récursive, vous devez réfléchir attentivement aux compromis .

Les problèmes de débordement de pile sont généralement un facteur décisif et une raison pour laquelle vous ne voudriez pas avoir de récursivité dans un système de production (backend). Cependant, aux fins de l'interview, tant que vous mentionnez les compromis, vous devriez généralement être d'accord avec l'une ou l'autre des implémentations. Vous devriez vous sentir à l'aise pour mettre en œuvre les deux.

Dans notre problème particulier, j'ai implémenté les deux versions. Voici le code python pour cela:

Une solution récursive: (les extraits de code d'origine peuvent être trouvés ici)

Une solution itérative: (les extraits de code d'origine peuvent être trouvés ici)

Étape 6: Ajouter une mémorisation

La mémorisation est une technique étroitement associée à la DP. Il est utilisé pour stocker les résultats d'appels de fonction coûteux et renvoyer le résultat mis en cache lorsque les mêmes entrées se produisent à nouveau.

Pourquoi ajoutons-nous la mémorisation à notre récursivité? On rencontre les mêmes sous-problèmes qui, sans mémorisation, sont calculés à plusieurs reprises. Ces répétitions conduisent très souvent à des complexités temporelles exponentielles.

Dans les solutions récursives, l'ajout de mémorisation devrait sembler simple. Voyons pourquoi. N'oubliez pas que la mémorisation n'est qu'un cache des résultats de la fonction. Il y a des moments où vous souhaitez vous écarter de cette définition afin de supprimer quelques optimisations mineures, mais traiter la mémorisation comme un cache de résultat de fonction est la manière la plus intuitive de l'implémenter.

Cela signifie que vous devez:

  1. Stockez le résultat de votre fonction dans votre mémoire avant chaque instruction de retour
  2. Recherchez dans la mémoire le résultat de la fonction avant de commencer à faire tout autre calcul

Voici le code ci-dessus avec une mémorisation ajoutée (les lignes ajoutées sont mises en évidence): (les extraits de code d'origine peuvent être trouvés ici)

Afin d'illustrer l'efficacité de la mémorisation et des différentes approches, faisons quelques tests rapides. Je mettrai l'accent sur les trois méthodes que nous avons vues jusqu'à présent. Voici la configuration:

  1. J'ai créé une piste de longueur 1000 avec des pointes à des endroits aléatoires (j'ai choisi d'avoir une probabilité qu'un pic soit à un endroit donné soit de 20%)
  2. initSpeed ​​= 30
  3. J'ai exécuté toutes les fonctions 10 fois et mesuré le temps moyen d'exécution

Voici les résultats (en secondes):

Vous pouvez voir que l'approche récursive pure prend environ 500 fois plus de temps que l'approche itérative et environ 1300 fois plus de temps que l'approche récursive avec mémorisation. À noter que cet écart augmenterait rapidement avec la longueur de la piste. Je vous encourage à essayer de l'exécuter vous-même.

Étape 7: Déterminer la complexité temporelle

Il existe quelques règles simples qui peuvent rendre la complexité du temps de calcul d'un problème de programmation dynamique beaucoup plus facile. Voici deux étapes à suivre:

  1. Comptez le nombre d'états - cela dépendra du nombre de paramètres changeants dans votre problème
  2. Pensez au travail effectué pour chaque état. En d'autres termes, si tout le reste, sauf un état, a été calculé, combien de travail devez-vous faire pour calculer ce dernier état?

Dans notre exemple de problème, le nombre d'états est | P | * | S |,

  • P est l'ensemble de toutes les positions (| P | indique le nombre d'éléments dans P)
  • S est l'ensemble de toutes les vitesses

Le travail effectué pour chaque état est O (1) dans ce problème car, étant donné tous les autres états, nous devons simplement regarder 3 sous-problèmes pour déterminer l'état résultant.

Comme nous l'avons noté dans le code précédent, | S | est limité par la longueur de la piste (| P |), on pourrait donc dire que le nombre d'états est | P | ² et parce que le travail effectué pour chaque état est O (1), alors la complexité temporelle totale est O (| P | ²).

Cependant, il semble que | S | peut être encore plus limité, car s'il s'agissait vraiment de | P |, il est très clair que l'arrêt ne serait pas possible car il faudrait sauter sur toute la longueur de la piste au premier coup.

Voyons donc comment nous pouvons mettre une limite plus étroite sur | S |. Appelons la vitesse maximale S. Supposons que nous partons de la position 0. À quelle vitesse pourrions-nous nous arrêter si nous essayions de nous arrêter le plus tôt possible et si nous ignorons les pics potentiels?

Dans la première itération, il faudrait au moins arriver au point (S-1), en ajustant notre vitesse à zéro par -1. À partir de là, nous passerions au minimum par (S-2) pas en avant, et ainsi de suite.

Pour une piste de longueur L , ce qui suit doit tenir:

=> (S-1) + (S-2) + (S-3) +…. + 1 <L

=> S * (S-1) / 2 <L

=> S² - S - 2L <0

Si vous trouvez les racines de la fonction ci-dessus, elles seront:

r1 = 1/2 + sqrt (1/4 + 2L) et r2 = 1/2 - sqrt (1/4 + 2L)

Nous pouvons écrire notre inégalité comme:

(S - r1) * (S - r2) < ; 0

Considérant que S - r2> 0 pour tout S> 0 et L> 0, nous avons besoin de ce qui suit:

S - 1/2 - carré (1/4 + 2L) < ; 0

=> S <1/2 + carré (1/4 + 2L)

C'est la vitesse maximale que nous pourrions éventuellement avoir sur une piste d'une longueur L. Si nous avions une vitesse supérieure à cela, nous ne pourrions pas nous arrêter même théoriquement, quelle que soit la position des pointes.

Cela signifie que la complexité temporelle totale ne dépend que de la longueur de la piste L sous la forme suivante:

O (L * sqrt (L)) qui est meilleur que O (L²)

O (L * sqrt (L)) est la limite supérieure de la complexité temporelle

Génial, vous avez réussi! :)

Les 7 étapes que nous avons traversées devraient vous donner un cadre pour résoudre systématiquement tout problème de programmation dynamique. Je recommande fortement de pratiquer cette approche sur quelques problèmes supplémentaires pour perfectionner votre approche.

Voici quelques étapes à suivre

  1. Étendez l'exemple de problème en essayant de trouver un chemin vers un point d'arrêt. Nous avons résolu un problème qui vous indique si vous pouvez vous arrêter, mais que se passe-t-il si vous souhaitez également connaître les étapes à suivre pour vous arrêter éventuellement le long de la piste? Comment modifieriez-vous l'implémentation existante pour faire cela?
  2. Si vous souhaitez consolider votre compréhension de la mémorisation et comprendre qu'il ne s'agit que d'un cache de résultats de fonction, vous devriez lire les décorateurs en Python ou des concepts similaires dans d'autres langages. Pensez à la manière dont ils vous permettraient de mettre en œuvre la mémorisation en général pour toute fonction que vous souhaitez mémoriser.
  3. Travaillez sur plus de problèmes de DP en suivant les étapes que nous avons suivies. Vous pouvez toujours trouver un tas d'entre eux en ligne (ex. LeetCode ou GeeksForGeeks). Pendant que vous pratiquez, gardez à l'esprit une chose: apprenez des idées, n'apprenez pas de problèmes. Le nombre d'idées est nettement plus petit et c'est un espace plus facile à conquérir qui vous servira également beaucoup mieux.

Lorsque vous sentez que vous avez conquis ces idées, consultez Refdash où vous êtes interviewé par un ingénieur senior et obtenez un retour détaillé sur votre codage, vos algorithmes et la conception de votre système.

Publié à l'origine sur le blog Refdash. Refdash est une plate-forme d'interview qui aide les ingénieurs à interviewer de manière anonyme des ingénieurs expérimentés de grandes entreprises telles que Google, Facebook ou Palantir et à obtenir un retour détaillé. Refdash aide également les ingénieurs à découvrir des opportunités d'emploi incroyables en fonction de leurs compétences et de leurs intérêts.