Entrevista Directa | conjunto 13

Hubo una ronda de codificación en CodeChef durante 3 horas. No puede usar casos de prueba personalizados dentro de su IDE o editar su código después de ejecutarlo.

Problema 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. Se proporciona una cuadrícula de alfabetos y un conjunto de 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 
/* return 0 for false, 1 for true. */ 
int findWordInAGrid(char grid[128][128], int m, int n, char word[32]) 

C++ 
bool findWordInAGrid(char grid[128][128], int m, int n, char word[32]) 

Java 
static boolean findWordInAGrid(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: abcdefghi Y el conjunto de palabras que se buscarán son: abc abedhi efgh

El resultado del ejemplo anterior debería ser: abc: true abedhi: true efgh: false Restricciones 1 ? m, n? 100

Problema de codificación 2: Obtendrás 2 puntos por resolver este problema

Se le da un árbol enraizado. El árbol no es necesariamente binario. El árbol contiene N Nodes, etiquetados del 1 al N. Se le proporciona el árbol en forma de array P[1..N] de tamaño N. P[i] denota la etiqueta del padre del Node etiquetado i. Para mayor claridad, puede suponer que el árbol cumple las siguientes condiciones.

• La raíz del árbol está etiquetada como 1. Por lo tanto, P[1] se establece en 0. El padre del Node T siempre tendrá una etiqueta menor que T. Por lo tanto, P[i] < i siempre será verdadero. Todos los Nodes contienen un valor mutable (o, más simplemente, una variable), que inicialmente se establece en 0.
• Se le pide que realice varias operaciones del siguiente tipo ADD XY: agregue Y al valor en el Node X. ADDUP XY: agregue Y al valor en el Node X. Luego, agregue Y al valor en P[X] (es decir, el padre de X). Luego, agregue Y al valor en P[P[X]] (es decir, el padre de P[X]).. y así sucesivamente, hasta que agregue Y al valor en la raíz.
• Una vez que haya realizado todas las operaciones dadas, se le pedirá que responda varias consultas del siguiente tipo VAL X: imprima el valor en el Node X. VALTREE X: imprima la suma de los valores en todos los Nodes del subárbol con raíz en X (incluido X ).
• Entrada: la primera línea de entrada contiene el número 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 los números N, M y Q respectivamente (separados por un carácter de espacio simple). N representa el número de Nodes. M representa el número de operaciones que debe realizar. Q representa el número de consultas que debe responder. Las siguientes N líneas contienen un número cada una, representando la array P[1..N]. Por supuesto, el número en la primera línea siempre es 0. Las siguientes M líneas contienen la descripción de la operación respectiva. Una operación será «SUMAR XY» o «SUMAR XY» (sin las comillas).
• Consulte la declaración del problema y la explicación de E/S de muestra para obtener claridad sobre el significado de las operaciones. Después de las operaciones, las siguientes líneas Q contienen la descripción de las consultas. Una consulta será «VAL X» o «VALTREE X» (sin las comillas). Consulte la declaración del problema y la explicación de E/S de muestra para obtener claridad sobre el significado de las consultas. Salida Imprime el resultado de cada consulta en una sola línea. Dado que la respuesta para algunas consultas puede ser demasiado grande, imprima el resultado módulo 1,000,000,007. No imprima ninguna línea en blanco entre los casos de prueba. Restricciones 1 ? t? 10 1 ? n? 50000 1 ? ¿M? 50000 1 ? ¿Q? 50000 1 ? X ? n 1 ? ¿Y? 50000 El archivo de entrada tendrá un tamaño inferior a 2 MB.

Entrada de muestra 2 5 5 3 0 1 1 1 3 ADD 1 10 ADD 2 20 ADD 3 30 ADD 4 40 ADDUP 5 50 VAL 3 VALTREE 3 VALTREE 1 7 4 5 0 1 2 2 2 1 2 ADD 6 76 ADDUP 1 49 ADD 4 48 SUMA 2 59 VALTREE 1 VALTREE 5 VAL 5 VAL 5 VALTREE 2 VAL 2

Salida de muestra 80 130 250 291 0 0 107 59 Explicación En el primer caso de muestra, al final de la aplicación de las operaciones, los valores en cada uno de los Nodes son los siguientes 1: 60 2: 20 3: 80 4: 40 5: 50 Además, la suma de los valores de todos los Nodes en el subárbol con raíz en cada uno de los Nodes es la siguiente 1: 250 2: 20 3: 130 4: 40 5: 50

Problema de codificación 3: recibirá 1 punto por resolver este problema

En un árbol binario, la suma de diámetros entre dos Nodes de hojas se define como la suma de todos los Nodes en el camino único cuando se viaja de una hoja a la otra. Suponga que el árbol es un árbol binario completo y que cada Node hoja está a la misma profundidad desde la raíz del árbol. Encuentre el valor de la suma máxima del diámetro en un árbol binario. Tenga en cuenta que el diámetro máximo también puede ser un Node de hoja única (dado que un Node de hoja única también es un diámetro válido, la ruta trivial de longitud 0 desde el Node de hoja hasta sí mismo).

Entrada : la primera línea de entrada es el número T, que indica el número de casos de prueba. La entrada para cada caso consta de 2 líneas. La primera línea consiste en el número de Nodes N en el árbol. La siguiente línea consta de los números A[1..n] que denotan el valor de cada Node en el árbol. El primer elemento de la entrada es el elemento raíz del árbol. Teniendo en cuenta que el índice del elemento raíz es 1 en el siguiente problema, el hijo izquierdo del i-ésimo elemento en la entrada es el (2*i)-ésimo elemento y el hijo derecho del i-ésimo elemento es el (2*i+1)-ésimo elemento.

Salida  : la salida consta de líneas T que indican el valor de la suma del diámetro máximo en el árbol binario para cada caso de prueba. Plantillas de solución En las plantillas de solución provistas, complete la función cuya firma es C / C++ int maxDiameterSum(int nodes, int tree[511]) Java static int maxDiameterSum(int nodes, int[] tree) El primer argumento de maxDiameterSum es el número de Nodes en el árbol. El segundo argumento es el árbol, presentado en un formato de array como se describe en la Sección de entrada anterior. maxDiameterSum debe devolver el valor de la suma de diámetro máximo en el árbol binario. Nota: Puede editar el código a su gusto. Agregar/eliminar encabezados. Agregar/eliminar métodos. Y así sucesivamente… Siempre y cuando su código final resuelva el problema con Entrada y Salida como se describe arriba.

Puede enviar su propio código, sin utilizar la plantilla en absoluto. Restricciones T ? 100 n? 511 El rango de valor de los Nodes está entre 100000 y 100000 N es de la forma 2 k 1, donde k es la altura del árbol. Entrada de muestra 1 7 2 4 5 8 4 3 6

Salida de muestra 22 Explicación La ruta seguida para obtener la suma máxima del diámetro en este caso es 8 (Node hoja) => 4 => 2 => 5 => 3 (Node hoja)
Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escriba un artículo y envíelo por correo 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.