207 estudiantes fueron elegibles para la ronda de codificación
Ronda de codificación (HackerRank): 90 minutos; 3 preguntas ordenadas en dificultad
Pregunta 1: implementación básica de Hashing dadas 2 strings
Pregunta 2: técnica de ventana corredera
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 3: Problema 2-D Dp
ENTREVISTA-:
23 seleccionados
además, había una lista de espera de 5 Lista de espera extendida de 7 (aunque la lista de espera y la lista de espera extendida nunca fueron llamadas para una entrevista)
Nota: cada enfoque que indique y la optimización que realice se anotarán; también se anotará la pista que se le dará; menos pistas, más posibilidades de selección
La ronda 1:
30 minutos; sin currículum; sin introducción; 2 preguntas; codificación adecuada
Pregunta 1: dada una array, encuentre el máximo de a[i]+a[j] donde |ij|>1, es decir, i y j no son adyacentes
Solución: O(n) espacio dp(no aceptable)
4 máximo de array con pseudocódigo
Pregunta 2: dado un árbol binario completo con niveles ordenados
Input : 1
/ \
/ \
5 6
/ \ / \
/ \ / \
7 8 9 16
search for an element ( no extra space )
brute force-: O(n) simple traversal of tree
solución requerida: suponga que el elemento está presente y primero encuentre el nivel del elemento dado al ver el Node más a la izquierda de cada nivel en log (N) tiempo
ahora aplique la búsqueda binaria en el nivel
La búsqueda binaria se puede aplicar de 2 maneras.
1-: reducir el árbol yendo al subárbol izquierdo o derecho después de cada búsqueda central donde el elemento central puede ser el Node más a la derecha del subárbol izquierdo o el Node más a la izquierda del subárbol derecho
2-: un hecho interesante que se puede usar es que la representación binaria de un número puede ayudarlo a llegar a ese Node
por ejemplo, si es el cuarto nivel y el Node es 5 (numerando el Node más a la izquierda de ese nivel desde 0) representa 101
1 significa atravesar a la derecha mientras que 0 significa atravesar a la izquierda
1
/ \
2 5
/ \ / \
7 8 10 12
/ \ / \ / \
14 15 16 17 18 19
19 is on node 5(101 or RLR) from 1-(right)->5 -(left)->10 -(right)-> 19
Complejidad del tiempo-: log(N) * log(N)
14 clasificados para la ronda 2
Ronda 2: HR cum Técnico
preguntas basadas en currículum
1. trabajo de vectores en c++
2. Discusión del proyecto (parte principal de la entrevista)
3. conectividad de mesas en tu proyecto
4. Tipo de normalizaciones
5. Definición de BCNF y por qué he usado mit en mi proyecto
6. tu planificación para los próximos 3 años
7. ¿Por qué flipkart?
después de que le dije esa respuesta, me preguntó de dónde habías copiado la respuesta y le dije que había hecho bien mi tarea, así que me hizo otra pregunta que es-:
8. ¿Cómo te preparas para las prácticas?
IB para codificación, GFG para materias y recursos humanos de varios blogs
9. idiomas que conoces
etc.
8 estudiantes clasificados para la ronda final
Ronda 3:
30 minutos extendidos por una hora
me preguntó cómo me sentía
«Hambre de ambos, comida y Flipkart», respondí.
«Elige cualquier comida o flipkart». añadió
Dije «después de ser colocado, me encantaría cenar contigo».
impresionado por la respuesta comenzó la entrevista
Pregunta 1-: dada una serie de intervalos con algún valor de beneficio asociado a ellos
no puede elegir intervalos superpuestos y tiene que maximizar la ganancia
deje que el conjunto dado de intervalos tenga el formato {hora de inicio, hora de finalización, valor} {{1, 3, 100 }, {2, 4, 200 }, {5, 7, 500 }, {6, 8, 600 } , {1, 100, 800 } }
respuesta elige el intervalo 2 y 4 o elige el intervalo 5
la ganancia máxima es 200+600 = 800
Se aceptó el código DP de complejidad de tiempo O(N^2), pero la solución requerida era O(N*logN)
Pregunta 2-:
versión extendida de https://www.geeksforgeeks.org/minimum-steps-reach-target-knight/
2a-: dado un origen y un destino en un plano infinito
llegar a destino en pasos mínimos moviéndose como caballero (en ajedrez)
2b-: preguntas cruzadas sobre su enfoque por qué BFS pero no DFS
2c-: mapa o estructura de datos de array bidimensional para la función isvisited() ??
2d-: bloqueando algunos puntos FINITOS en el plano ahora, ¿te acercarás al trabajo? si no, corregirlo
la respuesta es aplicar BFS desde ambos extremos y si alguna de las 2 colas dadas está vacía, entonces no es posible llegar
2e-: complejidad temporal y complejidad espacial de su código
Pregunta 3-: dada una array de 0’s y 1’s
encuentre una longitud máxima X formada usando 1
1 1 1 1 0 1 1 0 0 1 0 1 1 0 1 0 BOLD 1's form a X of length 3 Brute Approach-:
suponga que m[i][j] es el centro de X y atraviesa por 1 en 4 diagonales complejidad O( m*n*(m+n) )
la solución aceptada fue la memorización del espacio O(4*m*n) y la complejidad del tiempo O(m*n)
donde dp[i][j][0], dp[i][j][1], dp[i][j][2], dp[i][j][3] almacenan el número máximo de 1 hasta ahora para cuatro diagonales (superior izquierda, superior derecha, inferior izquierda e inferior derecha) respectivamente de m[i][j]
al fin 5 fueron seleccionados para rol de tiempo completo 🙂