La ronda 1:
La primera ronda fue una ronda de codificación en línea que consistió en 3 preguntas de codificación que se intentaron en 90 minutos.
Pregunta 1 :-
Hay una reunión programada en una oficina que dura el tiempo t y comienza a la hora 0. Entre la reunión hay n presentaciones cuyas horas de inicio y finalización se dan, es decir, la i-ésima presentación comienza a las s[i] y finaliza a las e[i ]-1. Las presentaciones no se superponen entre sí. Se le da k, el número máximo de presentaciones que puede reprogramar manteniendo intacto el orden original. Tenga en cuenta que la duración de la presentación no se puede cambiar. Solo puede cambiar la hora de inicio y finalización. Su tarea es maximizar el período de tiempo más largo en el que no hay ninguna presentación programada durante la reunión.
Restricciones: –
1<=t<=1, 000, 000, 000
0<=k<=n
1<=n<=100, 000
e[i]<=s[i+1], 0<=i <n-1
s[i] < e[i] para 0<=i<=n-1
Pregunta 2 :-
Se le proporciona una cuadrícula de x m que consta de valores 0 y 1. Un valor de 1 significa que puede ingresar a esa celda y 0 implica que no se permite la entrada a esa celda. Comienza en la esquina superior izquierda de la cuadrícula (1, 1) y debe llegar a la esquina inferior derecha (n, m) de modo que solo pueda moverse hacia la derecha o hacia abajo desde cada celda. Su tarea es calcular el número total de formas de alcanzar el objetivo.
Restricciones: –
1<=n, m<=10, 000
Pregunta 3 :-
Se le da una lista de aristas en un gráfico y para cada par de vértices que están conectados por una arista, hay dos aristas entre ellos, una arista curva y una arista recta, es decir, la tupla (x, y, w1, w2) significa que entre los vértices x e y hay una arista recta de peso w1 y una arista curva de peso w2. Te dan dos vértices a y b y tienes que ir de a a b a través de una serie de aristas de manera que en todo el camino puedas usar como máximo 1 arista curva. Su tarea es encontrar el camino más corto de a a b que satisfaga la condición anterior.
La ronda 2:
Esta fue una ronda técnica y duró aproximadamente una hora. Me pidieron que diseñara un juego de Snakes And Ladder y lo codificara en el idioma de mi elección. Usé números aleatorios para diseñar el tablero y luego me pidieron que jugara el juego entre dos jugadores y codifiqué lo mismo. Introdujo un truco a la pregunta y me pidió que calificara la dificultad del tablero. Pensé en términos de la ruta más corta (búsqueda primero en amplitud) desde el principio hasta el final, pero dijo que un mejor enfoque sería calcular la probabilidad de llegar a un número en particular desde el principio. Así que usé Programación Dinámica para calcular la probabilidad de alcanzar un número particular en x cantidad de movimientos donde 1<=x<=límite máximo en la cantidad de movimientos después de los cuales se declararía un empate. Luego me preguntó que no quería un juego que terminara en solo 15 movimientos, ya que eso haría que el juego fuera aburrido. Entonces me dijeron que calculara la probabilidad de que el juego termine en 15 a 100 movimientos. Finalmente me pidió que dijera con solo mirar la posición de los jugadores quién estaba en la posición ganadora en ese momento. Quedó satisfecho con mis respuestas.
Ronda 3:
Esta fue una ronda de resolución de problemas y duró 75 minutos. Me hizo una pregunta muy complicada. Aquí va…
Hay 3 enteros a, b, w.
Hay 2 ecuaciones –
- w+a=b
- a (Y bit a bit) b =0;
Me dieron el valor de w y me pidió que calculara el número de pares (a, b) que satisfacían las dos ecuaciones. Suponga que no hay desbordamientos. Utilicé Recursion + Bit Manipulation para resolver esto y pareció satisfecho con mi enfoque, aunque también necesité algo de su ayuda.
PD: – Recibí una llamada para una oferta 3 horas después.