Entrevista de pasantía de Microsoft fuera del campus

Hubo una ronda de programación competitiva en línea que preseleccionó a alrededor de 100 estudiantes para el proceso de reclutamiento que tuvo lugar en el campus de VIT Chennai.

La primera ronda fue una prueba escrita. (1 hora)
Preguntas:
1. Dadas dos listas enlazadas individualmente ordenadas en orden ascendente, devolver una lista enlazada ordenada en orden descendente combinando elementos de ambas listas enlazadas dadas. (10 puntos)

2. Escriba casos de prueba para la pregunta anterior. (5 puntos)

3. Dada una string, devuelva la codificación de longitud de ejecución de la string. Por ejemplo: aaabbc -> a3b2c, abbbbc -> ab4c
(10 puntos)

4. Escriba casos de prueba para la pregunta anterior. (5 puntos)

5. Se proporciona algún programa en C++ y se debe determinar la salida. (No tuve tiempo de intentar esto) (2 puntos)

6. Encuentra el error en el programa dado. Un programa Java que toma dos listas enlazadas que representan dos números y devuelve una lista enlazada que es la suma de los dos números. (3 puntos)

Segunda ronda : Entrevista

Pregunta: Verifique si una lista enlazada simple es un palíndromo o no.
Empecé con la solución de encontrar el elemento del medio e invertir la segunda mitad de la lista enlazada, y luego hacer una comparación lineal de los elementos correspondientes. Esto funciona pero estamos cambiando el estado de la lista original.

Luego hablé sobre el enfoque en el que atravesamos desde el elemento medio hasta el final colocando cada elemento dentro de una pila. Luego, saltando uno por uno y comparándolos con los elementos del encabezado de la lista.
Esto requiere una complejidad de espacio O(n).

El enfoque final fue uno basado en la recursividad. Me tomé el tiempo para pensar esto desde cero. Una forma de resolver esto se da aquí . Mi enfoque fue un poco diferente. Primero encontrando el Node medio. Luego, pasar ese Node medio a la función recursiva. Cuando la recursividad toca fondo, verificamos si el puntero principal y el Node actual en la recursividad son iguales o no, también el puntero principal se actualiza al siguiente Node en cada llamada recursiva hacia atrás.

Discutido sobre cómo encontrar el Node medio usando punteros rápidos y lentos.

Luego me pidió que escribiera el código de extremo a extremo en cualquier idioma. Usé python para codificarlo. Me felicitó cuando usé funciones anidadas en python para mantener limpio el código.

Tercera ronda : Entrevista

Pregunta: dado un tablero de ajedrez y el caballo se coloca en el punto x, y. Dadas las coordenadas del destino, encuentre el menor número de movimientos que Knight debe realizar para llegar al destino.

Usé un enfoque basado en BFS para explorar todos los caminos. Había muchos casos de esquina para comprobar. Se espera que discutamos todos estos casos.

PD: si tiene enfoques eficientes para resolver cualquiera de los problemas anteriores, póngalos en la sección de comentarios. Actualizaré en el artículo.