Ronda 1: prueba de codificación, plataforma Hackerrank, 3 preguntas, 1,5 horas
1. En una array dada de longitud n, encuentre max(A[j] – A[i]) tal que i < j.
2. Una persona puede crear un ramo de flores con 3 rosas (costo del ramo = p) o 1 rosa y 1 lirio (costo = q)
En una variedad de flores, la persona tiene que seleccionar un conjunto de flores contiguas, es decir, 2 o 3 para obtener el costo máximo.
Formato de entrada : una string de 0 (indica rosa) y 1 (indica lirio).
Salida : Coste máximo.
Ejemplos:
Input: p = 2, q = 3, s = 0001000 Output: 5
Solución : Programación dinámica
if three consecutive 0's:
dp[i] = max(dp[i-1], p + dp[i-3])
else if 1, 0 or 0, 1:
dp[i] = max(dp[i-1], q + dp[i-2])
return dp[n-1]
Nota : Maneje los valores límite para evitar errores de índice de array fuera de límite.
3. Se da un gráfico en el que los Nodes representan niños y las aristas ponderadas unen a dos niños que comparten un pasatiempo común.
Ejemplo: si dos Nodes ‘i’ y ‘j’ están unidos por un borde que tiene el valor ‘k’, significa que tanto ‘i’ como ‘j’ tienen un interés común ‘k’.
Encuentre el producto máximo de ‘i’, ‘j’, donde ‘i’, ‘j’ son los niños que comparten el número máximo de pasatiempos comunes.
Solución : Cree una tabla hash que almacene el número de aristas entre un par ‘i’, ‘j’. Encuentre el producto máximo de ‘i’ y ‘j’ si tienen el número máximo de aristas entre ellos.
Aquellos que resolvieron los tres fueron seleccionados para la siguiente ronda (27 estudiantes).
Ronda 1: técnica
1. En un árbol dado, encuentre la suma máxima posible de modo que si se selecciona un Node, sus hijos no se pueden seleccionar, es decir, si el valor del Node se agrega a la suma, sus hijos no pueden estar presentes en la suma Me pidieron que escribiera el pseudocódigo en 5 minutos (se estaba ejecutando un temporizador).
Solución : programación dinámica en árboles
2. En un arreglo dado, encuentre el subarreglo más largo tal que los elementos adyacentes difieran en uno.
3. En una array dada, encuentre la subsecuencia más larga tal que los elementos adyacentes difieran en uno.
Solución : subsecuencia más larga tal que los elementos adyacentes difieren en uno
4. Dada una función f, tal que f(x) = y tal que 1 <= y <= x, crea una permutación aleatoria de una string dada. Debería crear permutaciones aleatorias cada vez.
Solución : intercambiar str[ni] y str[f(ni)] donde i varía de 1 a n.
Ronda 2: técnica
1. Cree una string con un conjunto dado de strings de modo que en las strings adyacentes, la última letra de la primera string = la primera letra de la segunda string.
Ejemplo :
Input: tap cat pac Output: tap -> pac -> cat
Se sabe que formará un ciclo, es decir, primera letra de la primera string de la string = última letra de la última string de la string.
Solución : enstringr una array de strings para formar un círculo
Di una solución usando una tabla hash y una array, que era básicamente un recorrido DFS. El entrevistador no había visto este enfoque y dio muchos casos de prueba, que pasaron.
2. Dados los n jugadores y el resultado de los partidos que tuvieron, cree una string tal que, si A derrotó a B y B derrotó a C, entonces deberían colocarse como ABC. Es posible que C haya vencido a A.
Similar a la pregunta anterior. Quería la solución que involucraba gráfico dirigido y retroceso, por lo que hizo esta pregunta.
3. Rompecabezas: el jugador 1 y el jugador 2 se turnan y colocan una moneda en un disco circular. Gana la última persona que sea capaz de colocar una moneda en el disco. Diseñe una estrategia tal que el jugador 1 (la primera persona en colocar una moneda) siempre gane.
Solución : Juego de monedas de mesa redonda
4. Dado un árbol binario, imprima su vista izquierda. Escribe el pseudocódigo.
Ejemplo :
Input:
1
/ \
2 6
/ \
7 0
/\ /
3 9 2
Output: 1 2 7 3
Solución : vista izquierda del árbol binario
Publicación traducida automáticamente
Artículo escrito por epsilon1729 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA