Preguntas de la entrevista de Directi

Tomé la Ronda 1 de Codificación del reclutamiento del campus Direct I hoy. Compartiendo las 2 preguntas que se han hecho.

Pregunta 1 (inversión de substring óptima):
se le da una string S. Cada carácter de S es ‘a’ o ‘b’. Desea invertir exactamente una substring de S de modo que la nueva string sea lexicográficamente más pequeña que todas las demás strings que puede obtener al invertir exactamente una substring.
Por ejemplo, dado ‘abab’, puede optar por invertir la substring ‘ab’ que comienza en el índice 2 (basado en 0). Esto le da la string ‘abba’. Pero, si elige invertir la substring ‘ba’ a partir del índice 1, obtendrá ‘aabb’. No hay forma de obtener una string más pequeña, por lo tanto, invertir la substring en el rango [1, 2] es óptimo.

Entrada:
la primera línea contiene un número T, el número de casos de prueba.
Cada caso de prueba contiene una sola string S. Los caracteres de la string serán del conjunto {a, b}.

Salida:
Para cada caso de prueba, imprima dos números separados por comas; por ejemplo “x,y” (sin las comillas y sin ningún espacio en blanco adicional). “x,y” describe el índice inicial (basado en 0) y el índice final respectivamente de la substring que debe invertirse para lograr la string lexicográfica más pequeña. Si hay múltiples respuestas posibles, imprima la que tenga la ‘x’ más pequeña. Si todavía hay múltiples respuestas posibles, imprima la que tenga la ‘y’ más pequeña.

Restricciones:
1 ? t? 100
1 ? longitud de S? 1000

Sample Input:
5
abab
abba
bbaa
aaaa
babaabba

Sample Output:
1,2
1,3
0,3
0,0
0,4 

Atención:
Las restricciones están diseñadas de tal manera que un algoritmo O(N ³ ) por caso de prueba no pasaría.

Pregunta 2 (Consultas de base de datos): 2 puntos
Tiene un conjunto de N objetos. Cada uno de estos objetos tiene ciertas propiedades asociadas con ellos. Una propiedad está representada por un par (clave, valor). Por ejemplo, suponga que tiene los siguientes dos objetos.

Tower:
{
      (height, 100), (weight, 50),
      (xposition, 25), (yposition, 36)
}

Tree:
{
      (area, 100), (noofleaves, 500),
      (height, 25), (yposition, 36)
}

Cada objeto que tengas tendrá como máximo 4 propiedades. Un objeto tendrá al menos 1 propiedad. Tenga en cuenta, a partir de los dos objetos anteriores, que no es necesario que las propiedades clave sean las mismas para todos los objetos. Además, no es necesario que la clave sea diferente.
Ahora, dados N de tales objetos, desea responder M consultas. Cada consulta está representada por un conjunto de propiedades (nuevamente, como máximo 4 propiedades y al menos 1 propiedad). La respuesta a la consulta es el número de objetos en el conjunto, que tienen todas las propiedades dadas. Dos propiedades se consideran iguales si tanto la clave como el valor coinciden.
Por ejemplo, si tiene los dos objetos anteriores, la respuesta para las siguientes consultas es
Consulta: { (altura, 100), (posición y, 36) }
Respuesta:1 // coincide con Torre, pero no con Árbol

Consulta: { (yposition, 36) }
Respuesta: 2 // coincide con Tower y Tree

Consulta: { (altura, 100), (sin hojas, 500) }
Respuesta: 0 // ni la Torre ni el Árbol satisfacen ambas propiedades

Entrada:
La primera línea de entrada contiene N y M. A esto le sigue la descripción de los N objetos. La descripción del i-ésimo objeto comenzará con un número k, que es el número de propiedades asociadas con el objeto. Las siguientes k líneas contienen dos strings separadas por espacios: la clave de propiedad y el valor de la propiedad. Tenga en cuenta que el valor de la propiedad no es necesariamente un número entero (aunque esto es así en el ejemplo anterior).
Esto es seguido por la descripción de consultas M. El formato de una consulta será exactamente el mismo que el de los objetos. Verifique la entrada de muestra para aclaraciones.
Un archivo de prueba contendrá solo un caso de prueba. Un solo caso de prueba puede contener varias consultas.

Salida:
Imprimir M líneas. Cada línea debe ser la respuesta de la consulta respectiva.

Restricciones:
1 ? n? 10000
1 ? ¿M? 100000
1 ? k? 4

Sample Input
2 3
4
height 100a
weight 50b
xposition 25a
yposition 36b

4
area 100a
noofleaves 500
height 25
yposition 36b

3
weight 80
xposition 25a
yposition 36b

1
yposition 36b

2
xposition 25a
yposition 36b

Sample Output:
0
2
1

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.