Experiencia de entrevista Flipkart | Conjunto 32 (para SDE-1)

Flipkart visitó recientemente mi universidad para reclutar SDE-1. Aquí les comparto mi experiencia de entrevista.

Primera ronda: 2 preguntas de codificación en HackerRank (90 minutos).

1. Dados algunos datos sobre los sistemas informáticos (como RAM, ROM, velocidad del procesador, batería, etc.). Debe imprimir las k computadoras principales en función de (i) RAM (ii) Si la RAM es la misma, entonces la ROM (iii) Si la ROM es la misma, entonces la velocidad del procesador, etc.
Restricciones: k <= 100
(cantidad de sistemas informáticos) n <= 1000000

Solución : cualquier clasificación O (nlogn) funcionaría. Pero lo que hice fue implementar Bubble Sort y ejecutar k-pases. Luego imprimió los últimos elementos k de la array. Tomó un tiempo O(nk) que estuvo bien ya que k <= 100.

2. Hay un laberinto de tamaño n*n. Tom está sentado en (0,0). Jerry está sentado en otra celda (se ingresa la posición de Jerry). Entonces hay k trozos de queso colocados en k celdas diferentes (k <= 10). Algunas celdas están bloqueadas mientras que otras no. Tom puede moverse a 4 celdas en cualquier momento (izquierda, derecha, arriba, abajo una posición). Tom tiene que recoger todos los trozos de queso y luego llegar a la celda de Jerry. Necesita imprimir el número mínimo. de los pasos necesarios para hacerlo.

Solución : Programación Dinámica.

Segunda Ronda: Alrededor de 1 hora (Presencial)

1. Dada una variación de la lista enlazada individualmente, donde cada Node puede tener 2 punteros: siguiente y hacia abajo. Debe aplanar la lista en una lista enlazada individualmente en la que cada Node tenga solo un puntero siguiente. Esto debe hacerse en el lugar, por lo que el puntero hacia abajo de cada Node debe establecerse en nulo.

Ejemplo:

1 -> 2 -> 3 -> 4
|         |
V         V
7 -> 8    10 -> 11
|
V
14 -> 15 -> 16
       |
       V
       20 -> 21
Output:
1 -> 7 -> 14 -> 15 -> 20 -> 21 -> 16 -> 8 -> 2 -> 3 -> 10 -> 11 -> 4

Solución : Primero le dije que lo hiciera iterativamente usando stack. Dijo que es demasiado complejo. Luego le dije que usara la recursividad, que consistía en aproximadamente 2 líneas de código. Me pidió que lo codificara y quedó completamente satisfecho. Recuerde cubrir todos los casos base y los casos de esquina.

2.1. Se le da una string. Imprime el primer carácter que no se repite.

Solución: Le pregunté la codificación de caracteres. Dijo ASCII. Le dije que tomara una array de enteros «conteo» de tamaño 128 con cada elemento establecido en 0. Escanee la string y para cada carácter ‘c’, cuente [(int)c]++. Luego, escanee la string nuevamente y cuando encuentre el primer carácter para el cual count[(int)c] == 1, imprímalo y sepárelo. Si no se encuentra tal carácter cuyo recuento[(int)c] == 1, eso significa que no hay respuesta (no hay ningún carácter que no se repita en la string).

2.2. ¿Qué pasa si la cuerda es muy larga? Hacer dos pasadas es caro.

Solución : usaría una array de estructura con dos elementos de recuento e índice. Cuando contamos[(int)c]++, también estableceremos index[(int)c] = índice de c en la string. Ahora, en lugar de escanear la string por segunda vez, escanee la array de estructura (para i = 0 a 127) y mantenga una variable temporal, tempIndex = MAX_INTEGER. Cuando encuentre count[i] == 1, verifique si index[i] <tempIndex. Si es verdadero, actualice tempIndex a index[i]. Al final, imprima el carácter en la string en index = tempIndex. Si tempIndex == MAX_INTEGER, eso significa que no hay respuesta (no hay carácter que no se repita en la string).

2.3. No se le da una string. Se le dan algunas consultas de Tipo 1 y Tipo 2.
Tipo 1: Agregar carácter (dado como entrada) al final de la string. La string está inicialmente vacía.
Tipo 2: Imprime el primer carácter que no se repite en la string que se ha formado hasta el momento.

Solución : siga construyendo la string para cada consulta de Tipo 1. Eso llevaría tiempo O(n) para cada consulta de Tipo 1 en una string no mutable. Si usamos un tipo de datos mutable, como StringBuilder en el caso de Java, tomaría tiempo O (1) para cada consulta de Tipo 1.
Para la consulta de Tipo 2, ejecute el algoritmo de 2.2 (arriba). Eso tomaría tiempo O (n) para cada consulta de Tipo 2. Si hay q consultas de Tipo 2, tardará O(nq) tiempo.

2.4. Resuelva 2.3 (arriba) en tiempo constante, es decir, para cada consulta (de Tipo 1 o Tipo 2) tome tiempo constante. Entonces, la complejidad general debería ser O(q) donde q = no. de consultas tipo 1 + núm. de consultas tipo 2.

Solución : tomó mucho tiempo (alrededor de 20 minutos) y probó muchas cosas antes de llegar a la siguiente solución.

• Construya una cola usando una lista doblemente enlazada (la lista enlazada individualmente también se puede usar con alguna modificación en el siguiente algoritmo, pero el entrevistador dijo que no se molestara).
• Construya un hashMap con Key = carácter y dos valores. Valor 1: booleano isPresentInQueue, Valor 2: Puntero a un Node en la lista vinculada.
• Cuando reciba un carácter (en Consulta Tipo 1), verifique si ese carácter está presente en hashMap.
  • Si no está presente, insértelo. Establezca isPresentInQueue en verdadero. Inserte el carácter hasta el final de la cola y mantenga el puntero (dirección) del Node insertado en la parte Valor 2 del hashMap (para ese carácter en particular). Esto llevará O(1) tiempo.
  • Si el carácter está presente en hashMap e isPresentInQueue se establece en verdadero para ese carácter, establezca isPresentInQueue en falso. Usando el puntero (dirección) en la parte Valor 2 del hashMap (para ese carácter en particular), elimine el Node de la lista vinculada. Esto llevará O(1) tiempo.
  • Si el carácter está presente en hashMap e isPresentInQueue es falso, ignore el carácter y avance. Esto llevará O(1) tiempo.
• Cuando reciba una consulta de tipo 2, simplemente imprima el frente (encabezado) de la lista vinculada. Esa sería la respuesta. Esto llevará O(1) tiempo.

Cada consulta (tanto del tipo 1 como del tipo 2) toma un tiempo constante. Entonces, la complejidad general es O (q) o O (número de consultas).

3. Explique la ordenación por fusión externa. Y trata de optimizarlo si es posible.

Solución : dije que no sé qué es la clasificación de combinación externa. Pero sé qué es la clasificación combinada y sé que la clasificación externa consiste básicamente en clasificar algunos datos que están presentes en la memoria secundaria (porque es demasiado grande y no se puede llevar por completo a la memoria principal). Entonces, dijo que ahora combine los dos. Di un par de algoritmos, el primero fue un enfoque ingenuo en el que dividiría los datos completos en k partes, llevaría cada parte a la memoria, la ordenaría, la empujaría a la memoria secundaria y así sucesivamente. Luego les conté algo parecido a Tournament Trees.

4. Explicar las complejidades del mejor, promedio y peor caso de todos los algoritmos de clasificación que conozco. En qué escenarios funcionan mejor.

Solución : Le hablé de 8 algoritmos, sus complejidades mejores, promedio y peores casos, y los escenarios en los que son útiles (para todos ellos). Créame, cada uno de ellos es útil en un caso u otro. Por ejemplo, la clasificación de burbujas es uno de los mejores algoritmos para resolver la pregunta de codificación planteada en la primera ronda.

5. Preguntas sobre mis proyectos.

6. Preguntas sobre un evento (concurso de codificación algorítmica) que organicé en el tech-fest de mi universidad.

Tercera ronda: por un gerente senior de contratación (a través de Skype). Alrededor de 1 hora.

1. Preguntas sobre mis proyectos.
2. Preguntas sobre un evento (concurso de codificación algorítmica) que organicé en el tech-fest de mi universidad.
3. Mi sitio web favorito. Le dije a quora. Me preguntó cómo quora entrega la información tan rápido. Le dije que no sé exactamente lo que hacen. Pero puedo decir lo que haría si necesito entregar la información tan rápido. Luego di una idea muy abstracta en la que hice uso de sistemas distribuidos, almacenamiento en caché (basado en usuarios particulares y sus intereses), etc.
4. Un poco más de discusión sobre temas generales (pero técnicos). Me habló de su trabajo y equipo. Preguntado sobre mis intereses y aspiraciones.

5. Rompecabezas : Tienes los ojos vendados (no puedes ver). Hay 100 monedas sobre una mesa. 80 son cruz y 20 cara a cara. Debe dividirlos en dos grupos de x e y cada uno (x+y = 100). Puede elegir cualquier moneda y lanzarla (si es cruz, se convertirá en cara y si es cara, se convertirá en cruz), pero no puede ver, por lo que no sabe qué moneda está lanzando. Al final, los dos grupos deben contener el mismo número de cabezas.
Solución: Me tomó casi 15-20 minutos resolverlo. Divida en el grupo 1: 20 y el grupo 2: 80. Lance todas las 20 monedas del grupo 1.

Muchas gracias a GeeksForGeeks.

Consejos generales:

• Le pedirán que escriba código sintácticamente correcto para todas sus soluciones. Por lo tanto, no dé una solución muy compleja (a menos que sea necesario).
• Preguntarán por la complejidad temporal y espacial de todas sus soluciones. Analizar adecuadamente las soluciones antes de contar la complejidad. En caso de soluciones recursivas, escriba las relaciones de recurrencia.
• No pienses solo en tu mente. Piensa en voz alta. Cuéntales todo lo que pasa por tu mente.
• Si conoce un problema de antemano, dígales que lo ha visto antes. Están interesados ​​en saber
  cómo resolverías un problema nuevo y esa es tu mejor oportunidad para mostrar tu proceso de pensamiento. Si no les dices que conoces la solución y haces el tonto, se darán cuenta y será malo para ti. Créeme, seguramente se darán cuenta de que conocías la solución de antemano.

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.