Experiencia de entrevista de DE Shaw – Part 1

21 de agosto de 2020: DE Shaw visitó VIT, Vellore para ocupar el puesto de Ingeniería de calidad y pruebas. El límite de CGPA fue 7.0 y más de 1500 estudiantes aparecieron para la primera ronda en línea.  

Primera ronda en línea: esta ronda se llevó a cabo en el portal Hackerrank con una duración total de 95 minutos y se dividió en 4 secciones.

1ra sección –  Sección Aptitud: 14 Preguntas por 28 minutos. Las preguntas eran moderadas y no demasiado difíciles de resolver. Pero estaba demasiado nervioso y lo arruiné por completo y creo que resolví alrededor de 5-6. Las preguntas eran una mezcla de razonamiento cuantitativo y aptitud general.

2ª sección – Sección Técnica: 12 Preguntas por 17 minutos. Esta sección consta de adivinar las preguntas de salida, conceptos generales de programación, preguntas de SQL y algunas basadas en estructuras de datos y algoritmos. Creo que dediqué demasiado tiempo a algunas preguntas en lugar de pasar a las siguientes. Logré resolver 5-6. 

3ra Sección – Hubo 2 preguntas de codificación. Se asignaron 20 minutos para la primera pregunta y 30 minutos para la segunda pregunta. Desde que he estado haciendo codificación competitiva, sabía que podía hacerlo bien en esta sección. 

(1) Dada una array de enteros positivos, averigüe la cantidad de sub-arrays que consisten solo en números primos: pregunta bastante simple, usó el tamiz de Eratóstenes y codificó en 7 minutos y pasó todos los casos de prueba en el primer intento. Construyo algo de confianza al pasar a la siguiente pregunta. 

(2) Esta fue una pregunta difícil. Dadas 2 arrays, la array A (que contiene solo 0 y 1) y la otra array de costos B del mismo tamaño. Necesitábamos convertir todos los elementos de la array A a 1 en costo mínimo. Para cada i-ésimo elemento en la array A, la conversión de 0 a 1 requiere un costo de B[i], pero si A[i-1] y A[i+1] son ​​1, entonces A[i] se puede convertir a 1 con un costo de 0 . Devuelva el costo mínimo posible para convertir todos los 0 en 1. Pensé durante unos 12-13 minutos, pero simplemente no pude encontrar ningún enfoque óptimo. Entonces inventé una solución BFS sobre todos los índices (enfoque de fuerza bruta) y, para mi sorpresa, pasé 9/13 casos de prueba.

18 estudiantes fueron preseleccionados para la RONDA 2.

Comenzó el día siguiente a las 12 de la noche. Hubo 2 entrevistadores. Fue una ronda de pares de códigos y solo se trataba de resolver problemas y duró casi 100 minutos y me dieron 5 preguntas de codificación consecutivas. Probaron la solución que codifiqué con casos de prueba ocultos reales para 3 preguntas. No se preguntó nada sobre proyectos y materias básicas. T

(1) Dado un BST, conviértalo en un BST completo (un árbol es un árbol binario completo si todos los niveles están completamente llenos, excepto posiblemente el último nivel y el último nivel tiene todas las claves tan a la izquierda como sea posible). Mi entrevistador me explicó la pregunta. Estaba sentado ocioso. Nada cruzó por mi mente. Codifiqué la solución para el árbol BST a AVL. Fue inflexible y quería una configuración de árbol completa. Me rendí y él no me dio ninguna pista. 

(2) Dada una string, encuentre el recuento de todas las substrings de una string que tenga al menos 3 caracteres únicos. Les conté sobre la solución de fuerza bruta, es decir, el enfoque n^2. Luego, les conté sobre el enfoque de 2 punteros y el uso de un mapa hash para almacenar caracteres únicos. Rápidamente codificó la solución y pasó todos los casos de prueba que dieron. 

(3) Dé una array de n filas y m columnas de 0 y 1. En cada fila, las primeras celdas tienen un valor 0 y las restantes tienen un valor 1. El problema es encontrar el índice mínimo de la columna que contiene un valor 1. Omití el O (n ^ 2) e inmediatamente di binario método de búsqueda O(n*logm). Me pidieron un mejor enfoque. Pensé por un tiempo y actualmente una solución ligeramente más optimizada. Más tarde, después de la entrevista, me di cuenta de que esto se puede hacer en tiempo lineal si atravesamos la array en diagonal.

(4) Dada una cuadrícula. Encuentre los movimientos mínimos para pasar de la posición (0,0) a (n-1,n-1). Pero, la cuadrícula tendrá algunos obstáculos y solo podemos atravesar como máximo k obstáculos. La posición libre se marcará con 0 y el obstáculo con 1. Me tomé mi tiempo y obtuve un Dijkstra optimizado con algunas modificaciones. Parecían satisfechos ya que mi código pasó 39/41 casos de prueba y estaba obteniendo TLE para los últimos 2 casos de prueba.

(5) Problema de separación de palabras ( https://www.geeksforgeeks.org/word-break-problem-dp-32/). Primero codificaron el enfoque recursivo, luego pidieron más optimización. Agregué una tabla dp para almacenar los resultados de las soluciones superpuestas. Pasaron casos de prueba de muestra y probaron contra algunos casos de esquina. Tenía mucha confianza ahora y pensé que había terminado y estaba listo para enviarlo. Pero, querían más optimización. Ahora, la optimización que nos brinda la solución dp es que podemos verificar si tenemos la posibilidad de particionar la string desde un índice determinado y si no es posible particionar desde ese índice, la tabla dp simplemente devolverá -1 y no lo verificaremos otra vez. Pero, el problema principal es si es posible, ¿qué sigue? Tenemos que generar todas las combinaciones a partir de ese índice nuevamente, que ya se calculó anteriormente. Entonces, estamos repitiendo cosas que ya hemos hecho. No estamos almacenando las combinaciones que ya se generaron a partir de ese índice. Para mayor claridad sobre lo que dije, lo que querían es::str dado = “aaaaaaaaaaa” dict = [“a”,”aa”,”aaa”,”aaaa”,”……”,] . Ahora, si dp devuelve verdadero desde un cierto índice (digamos 5), aún estaremos calculando todas las particiones de ese índice cuando lo visitemos otra vez en nuestro árbol de recursión. Aquí, aunque el índice 5 devolverá verdadero que al menos 1 partición es posible, pero aún así el sufijo [5: len-1] tendrá muchas posibilidades y dp no las devolverá. Los escuché con mucha atención y entendí las deficiencias de mi solución dp. Mi entrevistador esperaba que le devolviera también todas las combinaciones posibles. Una vez más, tomó algo de tiempo y me tomó alrededor de 20 minutos más cambiar todo y hacer un funcionamiento en seco. Ejecutaron mi código de nuevo, 

Permítanme explicar nuevamente lo que realmente querían de mí, por ejemplo, en un problema de cambio de moneda estándar, nuestro dp[i][j] no solo establece si una suma de i es posible o no al tomar las primeras j monedas, sino que en fact dp[i][j] también nos indica el número de formas en que se puede lograr una suma de i tomando las primeras j monedas. Querían este tipo de optimización.

Un entrevistador parecía complacido mientras que otro no. Finalmente, me preguntaron si tenía alguna pregunta para ellos. Dije que no. Estaba bastante feliz de cómo fueron las cosas. Realmente disfruté los desafíos. Pero fui rechazado después de esta ronda y alrededor de 6 personas fueron llamadas para la próxima ronda. Por fin, 2 candidatos fueron seleccionados para la pasantía.