Ronda 1: Ronda de codificación [Hackerrank] – 60 minutos – 2 preguntas
P1: Dado un conjunto de amigos mutuos en una clase, ¿puede dividir la clase en dos grupos de manera que:
Para todos los estudiantes en un grupo, cada estudiante es amigo de todos los demás estudiantes?
Nota: La amistad no es transitiva, es decir, si A y B son amigos, y B y C son amigos, no implica que A y C sean amigos.
Un grupo que tiene un solo estudiante es un grupo válido en sí mismo.
Entrada:
la primera línea de entrada contendrá t: número de casos de prueba
La primera línea de cada caso de prueba contendrá dos entradas N, M.
N Nodes y M relaciones.
Las siguientes líneas M contienen dos Nodes A, B.
AB significa que A y B son amigos.
Salida: SÍ si se puede, NO si no es posible tal división.
Ejemplo:
1
6 7
1 2
2 3
3 1
2 4
4 5
5 6
6 4
Salida de esto: VERDADERO
1-2-3 es un subgrafo completamente conexo.
4-5-6 es un subgrafo completamente conectado.
Seguimiento: GeeksForGeeks
P2: Dada una alfombra de tamaño a*b [largo*ancho] y una caja de tamaño c*d, uno tiene que colocar la alfombra en la caja en un número mínimo de movimientos. Un movimiento es doblar la alfombra por la mitad, ya sea a lo largo o a lo ancho.
Incluso se puede girar la alfombra 90 grados cualquier cantidad de veces, no se contará como un movimiento.
Ejemplo:
Caja = 6 * 10
Alfombra = 8 * 12
Salida: No de movimientos = 1
Dobla la alfombra a lo ancho, 12/2, de
modo que ahora la alfombra mida 6*8 y quepa bien.
Enfoque:
Trate de pensar en comparar números más pequeños y números más grandes. y simplemente dividiendo el número mayor por 2, y rotando tantas veces como sea necesario.
Resultados: El límite de esta ronda fue pasar al menos 7/8 casos de prueba del segundo trimestre. Nadie pudo pasar todos los casos de prueba del Q1.
5 de nosotros pasamos a la siguiente ronda.
Ronda 2: Ronda de depuración [bolígrafo y papel] – 50 minutos
Se proporcionó el código AC de conversión de Infijo a Postfijo, 90-100 líneas de código.
Diseño básico del código:
struct stack_node {
// using linked-list struct for stack nodes
// this one seemed fine, no bugs
// needed to be taken care of
push() // insert at the end approach used here
// changed the whole function to use
// insert at the beginning approach
// even malloc wasn’t used for new nodes
pop() // deletion from the end
// used deletion from front
// free wasn’t used in deletion
front() // used to get value of top of node
// no issues here
bool precedence() // had some issues in parameter
// checks, swapped the parameters
};
main()
{
struct node* head; // isn’t null initialised
// make sure not to use nullptr, as it’s C
int i = 0, j = 0;
for (i = 0; i < strlen(infixStr); i++) {
if (infixStr[i] >= ‘A’ && infixStr <= ‘Z’)
postfix[j] = infixStr[i]; // j++ needed here
do {
char stackTop = front(head);
// no check was done for head == null,
// either here or in front ()
pop(head);
// didn’t needed pop at the very first
// peek of stack top
if (precedence(infixStr[i], stackTop)) {
push(infixStr[i], head);
break;
}
else {
postfix[j] = infixStr[i];
// many things need to be corrected here
// pop ( ) needs to be called here
// the postfix j++ bug again
// postfix [j++] = stackTop, rather than infixStr
}
} while (1);
printf(“% s”, postFix); // missed adding a ‘\0’ terminator here
}
}
// This is just a gist of the actual code
Resultados:
3 de 5 pasaron a la siguiente ronda.
Ronda 3: Ronda de entrevistas [cara a cara] – 45 minutos
Candidato-1:
Comenzó con currículum.
Discusiones sobre trabajos anteriores [tenía 1 año de experiencia antes de M.Tech].
De ida y vuelta sobre los desafíos enfrentados según los múltiples procesadores o subprocesos múltiples.
Se explicó un error en el que malloc iniciaba el bloqueo del sistema y alguna otra señal intentaba adquirir el bloqueo, una condición de carrera. Y la metodología de cómo encontrar el origen del problema y las tareas asincrónicas en el centro del mismo.
El entrevistador parecía estar contento con eso.
En esta ronda sólo se iba a discutir una cuestión.
Dado un árbol binario y un número X, encuentre:
todos los Nodes a una distancia X de la raíz
todos los Nodes a una distancia X de los Nodes hoja
Ejemplo:
Gráfico:
1
1 1
1 1 1 1
1 1 0 0 0 0 0 0
y X = 2.
Pictóricamente, el gráfico se veía así:
Producción:
Nodes a la distancia 2 de la raíz: 4 [DEFG]
Nodes a la distancia 2 de la hoja: 2 [A y B]
Hacer un seguimiento:
La parte A de la pregunta era simple.
Para la Parte B:
Dedique tiempo a explicar los diferentes enfoques de la solución (comenzando con Exponencial, luego O(n^2)).
20-25 minutos habían pasado hasta este punto.
Luego intenté definir estructuras para crear un gráfico y usar propiedades de BFS [estructuras de lista de adyacencia].
El entrevistador me detuvo allí solo y sugirió pensar en una solución diferente, donde ni siquiera queremos crear un árbol.
Dado que obtuvimos la entrada como un árbol binario completo [como 0 y 1]
, formulé una fórmula para encontrar Nodes.
Formuló una solución simple a partir de ella
(si una hoja está en la posición de entrada [i] [j], entonces los Nodes resultantes estarían en
la entrada [i] [j / (2^X)].
Ahora aquí viene la parte difícil: el
entrevistador me preguntó si la solución resultante ya contiene el Node «A», luego idee una técnica para que no veamos A una y otra vez.
Esta fue una especie de mejora de rendimiento pequeña pero impactante.
Después de unos minutos de discusión, brindó un enfoque en el que no necesitamos buscar
Nodes de entrada [i] [j – 2^K], ya que darían la misma respuesta (definieron una estructura de almacenamiento de hojas de derecha a izquierda y de abajo hacia abajo). forma ascendente, llevando la cuenta de 0 en cada fila).
El entrevistador me pidió que lo codificara, pero no tuve mucho tiempo para hacerlo (tal vez estaba usando un cronómetro o algo así). Escribí un código parcial y se acabó el tiempo.
RESULTADO: SELECCIONADO
Candidato-2:
Comenzó con una breve introducción sobre mí.
Se dio el mismo problema (árbol binario). Se suponía que debía escribir el código completo, incluida la entrada. Pero le pregunté si serviría el pseudocódigo y estuvo de acuerdo. Hice un BFS simple para la parte (a) y DFS para la parte (b), una solución O(n), y él estaba feliz con eso. Me pidió que optimizara una vez que terminé con el código.
Discutí algunas otras preguntas en mi currículum más tarde, pero parece que fue solo porque terminé temprano con el código. Me preguntaron sobre mis expectativas de aprendizaje en Nutanix y sobre los problemas que enfrenté al hacer uno de los proyectos que había mencionado en mi currículum.
RESULTADO: SELECCIONADO
Candidato-3:
Comenzó con una pequeña introducción y preguntó sobre mis pasatiempos.
También me dieron el mismo problema. Me pidieron que no escribiera pseudocódigo y que escribiera el código en python. Pude resolver la primera pregunta y escribí el código. También resolví el segundo problema pero tuve problemas para escribir código. Después de unos 45-50 minutos, el entrevistador me detuvo.
Más tarde me hicieron un par de preguntas sobre mi currículum y prácticas anteriores (2-3 min)
RESULTADO: NO SELECCIONADO