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

MCQ escrito
Había 20 preguntas de opción múltiple para hacer en 30 minutos y la mayoría de las preguntas técnicas eran de geeksquiz , una pregunta de sangre y relación y una pregunta simple de probabilidad.

No hubo marca negativa.

La ronda de codificación en papel
21 estudiantes fueron preseleccionados de la primera ronda de MCQ y en esta ronda se nos pidió que escribieramos los códigos (solo función) de 3 preguntas en 1 hora.
Q1. Se le da una array de tamaño MxN y solo los valores posibles en la array son
0, que representa una posición vacía
1, que representa una manzana fresca
2, que representa una manzana
podrida Una manzana podrida convierte todas las manzanas frescas en podridas que están adyacentes a ella en 1 unidad de tiempo. Dada una entrada a la array, debe calcular la cantidad de tiempo en que todas las manzanas frescas se pudrirán. También determine si todas las manzanas frescas podrían pudrirse en un tiempo finito o no. (20 puntos)

Entrada
2 1 0 2 1
1 0 1 2 1
1 0 0 2 1

Después de 1 unidad de tiempo, la array se transformará en
2 2 0 2 2
2 0 2 2 2
1 0 0 2 2

Después de 2 unidades de tiempo, la array se verá como
2 2 0 2 2
2 0 2 2 2
2 0 0 2 2

Por lo tanto, la salida debe ser de 2 unidades de tiempo. (La definición de adyacente solo incluye la celda izquierda, derecha, inferior y superior y NO la celda diagonal)

Q2. Se le proporciona un árbol binario y necesita averiguar la suma máxima de rutas entre los 2 Nodes de hoja del árbol binario (la suma máxima de rutas puede pasar o no a través de la raíz del árbol). A realizar en tiempo O(n) (20 puntos)

Q3. Se le da una array desordenada de enteros y necesita averiguar si existe un elemento mayoritario en ella . (El elemento mayoritario es aquel que aparece más de n/2 veces en una array de tamaño n). Para hacerse en tiempo O(n) (10 puntos)
El resultado de esta ronda se anunció tarde en la noche. Unos 7 u 8 estudiantes fueron llamados para las rondas de entrevistas cara a cara. Fui el primero en ser llamado y las rondas F2F comenzaron a las 11:30 p. m. y terminaron a las 5:00 a. m. de la mañana :-p Tuve la suerte de estar libre alrededor de la 1:15 a. m. 😀

Cara 2 Cara Ronda 1
Q1. No pude completar la pregunta 1 de la ronda de codificación de Paper (manzanas podridas). Ella (la entrevistadora) me pidió que rectificara el problema en él. Lo hice con la ayuda del espacio adicional MxN para la array visitada[][]. Ella dijo que lo hiciera en el lugar. Lo hice modificando los valores de Matrix a 3, 4, etc. 🙂

Q2. Encuentra el quinto desde el último elemento en una lista enlazada individualmente . En primer lugar, di una solución que tomó dos recorridos. Ella dijo que lo hiciera en 1 recorrido solamente. Lo hice tomando dos punteros y manteniendo una distancia de 5 Nodes entre ellos. Q3. Se le da una string, por ejemplo, si la string de entrada es «Soy abc xyz». La salida debería ser la string modificada como «xyz abc am I». Esto se debía hacer en el lugar y en tiempo O(n).

Q4. Se le da una array desordenada de enteros positivos y negativos. Debe averiguar el subarreglo de suma máxima en tiempo O (n). Debe encontrar los índices inicial y final junto con la suma.

P5. Se le da un BST y dos claves k1 y k2. Debe encontrar el ancestro común más bajo de las dos claves de forma iterativa. Sugerí la solución de almacenar la ruta en un vector y encontrar la primera falta de coincidencia del valor clave en la ruta raíz a k1 y raíz t k2.

Cara a Cara ronda 2
Q1. Tome el ejemplo de la codificación en papel alrededor de la pregunta de manzanas podridas y sugiera algún algoritmo en el que se le permita cambiar la posición de las manzanas podridas y frescas de tal manera que la array resultante convierta la menor cantidad de manzanas frescas en manzanas podridas. Sugerí un enfoque en el que primero contaría el número de manzanas frescas y podridas inicialmente y ordenaría todas las manzanas frescas en una subarray comenzando desde la posición (0, 0) y de manera similar ordenaría todas las manzanas podridas en la subarray desde (N-1 , M-1) posición. Estaba satisfecho con este enfoque.

Q2. Le dan un sistema de ascensores con 3 ascensores, tiene que sugerir algún algoritmo en el que la cantidad de tiempo que una persona espera en un piso x y ha presionado el botón de subir o bajar debe esperar la menor cantidad de tiempo y también la persona adentro el ascensor tampoco debe esperar demasiado para llegar a su piso de destino.

Q3. Hizo algunas preguntas generales sobre qué son los símbolos de un idioma. Qué es una gramática y reglas de producción. Luego me pidió que verificara si un código dado en algún idioma es sintácticamente correcto o no. Se le proporciona el conjunto de tokens válidos para este idioma y también la tabla de símbolos.

Q4. Se le proporciona un archivo de texto que almacena caracteres o palabras. Sugiera alguna forma de comprimir el archivo de modo que siempre haya una cierta cantidad de compresión de espacio posible.

Sugerí usar un árbol trie ya que todos los prefijos compartirán el espacio. Dijo que este enfoque depende de si la entrada tiene prefijos comunes o no.
Sugiere alguna otra forma. Luego dije que podemos usar la codificación Huffman y asignar el código más pequeño a la palabra más frecuente en el archivo y así sucesivamente. Dijo nuevamente que este enfoque también depende de si su entrada tiene palabras que aparecen con frecuencia o no.

Luego sugerí que, dado que todos los caracteres se pueden representar en términos de 8 bits o 1 byte. Podemos tomar el XOR del carácter anterior y siguiente y almacenarlo en la posición del carácter actual. De esta manera, siempre podría obtener una reducción de tamaño de/2 en el archivo codificado. La idea era similar a https://www.geeksforgeeks.org/xor-linked-list-a-memory-ficient-doubly-linked-list-set-1/

Estaba satisfecho y este fue el final de mi segunda ronda F2F. Me dijo que durmiera un poco porque tendrá una entrevista por Skype con nuestro gerente técnico seguida de una ronda de recursos humanos por la mañana.

3ra ronda (Skype)
Q1. Me pidió que definiera problemas NP y NP difíciles seguidos de la definición de autómatas y lenguaje regular. Luego me preguntó si son expresiones regulares.

Q2. Compartió conmigo un documento de Google y me dio una expresión regular como abab*(a|b) y una string de entrada s. Necesitaba escribir un código para verificar si la string de entrada dada podría generarse a partir de esta expresión regular o no. Devuelve un valor booleano verdadero o falso. Lo codifiqué en 5 minutos :-p

Q3. Se le da un árbol N-ario y un valor K. Debe devolver verdadero si existe algún camino de raíz a hoja que tenga suma = k y falso de lo contrario. Lo hice usando recursividad y en tiempo O(n).

Me dijo que tendrás tu ronda final de recursos humanos en algún momento. Sabía que iba bien porque parecía estar bastante satisfecho con mis respuestas.

Ronda final de recursos humanos
Esa fue la ronda que había estado esperando durante horas 😀
Ella (la HR) comenzó con algunas preguntas generales como cuéntame sobre ti y tus objetivos y metas en la vida. Cuáles son tus aficiones. Le dije que me encanta el arte y la artesanía. Me preguntó qué le haré si mañana es su cumpleaños :-p Fue muy amable y agradable para hablar. 🙂 No parecía que estuviera hablando con el HR. Era más como hablar con un amigo. Me preguntó qué me gustaba de Accolite y por qué deseaba unirme a la empresa y esas cosas. Finalmente discutimos sobre la escala salarial y la cultura laboral en Accolite.

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.