A pesar de tener una experiencia significativa en la creación de productos de software, muchos ingenieros se sienten nerviosos ante la idea de pasar por una entrevista de codificación que se centra en algoritmos. He entrevistado a cientos de ingenieros en Refdash, Google y en nuevas empresas de las que he formado parte, y algunas de las preguntas más comunes que inquietan a los ingenieros son las que involucran la Programación dinámica (DP).
A muchas empresas de tecnología les gusta hacer preguntas sobre DP en sus entrevistas. Si bien podemos debatir si son eficaces para evaluar la capacidad de alguien para desempeñarse en un puesto de ingeniería, DP sigue siendo un área que hace que los ingenieros se sientan atraídos por encontrar un trabajo que les guste.
Programación dinámica: predecible y preparable
Una de las razones por las que personalmente creo que las preguntas de DP podrían no ser la mejor manera de probar la capacidad de ingeniería es que son predecibles y fáciles de combinar. Nos permiten filtrar mucho más por la preparación que por la capacidad de ingeniería.
Estas preguntas suelen parecer bastante complejas por fuera y pueden darte la impresión de que una persona que las resuelve es muy buena en algoritmos. De manera similar, las personas que pueden no ser capaces de superar algunos conceptos retorcidos de DP pueden parecer bastante débiles en su conocimiento de los algoritmos.
La realidad es diferente y el factor más importante en su desempeño es la preparación. Así que asegurémonos de que todos estén preparados para ello. De una vez por todas.
7 pasos para resolver un problema de programación dinámica
En el resto de esta publicación, repasaré una receta que puede seguir para averiguar si un problema es un "problema de DP", así como para encontrar una solución a dicho problema. Específicamente, seguiré los siguientes pasos:
- Cómo reconocer un problema de DP
- Identificar las variables del problema
- Expresar claramente la relación de recurrencia
- Identificar los casos base
- Decide si quieres implementarlo de forma iterativa o recursiva
- Agregar memoización
- Determinar la complejidad del tiempo
Problema de muestra de DP
Con el fin de tener un ejemplo de las abstracciones que voy a hacer, permítanme presentarles un problema de muestra. En cada una de las secciones, me referiré al problema, pero también podría leer las secciones independientemente del problema.
Planteamiento del problema:
En este problema, estamos en un salto loco, tratando de detenernos, mientras evitamos los picos en el camino.
Estas son las reglas:
1) Te dan una pista plana con un montón de púas. La pista está representada por una matriz booleana que indica si un punto en particular (discreto) está libre de picos. Es Verdadero para claro y Falso para no claro.
Representación de matriz de ejemplo:
2) Se le da una velocidad inicial S. S es un número entero no negativo en cualquier punto dado, e indica cuánto avanzará con el siguiente salto.
3) Cada vez que aterrizas en un lugar, puedes ajustar tu velocidad hasta en 1 unidad antes del siguiente salto.
4) Desea detenerse de manera segura en cualquier lugar de la pista (no es necesario que esté al final de la matriz). Te detienes cuando tu velocidad se vuelve 0. Sin embargo, si aterrizas en un pico en cualquier punto, tu loca bola que rebota explota y se termina el juego.
La salida de su función debe ser un booleano que indique si podemos detenernos con seguridad en cualquier lugar de la pista.
Paso 1: Cómo reconocer un problema de programación dinámica
Primero, dejemos en claro que DP es esencialmente solo una técnica de optimización. DP es un método para resolver problemas dividiéndolos en una colección de subproblemas más simples, resolviendo cada uno de esos subproblemas solo una vez y almacenando sus soluciones. La próxima vez que ocurra el mismo subproblema, en lugar de volver a calcular su solución, simplemente busque la solución calculada previamente. Esto ahorra tiempo de cálculo a expensas de un gasto modesto (con suerte) en espacio de almacenamiento.
Reconocer que un problema se puede resolver con DP es el primer paso y, a menudo, el más difícil para resolverlo. Lo que quiere preguntarse es si la solución de su problema puede expresarse en función de soluciones a problemas menores similares.
En el caso de nuestro problema de ejemplo, dado un punto en la pista, una velocidad y la pista más adelante, podríamos determinar los puntos donde potencialmente podríamos saltar a continuación. Además, parece que si podemos detenernos desde el punto actual con la velocidad actual depende solo de si podemos detenernos desde el punto que elegimos para ir a continuación.
Eso es una gran cosa, porque al avanzar, acortamos la pista y hacemos nuestro problema más pequeño. Deberíamos poder repetir este proceso hasta que lleguemos a un punto en el que sea obvio si podemos detenernos.
Reconocer un problema de programación dinámica es a menudo el paso más difícil para resolverlo. ¿Puede la solución del problema expresarse como una función de soluciones a problemas menores similares?Paso 2: identificar las variables del problema
Ahora hemos establecido que existe una estructura recursiva entre nuestros subproblemas. A continuación, necesitamos expresar el problema en términos de los parámetros de la función y ver cuáles de esos parámetros están cambiando.
Por lo general, en las entrevistas, tendrá uno o dos parámetros cambiantes, pero técnicamente esto podría ser cualquier número. Un ejemplo clásico de un problema de un parámetro cambiante es "determinar un número de Fibonacci n-ésimo". Un ejemplo de un problema de dos parámetros cambiantes es "Calcular la distancia de edición entre cadenas". Si no está familiarizado con estos problemas, no se preocupe.
Una forma de determinar el número de parámetros cambiantes es enumerar ejemplos de varios subproblemas y comparar los parámetros. Contar el número de parámetros cambiantes es valioso para determinar el número de subproblemas que tenemos que resolver. También es importante por derecho propio para ayudarnos a fortalecer la comprensión de la relación de recurrencia desde el paso 1.
En nuestro ejemplo, los dos parámetros que podrían cambiar para cada subproblema son:
- Posición de la matriz (P)
- Velocidad (S)
Se podría decir que la pista de adelante también está cambiando, pero eso sería redundante considerando que toda la pista que no cambia y la posición (P) ya llevan esa información.
Ahora, con estos 2 parámetros cambiantes y otros parámetros estáticos, tenemos la descripción completa de nuestros subproblemas.
Identifique los parámetros cambiantes y determine el número de subproblemas.Paso 3: Exprese claramente la relación de recurrencia
Este es un paso importante por el que muchos se apresuran para comenzar a codificar. Expresar la relación de recurrencia con la mayor claridad posible fortalecerá la comprensión del problema y hará que todo lo demás sea mucho más fácil.
Una vez que sepa que existe la relación de recurrencia y especifique los problemas en términos de parámetros, esto debería ser un paso natural. ¿Cómo se relacionan los problemas entre sí? En otras palabras, supongamos que ha calculado los subproblemas. ¿Cómo calcularía el problema principal?
Así es como lo pensamos en nuestro problema de muestra:
Debido a que puede ajustar su velocidad hasta en 1 antes de saltar a la siguiente posición, solo hay 3 velocidades posibles y, por lo tanto, 3 puntos en los que podríamos ser los siguientes.
Más formalmente, si nuestra velocidad es S, posición P, podríamos pasar de (S, P) a:
- (S, P + S) ; # si no cambiamos la velocidad
- (S - 1, P + S - 1) ; # si cambiamos la velocidad en -1
- (S + 1, P + S + 1) ; # si cambiamos la velocidad en +1
Si podemos encontrar una manera de detenernos en cualquiera de los subproblemas anteriores, también podemos detenernos desde (S, P). Esto se debe a que podemos pasar de (S, P) a cualquiera de las tres opciones anteriores.
Este suele ser un buen nivel de comprensión del problema (explicación en inglés simple), pero a veces es posible que también desee expresar la relación matemáticamente. Llamemos a una función que estamos tratando de calcular canStop. Luego:
canStop (S, P) = canStop (S, P + S) || canStop (S - 1, P + S - 1) || canStop (S + 1, P + S + 1)
¡Vaya, parece que tenemos nuestra relación de recurrencia!
Relación de recurrencia: suponiendo que haya calculado los subproblemas, ¿cómo calcularía el problema principal?Paso 4: identificar los casos base
Un caso base es un subproblema que no depende de ningún otro subproblema. Para encontrar tales subproblemas, normalmente querrá probar algunos ejemplos, ver cómo su problema se simplifica en subproblemas más pequeños e identificar en qué punto no se puede simplificar más.
La razón por la que un problema no se puede simplificar más es que uno de los parámetros se convertiría en un valor que no es posible dadas las limitaciones del problema.
En nuestro problema de ejemplo, tenemos dos parámetros cambiantes, S y P. Pensemos qué valores posibles de S y P podrían no ser legales:
- P debe estar dentro de los límites de la pista dada
- P no puede ser tal que la pista [P] sea falsa porque eso significaría que estamos parados en un pico
- S no puede ser negativo y S == 0 indica que hemos terminado
A veces puede ser un poco difícil convertir las afirmaciones que hacemos sobre los parámetros en casos base programables. Esto se debe a que, además de enumerar las afirmaciones, si desea que su código se vea conciso y no verifique condiciones innecesarias, también debe pensar en cuáles de estas condiciones son posibles.
En nuestro ejemplo:
- P <0 || P> = longitud de la pista parece lo correcto. Una alternativa podría ser considerar m aking final P == de pista un caso base. Sin embargo, es posible que un problema se divida en un subproblema que vaya más allá del final de la pista, por lo que realmente necesitamos verificar la desigualdad.
- Esto parece bastante obvio. Simplemente podemos comprobar si la pista [P] es falsa .
- Similar al # 1, simplemente podríamos verificar si S <0 y S == 0. Sin embargo, aquí podemos razonar que es imposible que S sea <0 porque S disminuye como máximo en 1, por lo que tendría que pasar por S == 0 caso de antemano. Ther ntes S == 0 es un caso base suficiente para el parámetro S.
Paso 5: decide si quieres implementarlo de forma iterativa o recursiva
La forma en que hablamos sobre los pasos hasta ahora puede llevarlo a pensar que deberíamos implementar el problema de manera recursiva. Sin embargo, todo lo que hemos hablado hasta ahora es completamente independiente de si decide implementar el problema de forma recursiva o iterativa. En ambos enfoques, tendría que determinar la relación de recurrencia y los casos base.
Para decidir si va de forma iterativa o recursiva, debe pensar detenidamente en las compensaciones .
Los problemas de desbordamiento de pila suelen ser un factor decisivo y una razón por la que no querría tener recursividad en un sistema de producción (backend). Sin embargo, a los efectos de la entrevista, siempre que mencione las compensaciones, normalmente debería estar bien con cualquiera de las implementaciones. Debería sentirse cómodo implementando ambos.
En nuestro problema particular, implementé ambas versiones. Aquí hay un código de Python para eso:
Una solución recursiva: (los fragmentos de código originales se pueden encontrar aquí)
Una solución iterativa: (los fragmentos de código originales se pueden encontrar aquí)
Paso 6: agregar notas
La memorización es una técnica que está estrechamente asociada con DP. Se utiliza para almacenar los resultados de costosas llamadas a funciones y devolver el resultado en caché cuando se repiten las mismas entradas.
¿Por qué estamos agregando memorización a nuestra recursividad? Nos encontramos con los mismos subproblemas que, sin memorización, se calculan repetidamente. Estas repeticiones a menudo conducen a complejidades temporales exponenciales.
En soluciones recursivas, agregar memorización debería resultar sencillo. Veamos por qué. Recuerde que la memorización es solo un caché de los resultados de la función. Hay ocasiones en las que desea desviarse de esta definición para exprimir algunas optimizaciones menores, pero tratar la memorización como una función de caché de resultados es la forma más intuitiva de implementarla.
Esto significa que debes:
- Almacene el resultado de su función en su memoria antes de cada declaración de devolución
- Busque en la memoria el resultado de la función antes de comenzar a hacer cualquier otro cálculo
Aquí está el código de arriba con memorización agregada (las líneas agregadas están resaltadas): (los fragmentos de código originales se pueden encontrar aquí)
Para ilustrar la efectividad de la memorización y los diferentes enfoques, hagamos algunas pruebas rápidas. Haré una prueba de estrés con los tres métodos que hemos visto hasta ahora. Aquí está la configuración:
- Creé una pista de longitud 1000 con picos en lugares aleatorios (elegí tener una probabilidad de que un pico en cualquier lugar sea del 20%)
- initSpeed = 30
- Ejecuté todas las funciones 10 veces y medí el tiempo medio de ejecución.
Aquí están los resultados (en segundos):
Puede ver que el enfoque recursivo puro toma aproximadamente 500 veces más tiempo que el enfoque iterativo y aproximadamente 1300 veces más tiempo que el enfoque recursivo con memorización. Tenga en cuenta que esta discrepancia aumentaría rápidamente con la longitud de la pista. Te animo a que pruebes a ejecutarlo tú mismo.
Paso 7: determinar la complejidad del tiempo
Existen algunas reglas simples que pueden facilitar mucho la complejidad del tiempo de cálculo de un problema de programación dinámica. A continuación, se indican dos pasos que debe seguir:
- Cuente la cantidad de estados; esto dependerá de la cantidad de parámetros cambiantes en su problema
- Piense en el trabajo realizado por cada estado. En otras palabras, si se ha calculado todo lo demás menos un estado, ¿cuánto trabajo tiene que hacer para calcular ese último estado?
En nuestro problema de ejemplo, el número de estados es | P | * | S |, donde
- P es el conjunto de todas las posiciones (| P | indica el número de elementos en P)
- S es el conjunto de todas las velocidades
El trabajo realizado por cada estado es O (1) en este problema porque, dados todos los demás estados, simplemente tenemos que mirar 3 subproblemas para determinar el estado resultante.
Como señalamos en el código anterior, | S | está limitado por la longitud de la pista (| P |), por lo que podríamos decir que el número de estados es | P | ² y como el trabajo realizado por cada estado es O (1), entonces la complejidad de tiempo total es O (| P | ²).
Sin embargo, parece que | S | puede ser más limitado, porque si fuera realmente | P |, es muy claro que no sería posible detenerse porque tendría que saltar la longitud de toda la pista en el primer movimiento.
Entonces, veamos cómo podemos poner un límite más estricto en | S |. Llamemos a la velocidad máxima S. Supongamos que partimos de la posición 0. ¿Qué tan rápido podríamos detenernos si intentáramos detenernos lo antes posible e ignoramos los picos potenciales?
En la primera iteración, tendríamos que llegar al menos al punto (S-1), ajustando nuestra velocidad a cero en -1. A partir de ahí, como mínimo pasaríamos (S-2) pasos hacia adelante, y así sucesivamente.
Para una pista de longitud L , debe cumplirse lo siguiente:
=> (S-1) + (S-2) + (S-3) +…. + 1 <L
=> S * (S-1) / 2 <L
=> S² - S - 2L <0
Si encuentra raíces de la función anterior, serán:
r1 = 1/2 + raíz cuadrada (1/4 + 2L) y r2 = 1/2 - raíz cuadrada (1/4 + 2L)
Podemos escribir nuestra desigualdad como:
(S - r1) * (S - r2) < ; 0
Considerando que S - r2> 0 para cualquier S> 0 y L> 0, necesitamos lo siguiente:
S - 1/2 - raíz cuadrada (1/4 + 2L) < ; 0
=> S <1/2 + raíz cuadrada (1/4 + 2L)
Esa es la velocidad máxima que podríamos tener en una pista de longitud L. Si tuviéramos una velocidad superior a esa, no podríamos detenernos ni siquiera teóricamente, independientemente de la posición de los picos.
Eso significa que la complejidad del tiempo total depende solo de la longitud de la pista L en la siguiente forma:
O (L * sqrt (L)) que es mejor que O (L²)
O (L * sqrt (L)) es el límite superior de la complejidad del tiempo¡Impresionante, lo lograste! :)
Los 7 pasos que seguimos deberían brindarle un marco para resolver sistemáticamente cualquier problema de programación dinámica. Recomiendo encarecidamente practicar este enfoque en algunos problemas más para perfeccionar su enfoque.
Estos son algunos de los siguientes pasos que puede seguir
- Amplíe el problema de la muestra tratando de encontrar un camino hacia un punto de parada. Resolvimos un problema que te dice si puedes detenerte, pero ¿y si quisieras saber también los pasos a seguir para detenerte eventualmente en la pista? ¿Cómo modificaría la implementación existente para hacer eso?
- Si desea solidificar su comprensión de la memorización y comprende que es solo un caché de resultados de funciones, debe leer sobre decoradores en Python o conceptos similares en otros lenguajes. Piense en cómo le permitirían implementar la memorización en general para cualquier función que desee memorizar.
- Trabaje en más problemas de DP siguiendo los pasos que seguimos. Siempre puede encontrar un montón de ellos en línea (por ejemplo, LeetCode o GeeksForGeeks). Mientras practica, tenga en cuenta una cosa: aprenda ideas, no aprenda problemas. La cantidad de ideas es significativamente menor y es un espacio más fácil de conquistar que también te servirá mucho mejor.
Cuando sienta que ha conquistado estas ideas, consulte Refdash, donde lo entrevistará un ingeniero senior y obtenga comentarios detallados sobre su codificación, algoritmos y diseño de sistema.
Publicado originalmente en el blog Refdash. Refdash es una plataforma de entrevistas que ayuda a los ingenieros a entrevistarse de forma anónima con ingenieros experimentados de las principales empresas como Google, Facebook o Palantir y obtener comentarios detallados. Refdash también ayuda a los ingenieros a descubrir oportunidades laborales increíbles en función de sus habilidades e intereses.