Experiencia de entrevista de Accolite | Conjunto 4 (en el campus)

Ronda 1 (escrita) 
Alrededor de 140 estudiantes se presentaron para la prueba fuera de línea. 

Había 20 MCQ que debían realizarse en (30 minutos), las preguntas eran de OS, DBMS, Datastructures. 
Después de esa ronda de codificación estaba allí (codificación en papel) en la que se dieron 3 preguntas y tenemos que intentar 2 (1 hora) 

1. Escriba su propia función sqrt(). la función debe devolver la raíz cuadrada si es un cuadrado perfecto; de lo contrario, devolver el suelo (sqrt (x)) 
2. Dada una array que contiene números enteros positivos y negativos. tienes que encontrar el número positivo más pequeño que falta. su código debe ejecutarse en tiempo O (n) y espacio O (1). 
3. Dada una serie de cuerdas, encuentra si las cuerdas se pueden enstringr o no para formar un círculo. Una string x se puede poner antes de otra string y si el último carácter de x es el mismo que el primer carácter de y. 

Después de la ronda 1, 19 personas fueron preseleccionadas para las entrevistas. 

Ronda 2 (Técnica) (1:30 hr) 
1. Cuéntame sobre ti. Mientras tanto, él (entrevistador) miró mi CV y ​​preguntó sobre mis proyectos. 
Realicé 3 proyectos, por lo que comenzó a hablar sobre CUDA y la programación paralela y cómo se implementó sobre imágenes para detectar bordes y cuánto factor de ganancia se logró. 
en segundo lugar, hice un proyecto sobre el sistema de votación en línea, por lo que me pidió que dibujara el diagrama ER, los esquemas y la relación entre ellos y sus funcionalidades. Aproximadamente (25-30) minutos de discusión. 

2. Dado un BST, debe encontrar el k-ésimo elemento más pequeño en O (n) tiempo y O (1) espacio. 

3. Suponga que tiene un servidor donde llegan múltiples requests en el momento de, t1, t2… Ahora suponga que un usuario accede en cualquier momento particular t en el servidor, entonces el servidor debería devolver la última solicitud. tienes que diseñar la estructura de datos para el mismo. 
Sugerí que podemos usar la pila que devolverá la última solicitud, luego me pidió que hiciera las últimas 10 requests y luego sugerí usar una array de estructuras que almacenará la solicitud no. y la marca de tiempo junto con ellos. Ahora, en cualquier momento, podemos mover 10 elementos hacia atrás, pero dijo que supongamos que el usuario presiona con frecuencia, entonces cada vez tendré que retroceder una y otra vez, por lo que la complejidad del tiempo será mucho más alto, acepté y sugerí otro solución similar a la implementación de LRU para que las requests que llegan con frecuencia se puedan procesar más rápido. luego modificó la pregunta de que el usuario quiere requests del último minuto y dio una pista de que es necesario almacenar todas las requests, ¿no podemos almacenar solo las requests de cada 1 minuto? 

4. Dada una array que contiene los precios de una acción de 30 días. Una persona tiene 1 acción que puede comprar y vender cualquier número de veces, debe encontrar la ganancia máxima que puede obtener.  
Sugerí un enfoque para crear dos arrays auxiliares MIN desde la izquierda y MAX desde la derecha y atravesar ambos simultáneamente si la diferencia entre MAX[i] y MIN[i] es mayor que maxDiff, luego actualice maxDIff y almacene el índice actual y agregue a la suma si index+ 1 no es igual al índice de iteración actual y finalmente devuelve la suma. Intentó algunos casos de prueba sobre mi código y descubrió que en algunos casos estaba dando una respuesta incorrecta, luego me preguntó cómo es mi dominio sobre la programación dinámica, le dije que lo sé. solo los estándar y ninguna otra experiencia, luego dijo que esta pregunta es de DP pero que estaba feliz de ver mi enfoque. (Alrededor de 20-25 min.) 

Ronda 3 (Técnica) (1:30 h) 
1. Ella (entrevistadora) me preguntó si intenté la tercera pregunta en la prueba escrita, le dije que solo intenté la primera y la segunda, luego me dio papel y me dijo que implementara la tercera pregunta. 
Sugerí un enfoque para usar dos arrays de estructuras (para los primeros caracteres y los últimos caracteres) que contendrán un valor booleano para marcar la presencia del carácter en la string y también su índice. Ahora compare dos arrays y vea si ambas arrays tienen el mismo valor booleano y diferentes índices para todos los primeros y últimos caracteres. Si es así, las strings pueden formar una string, de lo contrario no. Tenía dudas sobre mi solución, por lo que encontró un caso de prueba en el que mi código daba una respuesta incorrecta, por lo que me dijo que buscara otra solución, se me ocurrió otro enfoque y le dije que podemos hacer un gráfico dirigido desde el primer y el último carácter y luego atravesarlo en DFS, ahora supongamos que si el Node visitado se visita nuevamente y el recuento total de Nodes visitados es el mismo que el total de Nodes, entonces podemos decir que las strings formarán una string, 

2. Dado un BST, debe encontrar el k-ésimo elemento más grande en el tiempo O (n) y el espacio O (1). 
Sugerí declarar un conteo de variables estáticas que incrementará el conteo si el Node se visita en orden y si el conteo se convierte en k, imprimiré los datos de ese Node y regresaré. Luego me preguntó cómo funciona la estática y la diferencia entre global y estática. 

3. Dado un teclado móvil de, por ejemplo, un teléfono nokia y un diccionario que tiene todas las palabras significativas que se pueden formar, suponga que ahora el usuario escribe algún número (entrada), entonces su programa debe sugerir todas las palabras significativas que están presentes en el diccionario. Antes de implementar esto me preguntó la estructura de datos para almacenar el diccionario de manera eficiente y luego cómo usará esta estructura de datos para hacer código. 
Al principio, sugerí que almacenaría el diccionario en una array 2-D y lo ordenaría lexicográficamente, ahora supongamos que el usuario escribe un número, la string que comienza con ese carácter se busca en la array. ella dijo que redujera la complejidad porque el diccionario puede contener miles de palabras, luego sugerí usar la estructura de datos de prueba para almacenar y buscar la string, ahora estaba satisfecha y me pidió que explicara el concepto. 
4. Dado el orden previo y posterior de un gráfico, ¿cómo se puede construir el gráfico?  
Cuando escuché esta pregunta, estuve atascado durante 2 minutos, pero luego dije que, en lo que respecta al gráfico, no lo sé, pero no se puede construir un árbol único con preorden y posorden, así que como gráfico, por lo que se necesita en orden, ella estaba feliz y estuvo de acuerdo en la respuesta. 

Ronda 4 (Técnica) (2:30 h) 
1. Suponga que se proporciona una lista enlazada y hay un bucle, tiene que encontrar Nodes huérfanos en tiempo O(n). Los Nodes huérfanos son los Nodes fuera del bucle. 

2. Diseñar un sistema de señalización de tráfico BRTS de manera que no choquen dos vehículos. Tenga en cuenta que el autobús BRTS seguirá los semáforos BRTS B1, B2, B3, B4 en 4 direcciones y el tráfico regular seguirá los semáforos regulares R1, R2, R3, R4 únicamente. En la entrada, solo se proporcionó el tiempo de ciclo máximo (tiempo después del cual se repite el proceso) verifique todos los casos de esquina (los semáforos tienen solo dos estados (ROJO y VERDE)). Debe indicar cualquier combinación posible de semáforos bajo el tiempo de ciclo máximo . (Alrededor de 1 hora de discusión). 

3. Suponga que se proporciona una lista enlazada pero no sabemos el número de Nodes, tiene que encontrar el k-ésimo Node desde el último sin contar los Nodes.  
4. Dada una array de n enteros, algunos elementos están en el rango de 0 a n-1 y algunos fuera de rango pueden ser negativos. Debe reorganizar la array de modo que todos los elementos que están en el rango aparezcan en su índice y el resto aparezca en manera ordenada para los índices que no están presentes. Esto debe hacerse en tiempo O (n) y espacio O (1). 
Por ejemplo, supongamos que n=6,4 5 2 3 6 -3 salida= -3,6,2,3,4,5 

5. ¿Cómo puede implementar la pila usando queue/queues?  
6. ¿Cómo puede ordenar los elementos con la ayuda de la cola? 
Sugerí una solución de tiempo O(n) junto con O(n) espacio adicional. Me pidió que lo hiciera en el espacio O(1), así que sugerí deque, parecía satisfecho. 

solo 4 fueron seleccionados hasta esta ronda (yo fui uno de ellos) 

Ronda 5 (Bar Raiser) (30 minutos) 

1. encontrar la longitud del palíndromo más largo en una string a partir del índice 0. 
2. encontrar si una string A está presente en la string B o no.  
3. encuentre la longitud del prefijo más largo en una string 

Después de que estos 2 fueron seleccionados finalmente y desafortunadamente yo no estaba entre ellos, ya que podrían haber pensado que estaba un poco estresado. Por último, sugeriría que su enfoque y conceptos deben ser sólidos, ya que siempre plantean preguntas con algunas variaciones. 

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.