Experiencia Entrevista Directi | Conjunto 15 (en el campus)

Ronda 1: la prueba en línea en Codechef contiene 3 preguntas de codificación

1. Amanada, una niña de la escuela, está aprendiendo alfabetos en inglés. Su maestra ideó un pequeño juego para hacer la tarea divertida. Una cuadrícula de ‘m’ filas y ‘n’ columnas está llena de alfabetos en inglés. Necesita buscar palabras en inglés en esta cuadrícula moviéndose un paso a la vez en cualquiera de las celdas de cuadrícula adyacentes. Una cuadrícula de alfabetos y un conjunto de Se dan palabras en inglés. Amanda puede comenzar desde cualquier parte de la cuadrícula y puede moverse en cualquiera de las 8 celdas de cuadrícula adyacentes, un paso a la vez. Cada celda de la cuadrícula solo se puede usar una vez.
Entrada
Se le proporciona una plantilla en la que debe implementar una función cuya firma se proporciona a continuación.
C
int findWordInAGrid(char grid[128][128], int m, int n, char word[32])
/* devuelve 0 para falso, 1 para verdadero. */

C++
bool findWordInAGrid(cuadrícula de caracteres[128][128], int m, int n, palabra de caracteres[32])

Java
estático booleano findWordInAGridJava(char[][] grid, int m, int n, String word)

grid[][] representa los caracteres que están en la cuadrícula dada. Solo las primeras m filas y las primeras n columnas deben considerarse relevantes. palabra es la palabra cuya aparición debe encontrarse en la cuadrícula. Recuerde, la palabra puede comenzar desde cualquier ubicación en la cuadrícula. palabra nunca contendrá más de 30 caracteres. Devuelve verdadero si la palabra se encuentra en la cuadrícula, falso en caso contrario.
Salida
La función debe devolver verdadero, si puede encontrar la palabra en la cuadrícula y falso de lo contrario.
Ejemplo
Consideremos la cuadrícula que se muestra a continuación:
abc
def
ghi
Y el conjunto de palabras que se buscarán son:
abc
abedhi
efgh
Salida:
La salida del ejemplo anterior debería ser:
abc: true
abedhi: true
efgh: falso

2. Te dan una cuadrícula con 3 filas y N columnas. Cada celda de la cuadrícula contiene el valor 0 inicialmente. Realiza varias operaciones del siguiente tipo en la cuadrícula Elija una fila, digamos r. Elija una columna inicial y una columna final, digamos s y e. Por supuesto, 1 ≤s ≤ e ≤ N. Ahora, establezca todos los valores en la cuadrícula en la fila r, desde la columna s a la columna e a 1. Después de realizar todas las operaciones, desea encontrar subcuadrículas en esta cuadrícula (o rectángulos, por favor) que contienen solo 1s. Lo más importante es que desea encontrar el rectángulo que tiene el área más grande . Imprime el área de este rectángulo.
Aporte
La primera línea de entrada contiene un número T, el número de casos de prueba. La primera línea de cada caso de prueba contiene el número N y M respectivamente, separados por un solo espacio. N es el número de columnas en la grilla. M es el número de operaciones que realiza en la cuadrícula. Cada una de las siguientes M líneas contiene tres números enteros R, C1 y C2 respectivamente para describir la operación. R es la fila en la que se realiza la operación. C1 y C2 son las columnas de inicio y final respectivamente. Puede suponer que 1 ≤ C1 ≤ C2 ≤ N.
Salida
Para cada caso de prueba, genere un solo número en una línea por sí mismo. Este número debe ser el área del rectángulo más grande que se puede elegir en la cuadrícula, que contiene solo 1s.
Restricciones
1≤T ≤ 100
1 ≤ N ≤ 1000000
1 ≤ M ≤ 1000
Atención: Los datos de prueba están diseñados de tal manera que las soluciones que simulan cada operación en O(N) obtendrán TLE. Debería poder resolver cada caso de prueba en O (N). Sugerencia: convierta cada operación en un par de eventos de «inicio» y «finalización». Observe que el orden de las operaciones no importa. Por lo tanto, puede procesar los eventos en orden creciente de columnas. También puede simplemente almacenar cuántos eventos comienzan/finalizan en cada celda (ya que todos los eventos son similares y tienen un efecto idempotente). Ahora, puede recorrer la cuadrícula columna por columna manteniendo la racha más larga de 1s hacia la izquierda en cada fila. Esto ayuda a considerar los mejores rectángulos posibles con su borde derecho en la columna actual.
Entrada de muestra
3
5 2
1 1 4
2 3 5
10 3
1 1 8
2 2 10
3 1 9
5 2
2 1 4
3 3 5
Salida de muestra
4
21
4
Explicación
En el primer caso de prueba, la cuadrícula final parece
11110
00111
00000.
Podemos ver que el rectángulo más grande con 1 tiene el área 4. Hay dos de esos rectángulos. 1,1 –
1,4. Y 1,3 – 2,4.
En el segundo caso de prueba, la cuadrícula final parece
1111111100
0111111111
1111111110
El rectángulo más grande es 1,2 – 3,8. El área de este rectángulo es 3*7=21.

3. Te dan N piedras, etiquetadas del 1 al N. La i-ésima piedra tiene el peso W[i]. Hay M colores, etiquetados con números enteros del 1 al M. La i-ésima piedra tiene el color C[i] (por supuesto, un número entero entre el 1 y el M, inclusive). Quieres llenar una mochila con estas piedras. La mochila puede contener un peso total de X. Desea seleccionar exactamente M piedras; uno de cada color. La suma de los pesos de las piedras no debe exceder X. Dado que pagó una prima por una Mochila con capacidad X (a diferencia de una Mochila con una capacidad menor), desea llenar la Mochila tanto como sea posible.
Escriba un programa que tome todos los valores anteriores como entrada y calcule la mejor forma de llenar la mochila, es decir, la forma que minimice la capacidad no utilizada. Salida de esta capacidad no utilizada. Consulte la explicación de los casos de prueba de muestra para mayor claridad.
Entrada
La primera línea de entrada contiene el entero T, el número de casos de prueba. Luego sigue la descripción de los casos de prueba T. La primera línea de cada caso de prueba contiene tres números enteros, N, M y X, separados por espacio simple. La siguiente línea contiene N enteros, W[1], W[2], W[3] … W[N], separados por un solo espacio. La siguiente línea contiene N enteros C[1], C[2], C[3] … C[N], separados por un solo espacio.
Producción
Una forma óptima de llenar la mochila minimiza la capacidad no utilizada. Puede haber varias formas óptimas de llenar la mochila. Muestra la capacidad no utilizada de la mochila (un solo número entero en una línea por sí mismo) de una manera óptima. Si no hay forma de llenar la Mochila, salida -1. Líneas T de salida, una para cada caso de prueba.
Restricciones
1 ≤ T ≤ 10
1 ≤ M ≤ 100
M ≤ N ≤ 100
1 ≤ W[i] ≤ 100
1 ≤ C[i] ≤ M
1 ≤ X ≤ 10000
Entrada de muestra
4
9 3 10
2 3 4 2 3 4 2 3 4
1 1 1 2 2 2 3 3 3
9 3 10
1 3 5 1 3 5 1 3 5
1 1 1 2 2 2 3 3 3
3 3 10
3 4 4
1 2 3
3 3 10
3 3 3
1 2 1
Salida de muestra
0
1
-1
-1
Explicación
En el primer caso de prueba puedes seleccionar piedra 2, piedra 5 y piedra 9. La mochila estará completamente llena. Por supuesto, hay varias otras formas de seleccionar piedras para que la mochila esté llena. La capacidad no utilizada en todas esas formas es 0.
En el segundo caso de prueba, no puede seleccionar piedras de modo que la mochila esté completamente llena. Puede seleccionar piedras {1, 4, 9}, de modo que la capacidad no utilizada sea 10-1-1-5 = 3. Pero hay una mejor manera. Seleccione piedras {2, 5, 8}. La capacidad no utilizada es 10-3-3-3 = 1. Esta es la forma óptima. Hay otra forma que es óptima. Seleccione piedras {1, 5, 9}. La capacidad no utilizada es 10-1-3-5 = 1. En el tercer caso de prueba solo hay una opción. Selecciona piedras {1, 2, 3}. El peso total será de 11. Esto es más de lo que puede contener la mochila. En el cuarto caso de prueba no hay ninguna piedra de color 3. Por lo tanto, no es posible una selección válida de piedras.
La respuesta será -1.
Los que resolvieron una pregunta fueron seleccionados para la segunda ronda.
Ronda 2: (Entrevista por Skype – 45 Minutos)

1. Dada una cuadrícula de m*n, un jugador P1 y P2 están en el Node (x1,y1) y (x2,y2) respectivamente. Hay n gemas colocadas en diferentes posiciones de la cuadrícula, es decir (G1, G2, G3…..Gn). Calcula el costo mínimo requerido para recoger todas las gemas. Una gema puede ser escogida por un solo jugador. Las gemas deben elegirse en un orden particular, es decir, G1 debe elegirse primero, luego G2 y luego G3 y así sucesivamente.
Por ejemplo:
P1 (1,1) & P2(3,4)
Hay 4 gemas:
G1 (1,1), G2(2,2),G3(3,2),G4(4,2)
Costo total : 5
P1 elegirá G4.
P2 elegirá G1, G2, G3.
Complejidad : O(n)
Ronda 3: (Entrevista por Skype – 45 Minutos)
1. Dada una array de n elementos. Las operaciones ‘n’ deben realizarse en la array. Para cada operación se proporciona start_index, end_index,trim_value. Uno ha recortado el valor desde start_index hasta end_index inclusive. Si el valor en ese índice es mayor o igual que el valor de recorte, hágalo igual a trim_value; de ​​lo contrario, déjelo como está. Después de realizar operaciones ‘n’, encuentre el valor máximo de la array.
Complejidad: O(n)

Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo electrónico a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.