Experiencia de entrevista de pasantía de Goldman Sachs (analista de verano, en el campus)

Recientemente, GS visitó nuestra universidad durante las pasantías para reclutar ‘Analistas de verano’ para 2019.

La ronda 1 fue una prueba en línea alojada en HackerRank. Estaba compuesto por 3 preguntas:
1. Pregunta de codificación (20 puntos, calificación parcial para casos de prueba): se basó en la manipulación de bits, donde tuvimos que crear «superstrings de bits» para una secuencia de números según un conjunto determinado de reglas. Implementé un BFS simple para todas las súper strings de bits posibles y pude pasar todos los casos de prueba.
2. 8 CS MCQ (10 puntos cada uno, -2 por incorrecto): las preguntas se basaron en gráficos, programación dinámica, análisis de complejidad, análisis gramatical, etc. Pude resolver la mayoría de estas.
3. 10 Quant MCQs (10 puntos cada uno, -2 por incorrecto): Estos se basaron en probabilidad, estadística, combinatoria, fundamentos de ML, ecuaciones diferenciales, etc. No pude hacer muchas preguntas aquí, pero ese fue el caso para la mayoría gente.

40 estudiantes fueron preseleccionados para entrevistas F2F en las que diferentes candidatos enfrentaron diferentes números de rondas de entrevistas por parte de varios paneles. Yo, personalmente, tuve 6 rondas.

1ra Entrevista – (40 mins)
1. Regiones máximas y mínimas que se pueden formar al hacer ‘n’ cortes en un pastel en 2D o 3D. Primero me hizo decirle mi enfoque y luego me pidió que derivara la fórmula del caso general observando el patrón o resolviendo la recursividad que se me había ocurrido.
2. Se dan n cuerdas y el costo de unir 2 cuerdas es proporcional a la suma de sus longitudes. Tuve que encontrar el costo total mínimo incurrido para crear 1 sola cuerda a partir de ellos. Sugerí un enfoque codicioso, en el que usé un Min-Heap para mi implementación.
3. Como mencioné Min-Heap en la pregunta anterior, me preguntó sobre las complejidades temporales de las diferentes operaciones en el montón. Luego me dio una array sin ordenar y me pidió que la ordenara usando Heap-Sort. Básicamente, quería que escribiera el código completo para la inserción, eliminación y recuperación de un montón en papel, lo cual hice. Después de lo cual, me pidió que hiciera las operaciones de montón en el lugar, es decir, usar el espacio O(1). Luego me pidió que comparara MergeSort, QuickSort y HeapSort. Me preguntó por qué los montones no se usan tan abundantemente como los BST, a lo que respondí que el Invariante en un montón para la comparación de dos elementos es muy débil en comparación con los BST (¡Gracias, MIT OCW!).

Segunda entrevista: (20 minutos)
Esta ronda se centró un poco más en mi currículum y mis intereses en informática. Me hizo 3 preguntas, una basada en la búsqueda binaria y otra basada en la manipulación básica de arrays. El tercero era el siguiente y tenía que resolverse en tiempo logarítmico.
https://stackoverflow.com/questions/12238241/find-local-minima-in-an-array
Me contó algunas cosas sobre la cultura laboral en GS, su experiencia allí y en qué proyectos generalmente trabajan los pasantes.

Tercera entrevista: esta fue la MÁS DIFÍCIL DE TODAS y duró 2 horas. El panel estaba formado por 2 chicos.
(a) Me hicieron 4 preguntas y querían que les comunicara lo que estaba pasando por mi mente y luego codificar todo en papel (¡literalmente, todo!).
1. Arbitraje de divisas: lo resolví tomando registros negativos de relaciones de cambio y tratándolos como pesos de bordes entre Nodes (monedas) en mi gráfico y encontrando un ciclo negativo usando Bellman-Ford.
2. Una pregunta sobre la concatenación de strings siguiendo un conjunto dado de reglas complejas. Me tomó bastante tiempo encontrar una solución ingenua y recursiva y, después de escribir, me pidió que optimizara. Dibujé el árbol de recursión y observé los subproblemas superpuestos y, por lo tanto, usé la tabulación para mejorar la complejidad del tiempo. Estaba contento con mi enfoque. Luego discutimos los enfoques de algunos problemas comunes de DP, como la distancia de edición, la mochila, etc.
3. Me preguntó cómo determina un compilador el orden de las tareas de compilación que se realizarán en los archivos MAKE e inmediatamente respondí Clasificación topológica. Luego me hizo escribir el código en papel y algunas preguntas sobre por qué funciona el método y su complejidad.
4. Una pregunta fácil sobre la búsqueda binaria. Tuve que encontrar la frecuencia de un determinado elemento en una array ordenada en el peor de los casos O (lgN) tiempo.

(b) El segundo panelista luego miró mi currículum y, dado que había mencionado un proyecto en curso sobre arquitecturas de servidor y computación en la nube, me hizo explicar el enfoque que iba a utilizar para simular el tráfico de red y luego profundizó en las ventajas y desventajas de la transformación de Arquitecturas tradicionales -> Virtualización -> Contenerización -> Arquitecturas sin servidor (FaaS). Quería que los comparara y contrastara y diera ejemplos, después de lo cual me pidió que dibujara aproximadamente: las capas de hardware, el sistema operativo host, las aplicaciones en cada una de las tecnologías.

Cuarta entrevista: (45 minutos)
El entrevistador era un ex alumno, por lo que tuvimos una breve charla sobre los clubes/departamentos a los que me había unido y otras actividades extracurriculares. Después de eso, me hizo algunas preguntas, todas las cuales pude responder.
1. Se basó en la estrategia: tenemos una pila de n monedas y 2 jugadores. En cada turno, un jugador puede retirar 1, 2 o 3 monedas de la pila. Suponiendo que ambos jugadores juegan de manera óptima y gana el jugador que vació la pila, ¿qué restricciones se deben poner en n para que el jugador que juega primero siempre gane?
2. https://stackoverflow.com/questions/4325200/find-the-majority-element-in-array.
Solución esperada en el tiempo O(n) y en el espacio O(1).
3. https://www.geeksforgeeks.org/closest-palindrome-number-whose-absolute-difference-min/
4. https://www.hackerrank.com/challenges/find-the-running-median/

Quinta entrevista: (40 minutos)
Me preguntaron en qué idioma soy competente y dije Java. Luego, me preguntó qué estructuras de datos había usado en Java y mencioné ArrayLists, Stacks, Priority Queues, HashMaps, TreeMaps, HashSets.
1. Dada una lista de objetos, en la que cada objeto puede o no ser otra lista de objetos, que puede o no ser otra lista de objetos, etc., escriba código para imprimir el contenido de todos los objetos que no son de lista.
2. Hay un flujo dinámico de tuplas que consta de datos de transacción (id de transacción, valor, nombres, etc.). Después de que entra cada tupla, necesito imprimir las transacciones máximas ‘k’ en función de sus valores existentes en la corriente actualmente y el costo amortizado debe ser O (1). Usé una cola de prioridad. Después de esto, se pidieron variaciones.
(a) ¿Qué pasa si ‘k’ está cambiando?
Vuelva a llenar la cola de prioridad cada vez que k cambie y almacene todas las tuplas existentes en un HashMap desde el que se puedan consultar.
(b) Si los valores de transacción son los mismos, queremos comparar según los identificadores. ¿Cómo implementas eso?
Anule la lógica predeterminada de compareTo() haciendo que la tupla (clase en Java) implemente una interfaz comparable.

Sexta entrevista: (45 minutos)
No se hicieron preguntas de codificación en esta ronda. Me pidieron que explicara todos y cada uno de los puntos principales que había mencionado en mi currículum y tuvimos una discusión sobre cada uno de esos puntos durante 10 a 15 minutos. Para los proyectos, me pidieron su implementación detallada y casos de uso.

¡Finalmente, fui seleccionado para la pasantía!