GOCC14: Google Online Coding Challenge 2020 – New Grad (India)

El 22 de agosto de 2020 se llevó a cabo el desafío en línea de Google 2020 para estudiantes universitarios 2021 . Antes de esta ronda, se realizó una preselección en función de su currículum.

La prueba se realizó en la plataforma HackerEarth. La prueba constaba de dos preguntas codificadas y el tiempo asignado era de 60 minutos. Mi conjunto de preguntas se mencionan a continuación.

• Primera pregunta: se le da una string S (que solo tiene letras minúsculas en inglés). En una operación, puede eliminar la substring «pr» de la string S y obtener la cantidad X o puede eliminar la substring «rp» y obtener la cantidad Y. 

Encuentre la cantidad máxima que puede obtener si realiza cero o más operaciones de este tipo de manera óptima. 

Nota : 

• La substring de una string S se define como una secuencia continua de caracteres en S.
• Después de eliminar «pr» o «rp», el orden de las letras restantes debe seguir siendo el mismo .

Ejemplo: 

abppprrr  (string S)  
5 4       (value of X and Y )

Producción:

15

Explicación : 

Aquí, S =” abppprrr” 

X= 5, Y=4.

Eliminar substrings se mencionan:

Eliminar “pr”, nueva string S=”abpprr”.

Eliminar “pr”, nueva string S=”abpr”.

Eliminar “pr”, nueva string S=” “.

En total, eliminamos pr 3 veces, por lo que la puntuación total es 3*X + 0*Y = 3*5 =15.

• Segunda Pregunta: Dado un arreglo A de N enteros y otro arreglo B de M enteros (no necesariamente distintos). La tarea es encontrar la cantidad mínima de elementos que se agregarán en B para que A se convierta en una subsecuencia de B. Tenga en cuenta que puede agregar elementos en cualquier posición en B. 

Una subsecuencia es una secuencia que se puede derivar eliminando algunos o ningún elemento de la secuencia sin cambiar el orden de los elementos restantes. 

Ejemplo: 

5 6           ( size of A array and B array)
1 2 3 4 5     ( A array )
2 5 6 4 9 12  ( B array )

Producción: 

3

Explicación: Necesitamos sumar 3 números en B de modo que A se convierta en una subsecuencia de B. 

Agregamos 1 al comienzo de B y los elementos 3, 4 entre 2 y 5. Ahora la array B se convierte en [ 1 , 2, 3, 4 , 5, 6, 4, 9, 12] y A es una subsecuencia de B.