¿Cuáles son los 10 problemas de programación dinámica más populares entre los entrevistadores?

Answer 1

El resto de las respuestas proporcionaron una muestra bastante representativa de preguntas de programación dinámica y siempre puede encontrar más en línea (por ejemplo, LeetCode o GeeksForGeeks).

Tenga en cuenta que todos estos son grandes problemas para aprender a programar dinámicamente, pero no tienen nada que ver con los más populares en las entrevistas. De hecho, me sorprendería si alguna vez le hicieran alguna de las preguntas enumeradas en una entrevista a una empresa de alta tecnología . ¿Porqué es eso? Porque los entrevistadores monitorean foros como este para asegurarse de que evitan las preguntas que se han discutido públicamente y que darían una ventaja súper injusta a las personas que se topan con ellos.

Por lo general, cuando las personas preguntan acerca de la popularidad de algo, implican una distribución de energía en la que se usan algunos artículos en cantidad desproporcionada de veces.

Las preguntas de la entrevista se distribuyen en una distribución mucho más uniforme donde no tiene mucho sentido hablar de popularidad.

Lo que realmente desea preguntar es cuáles son las ideas más populares en las preguntas de programación dinámica y cuáles son los pasos para resolver tales preguntas.

Aquí está una lista de las cosas más importantes para recordar:

1. Reconocer un problema de programación dinámica . Este suele ser el paso más difícil y tiene que ver con reconocer que existe una relación recursiva. ¿Se puede expresar el resultado de su problema como una función de los resultados de los problemas más pequeños que parecen iguales?
2. Determine el número de parámetros cambiantes . Exprese su problema en términos de los parámetros de la función y vea cuántos de esos parámetros están cambiando. Por lo general, tendrá uno o dos, pero técnicamente este podría ser cualquier número. Los ejemplos típicos para problemas de un parámetro son fibonacci o un problema de cambio de moneda, porque dos parámetros es la distancia de edición.
3. Expresar claramente la relación recursiva . Una vez que descubras que la relación recursiva existe y especificas los problemas en términos de parámetros, esto debería ser un paso natural. ¿Cómo se relacionan los problemas entre sí? Es decir, suponiendo que haya calculado los subproblemas, ¿cómo calcularía el problema principal?
4. ¿Cuáles son sus casos base? Cuando desglosa los subproblemas en subproblemas más pequeños y los desglosa aún más, ¿cuál es el punto en el que ya no puede romperlo? ¿Todos estos subproblemas terminan dependiendo del mismo subproblema pequeño o varios de ellos?
5. Decida si desea implementarlo de forma iterativa o recursiva y siéntase cómodo con ambos . Conozca las compensaciones entre uno u otro, como el desbordamiento de pila recursivo, la escasez de computación, piense si se trata de un trabajo repetido o algo que siempre hace en línea, etc.
6. Añadir memoization . Si lo está implementando recursivamente, agregue memoria. Si lo haces de forma iterativa, esto vendrá gratis. Agregar memoización debería ser súper mecánico. Solo vea si ha memorizado el estado al comienzo de su función y agréguelo a la memoria antes de cada declaración de retorno. El valor de la memoria casi siempre debe ser el resultado de su función.
7. Complejidad del tiempo = (# de estados posibles * trabajo realizado por cada estado) . Esto también debería ser relativamente mecánico. Cuenta el número de estados que puedes tener. Esto será lineal si tiene un solo parámetro, cuadrático si tiene dos y así sucesivamente. Piense en el trabajo realizado para cada estado; ese es el trabajo que debe hacer asumiendo que ha calculado todos los subproblemas.

Aprende ideas, no aprendas problemas . La cantidad de ideas es significativamente menor y es un espacio más fácil de conquistar que también le servirá mucho mejor.

Cuando sientas que has conquistado estas ideas, echa un vistazo a Refdash donde te entrevista un ingeniero superior y obtén una información detallada sobre tu codificación, algoritmos y diseño del sistema.

Answer 2

Preguntas de la entrevista de programación dinámica

El enlace anterior recoge algunos problemas resueltos por la programación dinámica, como:

1. Suma máxima de todas las subarreglas
Una sub-matriz tiene un número de algunos números continuos. Dado un conjunto de enteros con números positivos y negativos, obtenga la suma máxima de todos los subarreglos. La complejidad del tiempo debe ser O (n).
Por ejemplo, en la matriz {1, -2, 3, 10, -4, 7, 2, -5}, su sub-matriz {3, 10, -4, 7, 2} tiene la suma máxima 18.

2. Longitud máxima de las subsecuencias incrementales
Dada una matriz sin clasificar, encuentre la longitud máxima de la subsecuencia en la que los números están en orden incremental.

Por ejemplo: si la matriz de entrada es {7, 2, 3, 1, 5, 8, 9, 6}, una subsecuencia con la mayoría de los números en orden incremental es {2, 3, 5, 8, 9} y el valor esperado La salida es 5.

3. Editar distancia
Implementar una función que obtiene la distancia de edición de dos cadenas de entrada. Hay tres tipos de operaciones de edición: inserción, eliminación y sustitución. La distancia de edición es el número mínimo de operaciones de edición para modificar una cadena de una a otra.

4. Número mínimo de monedas para el cambio
Por favor, implemente una función que obtenga el número mínimo de monedas, cuyo valor es v1, v2,…, vn, para hacer un cambio por una cantidad de dinero con valor t. Cualquier moneda con valor vi puede duplicarse para hacer cambios en cualquier momento.
Por ejemplo, el número mínimo de monedas para realizar el cambio de 15 de un conjunto de monedas con valor 1, 3, 9, 10 es 3. Podemos elegir dos monedas con valor 3 y una moneda con valor 9. El número de monedas para otras opciones debe ser mayor que 3.

5. Programación dinámica sobre valores robados
Hay n casas construidas en una línea, cada una de las cuales contiene algún valor en ella. Un ladrón va a robar el valor máximo en estas casas, pero no puede robar en dos casas adyacentes porque el propietario de una casa robada le dirá a sus dos vecinos en el lado izquierdo y derecho. ¿Cuál es el valor máximo robado?

6. La subcadena más larga sin duplicación
Dada una cadena, obtenga la longitud de la subcadena más larga que no tenga caracteres duplicados. Suponiendo que todos los caracteres en la cadena están en el rango de ‘a’ a ‘z’.

7. Producto máximo al cortar la cuerda
Dada una cuerda con longitud n , cómo cortar la cuerda en m partes con longitud n [0], n [1],…, n [ m -1], para obtener el producto máximo de n [0] * n [1] *… * n [ m -1]? Tenemos que cortar al menos una vez. Además, la longitud de toda la longitud de la cuerda, así como la longitud de cada parte, están en valor entero.

Answer 3

En mi experiencia como alguien que ha creado muchos videos de programación dinámica, he hablado con muchas personas que se están preparando para las entrevistas y he realizado muchas entrevistas, aquí están mis 10 preguntas principales.

1) Problema de mochila 0/1: dado el peso / precio de ciertos artículos con 1 cantidad cada uno y el peso máximo permitido, cómo elegir los artículos de manera tal que la suma del peso de los artículos seleccionados sea menor o igual al peso máximo permitido y el valor de esos artículos. se maximiza. Los siguientes son mis videos en los que se analizan los enfoques descendente y ascendente.

2) Problema de cambio de moneda: Dadas las monedas de ciertas denominaciones con una cantidad ilimitada y un total, la cantidad mínima de monedas que se necesitaría para formar ese total. A continuación se muestra mi enlace de video para acercamiento de abajo hacia arriba y de arriba hacia abajo.

3) Subsecuencia que aumenta más: en una matriz, encuentre una subsecuencia que tenga la longitud más larga y que aumente en orden. A continuación se muestran las soluciones n ^ 2 y nlogn.

4) Distancia de edición mínima: dadas dos cadenas, cuántas ediciones mínimas se necesitarían para convertir una cadena en otra cadena. Por edición me refiero a que puede agregar, actualizar o eliminar caracteres en la cadena.

5) Subsecuencia común más larga: dadas dos cadenas encuentran una subsecuencia común tanto en la cadena como en la más larga. Su otra variación es la subcadena común más larga entre dos cadenas. El video para ambos está abajo.

6) Problema de justificación de texto – Dadas algunas cadenas y el ancho de una pantalla. ¿Cómo alineas las cuerdas para que no excedan el ancho de la pantalla? O en otras palabras, ¿dónde coloca los saltos de línea entre las cadenas para que se vea lo más bonito posible o el texto se vea lo más alineado posible?

7) Problema de ruptura de palabras: se te da un trabajo largo que puede ser una combinación de diferentes palabras. También te dan un diccionario. Tienes que decir si las palabras en el diccionario se pueden combinar para formar esta palabra larga.

8) Problema de intercalado de cadenas: se le asignan 3 cadenas. Debe indicar si la primera y la segunda cadena pueden intercalarse entre sí para formar la tercera cadena o no.

9. Problema de suma de subconjunto: se le dan números de suma y un valor total. Debe indicar si algún subconjunto de estos números puede sumar el total dado. Otra variación simple es el problema de la partición, donde tienes que dividir el conjunto de números en 2 grupos donde la suma de cada grupo es la misma.

10. Estrategia óptima para el juego: dos jugadores juegan este juego. Te dan una serie de números. Cada jugador se turna para elegir cualquiera de los extremos de la matriz. ¿Cómo eliges para maximizar tus posibilidades de ganar? El jugador con la suma más alta de todos los valores seleccionados es el ganador.

Answer 4

Aquí está la lista de 10 preguntas de programación dinámica que suelen hacer los entrevistadores (hice esta lista mientras me preparaba para las entrevistas):

1. Problema de lanzamiento de dados: dados n dados cada uno con m caras, numerados de 1 a m, encuentre el número de formas para obtener la suma X. X es la suma de los valores en cada cara cuando se lanzan todos los dados.
2. Cambio de moneda : se le dan n tipos de denominaciones de moneda de valores v (1)
3. Recuento de paréntesis booleanos: se le da una expresión booleana que consiste en una cadena de los símbolos ‘verdadero’, ‘falso’, ‘y’, ‘o’, y ‘xor’. Cuente el número de formas de paréntesis de la expresión para que se evalúe como verdadera. Por ejemplo, solo hay una manera de poner entre paréntesis ‘verdadero y falso xor verdadero’ de manera que se evalúe como verdadero.
4. Problema de suma de subconjuntos: dado un conjunto de enteros no negativos y una suma de valores, determine si hay un subconjunto del conjunto dado con suma igual a la suma dada.
   Número mínimo de saltos: dada una matriz de enteros en la que cada elemento representa el número máximo de pasos que se pueden avanzar desde ese elemento, encuentre el número mínimo de saltos para llegar al final de la matriz (a partir del primer elemento).
5. Recorrido por dos personas de una secuencia de ciudades: se le da una secuencia ordenada de n ciudades y las distancias entre cada par de ciudades. Debe dividir las ciudades en dos subsecuencias (no necesariamente contiguas) de modo que la persona A visite todas las ciudades en la primera subsecuencia (en orden), la persona B visite todas las ciudades en la segunda subsecuencia (en orden) y la suma de las Las distancias totales recorridas por A y B se minimizan. Suponga que la persona A y la persona B comienzan inicialmente en la primera ciudad en sus subsecuencias respectivas.
6. Partición equilibrada: tiene un conjunto de n enteros cada uno en el rango 0 … K. Particione estos enteros en dos subconjuntos de tal manera que minimice | S1 – S2 |, donde S1 y S2 denotan las sumas de los elementos en cada uno de los dos subconjuntos .
7. Estrategia óptima para un juego: considere una fila de n monedas de valores v (1)… v (n), donde n es par. Jugamos un juego contra un oponente alternando turnos. En cada turno, un jugador selecciona la primera o la última moneda de la fila, la elimina de forma permanente y recibe el valor de la moneda. Determine la cantidad máxima de dinero que definitivamente podemos ganar si nos movemos primero.
8. Valor máximo Subsecuencia contigua: dada una secuencia de n números reales A (1) … A (n), determine una subsecuencia contigua A (i) … A (j) para la cual se maximiza la suma de elementos en la subsecuencia.
9. Distancia de edición: Dadas dos cadenas de texto A de longitud n y B de longitud m, desea transformar A en B con un número mínimo de operaciones de los siguientes tipos: eliminar un carácter de A, insertar un carácter en A o cambiar algunas personaje en A en un nuevo personaje. El número mínimo de tales operaciones requeridas para transformar A en B se llama la distancia de edición entre A y B.

Answer 5

Las siguientes preguntas son los problemas de programación dinámica más populares para las entrevistas:

1. Dada una matriz que consta de 0 y 1, encuentre la submatriz de tamaño máximo que consta de solo 1.
2. Dada una matriz que contiene enteros positivos y negativos, encuentre la matriz contigua con la suma máxima.
3. Subsecuencia creciente más larga: encuentre la longitud de la subsecuencia más larga de una secuencia dada de tal manera que todos los elementos estén ordenados en orden creciente / no decreciente.
   Hay muchos problemas que se reducen a este problema, como el apilamiento de cajas y la construcción de puentes. Estos días los entrevistadores esperan una solución NLogN.
4. Distancia de edición: dadas dos cadenas y un conjunto de operaciones Cambiar (C), insertar (I) y eliminar (D), encontrar el número mínimo de ediciones (operaciones) necesarias para transformar una cadena en otra.
5. 0/1 Problema de mochila: un ladrón que roba una tienda y puede cargar un peso máximo de W en su mochila. Hay n artículos y el artículo pesa wi y vale vi dólares. ¿Qué objetos debe tomar el ladrón?
6. Partición equilibrada: tiene un conjunto de n enteros cada uno en el rango 0 … K. Particione estos enteros en dos subconjuntos de tal manera que minimice | S1 – S2 |, donde S1 y S2 denotan las sumas de los elementos en cada uno de los dos subconjuntos .
7. Cambio de moneda: dado un valor N, si queremos hacer un cambio por N centavos y tenemos un suministro infinito de monedas de valor S = {S1, S2, .., Sm}, ¿de cuántas maneras podemos hacer el cambio?
8. Subsecuencia común más larga: encuentre la subsecuencia común más larga de las dos cadenas A y B, donde los elementos son letras de las dos cadenas y deben estar en el mismo orden.
9. Subsecuencia palindrómica más larga: la pregunta es la misma que la anterior pero la subsecuencia también debe ser palindrómica.
10. Número mínimo de saltos: dada una matriz de enteros en la que cada elemento representa el número máximo de pasos que se pueden avanzar desde ese elemento, encuentre el número mínimo de saltos para llegar al final de la matriz (a partir del primer elemento).

Answer 6

Aquí hay algunos problemas populares de DP que se preguntaron con frecuencia según mi observación.

1. Subarreglo contiguo de suma más grande (algoritmo de Kadane)

Dada una matriz que contiene enteros negativos y positivos. Encuentra la sub-matriz contigua con suma máxima.

Consulte la siguiente imagen por ejemplo:

Enlace a la solución: Subarray contiguo de mayor suma

2. Cambio de moneda

Dado un valor N, si queremos hacer un cambio para N centavos, y tenemos un suministro infinito de monedas de valor S = {S1, S2, .., Sm}, ¿de cuántas maneras podemos hacer el cambio? El orden de las monedas no importa.

Ejemplo:

Para N = 4 y S = {1,2,3}, hay cuatro soluciones: {1,1,1,1}, {1,1,2}, {2,2}, {1,3}. Así que la salida debe ser 4.

Para N = 10 y S = {2, 5, 3, 6}, hay cinco soluciones: {2,2,2,2,2}, {2,2,3,3}, {2,2,6 }, {2,3,5} y {5,5}. Así que la salida debería ser 5.

Enlace a la solución: Cambio de moneda

3. Número mínimo de saltos para llegar al final.

Dada una matriz de enteros donde cada elemento representa el número máximo de pasos que se pueden realizar desde ese elemento. Escriba una función para devolver el número mínimo de saltos para llegar al final de la matriz (a partir del primer elemento).

Si un elemento es 0, entonces no se puede mover a través de ese elemento.

Ejemplo:

Entrada: arr [] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
Salida: 3 (1-> 3 -> 8 -> 9)
Explicación: El primer elemento es 1, por lo que solo puede ir a 3. El segundo elemento es 3, por lo que puede hacer un máximo de 3 pasos, es decir, a 5 u 8 o 9.

Enlace a la solución: Número mínimo de saltos para llegar al final.

4. Número de monedas

Dado un valor V, si queremos hacer un cambio para V centavos, y tenemos un suministro infinito de monedas de valor C = {C1, C2, .., Cm}, ¿cuál es el número mínimo de monedas para realizar el cambio?

Ejemplos:

Entrada: monedas [] = {25, 10, 5}, V = 30
Salida: mínimo 2 monedas requeridas
Podemos usar una moneda de 25 centavos y una de 5 centavos.

Entrada: monedas [] = {9, 6, 5, 1}, V = 11
Salida: mínimo 2 monedas requeridas
Podemos usar una moneda de 6 centavos y 1 moneda de 5 centavos.

Enlace a la solución: encuentre el número mínimo de monedas que hacen un valor dado

5. Coincidencia de patrones comodín

Dado un texto y un patrón de comodín, implemente un algoritmo de coincidencia de patrón de comodín que encuentre si el patrón de comodín coincide con el texto. La coincidencia debe cubrir todo el texto (no texto parcial).

El patrón comodín puede incluir los caracteres ‘?’ y ‘*’
‘?’ – coincide con cualquier carácter individual
‘*’ – Coincide con cualquier secuencia de caracteres (incluida la secuencia vacía)

Ejemplo:

Texto = “baaabab”,
Patrón = “***** ba ***** ab”, SALIDA: verdadero
Patrón = “baaa? Ab”, SALIDA: verdadero
Patrón = “ba * a?”, SALIDA: verdadero
Patrón = “a * ab”, SALIDA: falso

Enlace a la solución: Wildcard Pattern Matching

6. Ruta de coste mínimo

Dado un costo de la matriz de costos [] [] y una posición (m, n) en el costo [] [], escriba una función que devuelva el costo de la ruta del costo mínimo para alcanzar (m, n) desde (0, 0). Cada celda de la matriz representa un costo para atravesar esa celda.

El costo total de una ruta a alcanzar (m, n) es la suma de todos los costos en esa ruta (incluidos el origen y el destino). Solo puede atravesar las células hacia abajo, hacia la derecha y hacia abajo en diagonal desde una celda dada, es decir, desde una celda dada (i, j), celdas (i + 1, j), (i, j + 1) y (i + 1, j + 1) puede ser atravesado. Puede suponer que todos los costos son enteros positivos.

Ejemplo : Considere la siguiente figura, ¿cuál es la ruta de costo mínimo para (2, 2)?

La ruta con el costo mínimo se resalta en la siguiente figura.
La ruta es (0, 0) -> (0, 1) -> (1, 2) -> (2, 2). El costo de la ruta es 8 (1 + 2 + 2 + 3).

Enlace a la solución: Min Cost Path

7. Contar formas de llegar a la escalera n.

Hay n escaleras, una persona parada en la parte inferior quiere llegar a la cima. La persona puede subir 1 escalera o 2 escaleras a la vez. Cuente el número de formas, la persona puede llegar a la cima (el orden sí importa).

Ejemplo:

Considere el ejemplo que se muestra en la imagen de abajo. El valor de n es 3 .

Hay 3 formas de llegar a la cima.

Algunos ejemplos más:

Entrada (Número de escaleras): 4
Salida (Número de formas posibles para llegar a la escalera Nth): 5
Explicación:
i) 1 -> 1 -> 1 -> 1 (La persona sube 1 paso desde la parte inferior, luego 1 paso, seguido de 1 paso, luego 1 paso, hasta llegar a la parte superior).
Similar,
ii) 1 -> 1 -> 2
iii) 1 -> 2 -> 1
iv) 2 -> 1 -> 1
v) 2 -> 2

Entrada: n = 1
Salida: 1
Solo hay una forma de subir 1 escalón.

Entrada: n = 2
Salida: 2
Hay dos formas: (1, 1) y (2)

Enlace a la solución: cuente las formas de llegar a la escalera n.

8. Cuerdas intercaladas

Dadas las tres cadenas A, B y C. Escriba una función que verifique si C es un entrelazado de A y B.

Se dice que C intercala entre A y B, si contiene todos los caracteres de A y B y se conserva el orden de todos los caracteres en cadenas individuales.

Ejemplos:

Entrada: YX X XXY
Salida: XXY no es intercalado de YX y X

Entrada: XY X XXY
Salida: XXY es el entrelazado de XY y X.

Enlace a la solución: busque si una cadena está intercalada de otras dos cadenas

9. Total de mensajes de decodificación

Supongamos que 1 representa ‘A’, 2 representa ‘B’, etc. Dada una secuencia de dígitos, cuente el número de decodificaciones posibles de la secuencia de dígitos dada.

Ejemplos:

Entrada: dígitos [] = “121”
Salida: 3
// Las posibles decodificaciones son “ABA”, “AU”, “LA”

Entrada: dígitos [] = “1234”
Salida: 3
// Las posibles decodificaciones son “ABCD”, “LCD”, “AWD”

Una secuencia de dígitos vacía se considera que tiene una decodificación. Se puede suponer que la entrada contiene dígitos válidos del 0 al 9 y que no hay 0 iniciales, ni 0s finales extra y no hay dos o más 0 consecutivos.

Enlace a la solución: recuento de posibles decodificaciones de una secuencia de dígitos dada

10. Cuente todas las sub-cadenas de Palindrome en una cadena

Dada una cadena, la tarea es contar toda la subcadena de palíndromo en una cadena dada. La longitud de la subcadena de palíndromo es mayor o igual a 2.

Ejemplos:

Entrada: str = “abaab”
Salida: 3
Explicación: Todas las subcadenas de palíndromo son: “aba”, “aa”, “baab”

Entrada: str = “abbaeae”
Salida: 4
Explicación: Todas las subcadenas de palíndromo son: “bb”, “abba”, “aea”, “eae”

Enlace a la solución: contar todas las subcadenas de Palindrome en una cadena

Answer 7

Programación dinámica de problemas de práctica

Archivos de programación dinámica – GeeksforGeeks

Estos enlaces pueden ayudarte. La mayoría de los problemas de DP que he enfrentado en las entrevistas están cubiertos en estos dos sitios.

Topcoder también tiene una buena colección de problemas de DP que van desde lo fácil hasta lo difícil. Para ganar confianza en DP, sugeriría que primero repase los enlaces anteriores y luego intente resolver los problemas de DP en Topcoder.

Answer 8

A continuación se muestran los 10 problemas más populares que se pueden resolver fácilmente mediante la programación dinámica y que se suelen realizar en entrevistas técnicas.

1. La subsecuencia común más larga
2. La más corta de la supersecuencia
3. El problema de la subsecuencia cada vez mayor
4. El problema de la distancia Levenshtein (Editar distancia)
5. Matriz de multiplicación de la cadena
6. 0-1 problema de mochila
7. Problema de particion
8. Corte de varilla
9. Problema de cambio de moneda
10. Problema de ruptura de palabras

Answer 9

Algunos problemas de programación dinámica que mis amigos o yo hemos preguntado en las entrevistas.

Dada una matriz de dimensiones mxn que tiene todas las entradas como 1 o 0, averigüe el tamaño de la matriz secundaria de tamaño máximo con todos los 1s.

Detectar si un subconjunto de un conjunto dado de N enteros no negativos suma un valor dado S

Encuentra la distancia de edición mínima entre dos cadenas dadas
Dadas las dos cadenas S1 y S2, averigüe la distancia de edición mínima para transformar S1 en S2. Operaciones de edición: inserción, eliminación, sustitución.

La subcadena común más larga
Dadas dos cuerdas S1 y S2. Encuentra la subcadena común más larga entre S1 y S2.

La subsecuencia común más larga
Dadas dos cuerdas S1 y S2. Encuentra la subsecuencia común más larga entre S1 y S2.

Saltos mínimos para llegar al final de un array.

Palíndromo más corto
Dada una cadena s, forma un palíndromo más corto agregando caracteres al comienzo de la cadena.

Palindrome Min Cut
Dada una cadena S, encuentre el número mínimo de cortes necesarios para separar la cadena en un conjunto de palíndromos.

La subcadena palindrómica más larga
Dada una cadena S, encuentra la subcadena palindrómica más larga.

Secuencia palindrómica más larga
Dada una cadena S, encuentra la subsecuencia palindrómica más larga.

Secuencia creciente más larga O (n logn)
Dada una matriz de enteros, encuentra la subsecuencia creciente más larga.

0-1 Problema de mochila
Dado un conjunto de artículos, cada uno con peso y beneficio, determine los artículos que se incluirán en una colección para que el peso total sea menor o igual a un límite de peso determinado y se maximice el beneficio total.

Para imprimir el número máximo de Como usando cuatro claves dadas.
Imagine que tiene un teclado especial con las siguientes cuatro teclas: Tecla 1: Imprime ‘A’ en la Tecla de pantalla 2: (Ctrl-A): Seleccione la Tecla de pantalla 3: (Ctrl-C): Copie la selección a la tecla de búfer 4: (Ctrl-V) : Imprime el búfer en la pantalla agregándolo después de lo que ya se ha impreso. Si solo puede presionar el teclado N veces (con las cuatro teclas anteriores), escriba un programa para producir el máximo número de A.

Número total de posibles árboles binarios de búsqueda con n teclas –
Dada n, ¿cuántos BST estructuralmente únicos (árboles de búsqueda binarios) que almacenan valores 1 … n?

Contar todas las decodificaciones posibles de una secuencia de dígitos dada
Dado un dígito en la Cadena S, cuente el número de codificaciones de la cadena.

Distintas cadenas binarias de longitud n sin 1s consecutivos
Cuente todas las posibles cadenas binarias distintas de longitud n sin 1s consecutivos

Answer 10

He dado entrevistas de Microsoft, Intuit, NetApp, Amazon, etc. Las preguntas más frecuentes sobre programación dinámica son:

Imprimir la subsecuencia común más larga

Problema de supercuerdas más corto

La subsecuencia bitónica más larga

Suma más grande Subarray contiguo

Subarray máximo de producto

Subarray máximo de producto

Número mínimo de saltos para llegar al final de un array.

Máxima diferencia entre dos elementos.

Gracias

Answer 11

Pago y envío siguiendo el enlace MIT. Tiene muy buenos videos cortos sobre problemas populares de DP.

Programación dinámica de problemas de práctica

Answer 12

Mi libro enumera los 20 problemas principales de DP (con soluciones) junto con una descripción detallada de todo el enfoque …

Programación dinámica para entrevistas de codificación (un enfoque ascendente para la resolución de problemas)

Answer 13

Lo invitamos a suscribirse a TrieUs.com para la preparación de la entrevista visitando nuestro sitio web http://www.trieus.com .

Enviaremos preguntas recientes sobre programación y diseño de las principales compañías como Google, Facebook, Amazon, Linkedin, etc. a todos nuestros suscriptores. Más importante aún, el objetivo no es darle algo como una respuesta estándar. En su lugar, nos enfocamos en decirle cómo analizar cada pregunta y cómo reutilizar las mismas técnicas en problemas similares.

El sitio web es nuevo, pero lo actualizaremos diariamente. También nos encantaría escuchar sus comentarios / sugerencias.

– Equipo de TrieUs