Entrevista Directa | Conjunto 8 (fuera del campus)

Solicité Directi fuera del campus en su sitio web de carreras y recibí una llamada. Hubo un total de 5 rondas.

Ronda de codificación en línea: 1,5 horas
Hubo un total de 3 preguntas. Todos ellos eran preguntas de codificación que cubrían ad-hoc, dp, hashing, gráficos, etc. y solo podía hacerlo si realiza una codificación competitiva en línea regular. Esta ronda fue la más difícil y debe elegir sabiamente las preguntas que desea intentar. Hice dos de estos.
Q1- Pastel de queso con arándanos:
Descripción del problema
Hay una escuela en un pueblo. Tiene N clases. Un buen día, alguien donó pasteles de queso con moras azules B a las escuelas. Ahora necesita dividir estos pasteles de manera que:
Cada clase reciba al menos 1 pastel.
Cada clase compartirá el(los) pastel(es) entre los estudiantes.
Su objetivo es minimizar el número máximo de estudiantes por pastel en cualquier clase.
Aporte
La primera línea de la entrada contiene dos números enteros N y B separados por espacios que indican el número de clases y el número total de pasteles de queso con arándanos, respectivamente.
Las próximas N líneas contienen el número de estudiantes en cada clase.
Salida
Para cada caso de prueba, genere la cantidad máxima de estudiantes que compartirán un pastel.
Restricciones
2 <= N <= 5*105 N <= B <= 2*106 1 <= número de estudiantes en i-ésima clase <= 5*106 Entrada de muestra – 1 1 2 35 Salida de muestra – 1 18 Entrada de muestra – 2 2 7 20 50 Salida de muestra – 2 10

P2: Servicio de aparcacoches pobre
Nuestro Chef está abriendo un nuevo restaurante en la ciudad. Hoy, siendo la noche de inauguración de su nuevo restaurante, la gran popularidad del chef ha atraído a una gran multitud para la gran inauguración. Para comodidad de los clientes, los coches de todos los clientes se han marcado con un número del 1 al N, donde N es el número total de coches, correspondiente al número de su plaza de aparcamiento en la que debe aparcar cada coche. Debido a la gran multitud, el estacionamiento de automóviles está lleno excepto por un espacio de estacionamiento. Además, como los autos venían con demasiada frecuencia, no podían ser estacionados en su respectivo estacionamiento. El pobre valet del estacionamiento del restaurante, Raka, se queda con la ardua tarea de estacionar los autos en sus respectivos lugares. Afortunadamente para él, el estacionamiento se ha cerrado y no vienen más autos y ahora puede colocar los autos en sus lugares apropiados.
otro estacionamiento. Puede usar el espacio de estacionamiento vacío para mover los autos. Quiere acomodar los autos en la menor cantidad de movimientos posible. Raka te pide ayuda para encontrar la estrategia óptima para colocar los coches en los lugares adecuados.

Entrada
Un número entero T que denota el número de casos de prueba.
Para cada caso de prueba hay 2 líneas.
La primera línea coincide con un solo número entero N, donde N denota el número de automóviles.
La segunda línea contiene N enteros
K0 a KN-1, donde Ki representa el número marcado en el automóvil que se encuentra en el espacio de estacionamiento número i en la configuración inicial.
El estacionamiento número N se deja vacío.
Salida
Para cada salida de prueba, un solo entero M, donde M es el número de movimientos de vagones necesarios para colocar todos los vagones en su ubicación adecuada. Entrada de
ejemplo : 2 3 1 0 2 4 2 1 3 0

Salida:
3
4

P3:
Descripción del problema
del validador XML Definamos una stringcomo una etiqueta de apertura, donde x es cualquier letra pequeña del alfabeto latino.
Cada etiqueta de apertura coincide con una etiqueta de cierre del tipo, donde x es la misma letra.
Las etiquetas se pueden anidar entre sí, es decir, un par de etiquetas de apertura y cierre se pueden ubicar dentro de otro par.

Definamos la noción de un texto XML:

1) Una string vacía es un texto XML
2) Si S es un texto XML, entonces “ S ” (las comillas y los espacios son para mayor claridad) también es un texto XML,
donde a es cualquier letra latina minúscula
3) Si S1 , S2 son textos XML, luego «S1 S2» (las comillas y los espacios son para mayor claridad) también es un texto XML

Se le da una string. Debe verificar si la string dada es un xml válido o no.
Entrada La
primera línea contiene T número de casos de prueba
Para cada caso de prueba:
solo una línea que contiene la string xml etiquetada S.
Salida
Para cada caso de prueba,
una línea que contiene una string VERDADERO si s es un xml válido FALSO si no lo es.
Restricciones
0 < T <= 10 0 < longitud de S <= 10^5 Entrada de ejemplo: 2 <a><b></b></a>
<a><b></a>

Salida:
VERDADERO
FALSO

Explicación
En el primer ejemplo, <b></b> es un texto xml válido dentro de otro texto xml válido <a></a>.

Por lo tanto, la string total es texto XML

En el segundo ejemplo, <b> no tiene un par coincidente y, por lo tanto, la string no es un texto xml válido

Ronda 2: Cara a cara (Skype- 1 hora)
Esta fue una ronda de codificación de algoritmo DS+. Dijeron que habrá tres rondas de DS+Algo y es necesario pasar cualquiera de ellas dos, pasé las dos primeras para que no tomaran la tercera.
P1- Dados n rangos [a1, b1], [a2, b2], [a3, b3]…. [an, bn] donde todos los rangos se encuentran entre [0, 10^6]. Todas las entradas son números enteros. Proporcione el número total de enteros únicos en todos los rangos.
Ejemplo:
Entrada:
[1, 3]
[4, 9]
[3, 7]
salida: 9
Aquí insistió en hacer un código óptimo después de mi primer acercamiento, aprobó el segundo y me pidió que lo codificara. Tiene algunos buenos casos de esquina.

P2: Comprueba si una array se puede dividir en pares cuya suma es divisible por k.
Entrada: arr[] = {92, 75, 65, 48, 45, 35}, k = 10
Salida: Verdadero
Podemos dividir la array en (92, 48), (75, 65) y
(45, 35). La suma de todos estos pares es múltiplo de 10.

Ronda 3: Cara a cara (skype – 1 hora)
También una ronda de DS Algo. En esta ronda se hizo una pregunta.
Pidió que explicara sobre gráficos y preguntas generales de dfs y pidió que explicara el código de dfs y cuáles son sus aplicaciones. Entonces me hizo una pregunta.

P-Se te da un árbol. Cada Node puede tener cualquier número de hijos no específicos. Ahora creamos una string de 0 y 1. En primer lugar, suponga que está atravesando en dfs, por lo que cada vez que atraviese un Node, escriba el anexo 1 en la string atravesando todos sus hijos y nietos, ahora cuando regrese nuevamente a este Node en particular con todos los niños atravesados. agregue 0 a la string y regrese más arriba. De esta manera, debe enstringr con recorrido completo.
Ejemplo, tome un árbol con una raíz, sus dos hijos y el hijo izquierdo tiene un hijo más. Su string correspondiente será 11100100.
Ahora, la pregunta real es, dada esta string para un árbol, primero obtenga esta estructura de árbol de esta string y, en segundo lugar, identifique si esta estructura de árbol correspondiente puede tener más de 1 string posible, es decir, distinta de la dada.
(Sugerencia: el DFS se puede hacer de diferentes maneras según el niño que atraviese primero. Piense también en el isomorfismo del árbol, para todos sus subhijos).
Me tomé el tiempo, discutí cada paso con él, fue útil y me pidió que hiciera el código. Lo pude hacer, esta entrevista duro 80 mins.

Ronda 4: Ronda técnica (Skype – 45 minutos)
Esta ronda consistió en SO, DBMS, redes y fundamentos básicos de la computadora. Tuvimos una discusión detallada sobre todas las respuestas
Q1- sobre el proceso del consumidor productor y todos sus detalles conceptuales
Q2-solución del problema del consumidor productor, todas las soluciones (hardware y software) con explicación de las tres condiciones con ejemplos (exclusión mutua, progreso y espera acotada)
Q3-. Conducía a esclusas y semáforos. Me preguntó qué son los bloqueos mutex y las aplicaciones de bloqueos y semáforos.
P4- Una pregunta relacionada con el proceso, explicando para un programa todas sus etapas como proceso y su procesamiento (básicamente el nuevo->listo->ejecutando, etc.).
Q5- ¿Qué es swapper? Funciona.
Q6- Despachador y funcionamiento.
Q7- Thrashing y, en consecuencia, luego fue a pedir segmentación de paginación de demanda.
P8- ¿Qué es HTTP? ¿Cómo es un protocolo sin estado?
Q9- Modelo OSI y su analogía en la vida real si conocía alguna.
P10- Modelo TCP/IP y en qué se diferencia de OSI.
P11: una consulta SQL, no recuerdo exactamente, pero estaba en grupo y tenía conceptos de subconsulta y combinación.
Q12- Me preguntó indexación, tipos y qué estructura de datos usar. Le dije a Btrees y le pedí que explicara cómo y por qué ayuda. Me confundió con BST y preguntó, aunque la complejidad del tiempo será la misma, entonces por qué Btree (pensé y discutí, luego llegué a la conclusión sobre las escrituras de disco)

Ronda 5: (en general -1:30 horas, Skype)
Esta fue tomada por una persona importante que parecía gerente senior/ED.
Esto fue total tech+ds+algo+HR.
Q1- Me preguntó sobre mi proyecto de pasantía en detalle, sobre las tecnologías utilizadas, cuánto contribuí, etc.
Q2- Diseñe un Twitter localizado, que muestre los tweets de las personas dentro de un radio de 2 millas. Manejando los casos
2.1-Cada vez que una persona tuitea (dentro de 2 millas) debería aparecer en su página instantáneamente, básicamente empujando. (se pidió optimización de esto)
2.2-Diseñar las tablas de la base de datos, mostrar las relaciones entre ellas, qué atributos estoy tomando y por qué?
2.3- Se le pidió que escribiera 2 consultas sobre cómo extraer datos de la base de datos.
2.4-Cuando se me pidió que optimizara una consulta, brindé algunos métodos sobre el uso de uniones y subconsultas, pero me dio una pista sobre el uso de la indexación, así que usé la indexación (utilicé Btrees para la indexación; no escribí el código btree, solo el concepto)
Q3- Me explicó un concepto, es decir, dada una array de tamaño n, que contiene números del 1 al n, me pidió que escribiera una array que contuviera los números actuales, el número más cercano a la izquierda, que es más pequeño que el número actual.
Ahora la pregunta se da solo en esta array (la segunda), ¿puedes hacer la anterior? Me pidió que codificara mi lógica.

La clave básica es que debe practicar la codificación en plataformas en línea, así como geeksforgeeks, y pensar antes de responder, tomarse poco tiempo, pensar en todos los casos y pedir poca ayuda si se atasca. En general, fue una buena experiencia.

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.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.