Experiencia Entrevista Directi | Conjunto 16 (Pool-Campus para desarrolladores de aplicaciones)

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

Perfil ofrecido Desarrollador de Aplicaciones. Practica en el entorno de Codechef.
Seleccionaron a 3 estudiantes en esta ronda, fue un grupo de universidades del campus que participaron en toda la India. Soy de Puno. La ronda fue realmente un momento difícil no será suficiente. Los que hacen programación competitiva para ellos sería un poco fácil. Si incluso resuelve al menos uno, despejará esta ronda.

Problema de codificación 1: visita costosa
Tiene una cuadrícula de tamaño N x M. Las filas de la cuadrícula están numeradas de 1 a N de arriba a abajo y las columnas de la cuadrícula están numeradas de 1 a M de izquierda a derecha. Entonces, la esquina superior izquierda se indexa como (1,1) y la esquina inferior derecha se indexa como (N,M).

El costo de visitar una celda en el índice (i,j) se denota por C[i][j]. El costo de cambiar la dirección de su orientación en el índice (i,j) se denota por P[i][j].

Debe comenzar desde la celda (1,1) y llegar a la celda (N, M) con un costo mínimo. En la celda (1,1), puede mirar hacia ‘Derecha’ o mirar hacia ‘Abajo’. En cualquier momento, puede mirar hacia la derecha o hacia abajo.

Hay 2 tipos de movimientos permitidos:
1. Mueva una celda hacia la dirección de orientación, es decir, si está mirando hacia la ‘Derecha’, puede mover una celda hacia la ‘Derecha’ o si está mirando hacia ‘Abajo’, puede mover una celda ‘ Abajo’. El costo de visitar la celda (i,j) será C[i][j].
2. Cambie la dirección de orientación, es decir, si está mirando hacia la ‘Derecha’, ahora puede mirar hacia ‘Abajo’ o si está mirando hacia ‘Abajo’, ahora puede mirar hacia la ‘Derecha’. El costo de cambiar la dirección de orientación en la celda (i,j) será P[i][j].

Encuentre el costo mínimo para llegar a (N,M) después de comenzar desde (1,1).

Restricciones:
1 <= T <= 3
1 <= N,M <= 1000
1 <= C[i][j], P[i][j] <= 1000

Formato de entrada:
la primera línea de cada archivo de prueba contiene T, el número de casos de prueba.
En cada caso de prueba, la primera línea contiene dos enteros N y M que indican las dimensiones de la cuadrícula.
Las siguientes N líneas contienen M enteros, cada una de las cuales denota la array de costos C. Las
siguientes N líneas contienen M enteros, cada una de las cuales denota la array de costos P.

Formato
de salida: para cada caso de prueba, genere una sola línea que contenga el costo mínimo de llegar a (N,M) desde (1,1).

Ejemplo:

Entrada:
2
2 2
1 2
3 4
5 6
7 8
2 2
1 2
3 4
5 6
1 8

Salida:
13
9

Problema de codificación 2: string a número
Debe pasar una clave secreta a su amigo, que consta de todos los números, pero no confía en el operador. Entonces, en su lugar, pasa una string de caracteres. Se le ocurre un conjunto de reglas para asignar la string a la clave original.

1. Cada carácter de la string debe reemplazarse como sugiere la regla.

2. Si el lado derecho de la regla es un carácter, entonces este carácter debe reemplazarse nuevamente hasta que encontremos un número. El rango de los números se encuentra entre 1 y 9.

3. Si no se puede encontrar dicho número pero se detecta un ciclo, cada uno de esos caracteres debe reemplazarse con 0. Tenga en cuenta que esto incluye números que se asignan a sí mismos (autobucles).

4. Si no se detecta ningún ciclo y no se pudo encontrar ningún reemplazo de número, debe generar -1.

5. Si aparece un carácter en la string de prueba que no aparece en la asignación, genera -1.
Aporte

La primera línea de entrada contiene un solo entero T, el número de casos de prueba. Los casos de prueba T seguirán. Cada caso de prueba comienza con un mapeo. Un mapeo comienza con un número N, el número de reglas. Luego seguirán N líneas, cada línea en forma de AB, donde A será reemplazada por B. Luego sigue un número entero K, el número de strings de prueba. Luego siguen K líneas, cada línea consta de una string de prueba.
Producción

Para cada caso de prueba, imprima en la primera línea # seguido del número de caso de prueba, seguido de la string de reemplazo para cada string de prueba.
Plantillas de solución

En las plantillas de solución proporcionadas, complete la función cuya firma es

C/C++
void decode (int n, char orig[26], char mapeado[26],
int k, char input[32][128], char output[32][128])

Java
public static void decode (int n, char[] orig, char[] mapeado,
int k, String[] entradas, String[] salidas)

‘n’ es el número de asignaciones. ‘orig’ y ‘mapped’ almacenan los valores originales y mapeados respectivamente. ‘k’ es el número de consultas. ‘entradas’ son las strings codificadas. Se espera que almacene sus respuestas en ‘salidas’, que luego se imprimen en la plantilla. Tenga en cuenta que en JAVA, no asigne salidas. Se asignará y, por lo tanto, pondrá sus respuestas en salidas.

Nota: Puede editar el código a su gusto. Añadir/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

1 <= T <= 100
1 <= N <= 26
El lado izquierdo de la regla consiste en un solo carácter en minúscula
. El lado derecho de la regla consiste en un solo carácter en minúscula o un solo dígito distinto de cero.
Ningún carácter se asignará a más de un carácter,
es decir, no puede tener una situación en la que a se asigne tanto a b como a c.

Entrada de muestra
1
10
a b
b c
c a
d e
e f
f 9
g h
i j
j 7
k p
3
abcdefij
kabc
aza

Salida de muestra
#1
00099977
-1
-1

Explicación
String 1: a, b y c forman un ciclo, y d se asigna a e, que se corresponde con f, que se corresponde con 9, e i se corresponde con j, que se corresponde con 7.

String 2: k se asigna a p, que no se asigna a nada más. Por lo tanto -1.

String 3: el carácter z no aparece en el mapeo. Por lo tanto -1.

 
Problema de codificación 3: Suma binaria
En un árbol binario, la suma de diámetros entre dos Nodes de hojas se define como la suma de todos los Nodes en la ruta única 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 una sola hoja (dado que un Node de una sola hoja también es un diámetro válido: la ruta trivial de longitud 0 desde el Node de la hoja hasta sí mismo).
Aporte

La primera línea de entrada es el número T, que denota 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.
Producción

La salida consta de líneas T que indican el valor de la suma máxima del diámetro en el árbol binario para cada caso de prueba.
Plantillas de solución

En las plantillas de solución proporcionadas, complete la función cuya firma es

C/C++
int maxDiameterSum(int Nodes, int tree[511])

Java
static int maxDiameterSum (Nodes int, árbol int [])

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. Añadir/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 2k-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)

Solución:
Traté de resolver pero no borró los casos extremos.
<a href=”https://ide.geeksforgeeks.org/ReDZuU”>https://ide.geeksforgeeks.org/ReDZuU</a>

No lo memorices. No ayudará que te pregunten algoritmos en la entrevista.

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.