Pasé por un total de 6 rondas. La evaluación general se centró principalmente en estructuras de datos y algoritmos. Mi idioma preferido fue Java en todo momento. La primera ronda fue una ronda de codificación realizada en la plataforma Hackerrank. La segunda ronda fue nuevamente una ronda de codificación que se llevó a cabo en su propia plataforma: un codificador en presencia telefónica de un entrevistador. Después de despejar la ronda de coderpad, se debían seguir cuatro rondas de entrevistas cara a cara. Sin embargo, debido a la pandemia, las rondas cara a cara se realizaron a través de videollamadas.
Ronda 1 (Hackerrank):
Había dos enunciados del problema y se esperaba que yo los resolviera. Mi idioma preferido era JAVA.
A continuación se muestran los enlaces de la pregunta realizada:
1. https://leetcode.com/discuss/interview-question/625140/goldman-sachs-oa-2020-array-burst-problem-birthday-party (Segunda pregunta)
2. https://leetcode.com/discuss/interview-question/334671/goldman-sacks-july-2019-hackerrank-2
Ronda 2 (Teclado):
Se compartió un enlace de coderpad entre el entrevistador y yo. Había dos preguntas. El entrevistador me explicó detalladamente la duda tras lo cual procedí a resolverla. Después de que terminé, el entrevistador me pidió que compilara y ejecutara. Todos los casos de prueba pasaron con éxito. El entrevistador agregó algunos casos de prueba personalizados y ejecutó el programa nuevamente para verificar más el código. El mismo proceso se repitió también para la segunda pregunta.
Abajo están los enlaces de la pregunta que me hicieron.
1. https://www.geeksforgeeks.org/josephus-problem-set-1-a-on-solution/
2. https://www.geeksforgeeks.org/minimum-length-subarray-sum-greater-given-value/
Entrevista en persona
Hubo dos entrevistadores en todas las rondas técnicas. Todos los entrevistadores tenían entre 7 y 8 años de experiencia, la mayoría sirviendo en el nivel de VP. Cada ronda comenzaba con una breve introducción seguida de preguntas sobre mi experiencia, proyectos pasados y actuales, etc. Principalmente, las rondas se componían de preguntas de codificación basadas en estructuras de datos y algoritmos. Había pocas preguntas orientadas al idioma.
La última ronda fue del gerente de contratación. El gerente de contratación informó sobre su equipo, la tecnología en la que trabajan, su impacto general en el negocio de la organización, etc. A diferencia de otras rondas, en esta no se me pidió que codificara. Se compone principalmente de debates en profundidad y contrapreguntas.
Ronda 1 (Ronda técnica):
1. Dada una entrada secuencial de enteros en una array, encuentra el número que falta.
Caso de prueba: me dieron 76 77 79 80 81 como una entrada de array y se esperaba que devolviera 78.
Complejidad de tiempo esperada: O (logn)
Después de discutir diferentes enfoques, resolví el problema usando el principio de búsqueda binaria en O (logn).
Aquí hay una variación del problema solicitado https://www.geeksforgeeks.org/find-the-only-missing-number-in-a-sorted-array/?ref=rp . La diferencia que son los números enteros no necesita estar en el rango de 1 a n-1. Puede comenzar desde cualquier número entero.
2. Problema de Candy Crush: para una secuencia de números enteros, todos los mismos números consecutivos que aparecen más de 3 veces se cancelan. Al final devuelve la secuencia restante de enteros.
Me preguntaron sobre el tipo de estructura de datos que usaría. La complejidad temporal esperada era O(n).
Solución: Discutí el enfoque usando stack y haciendo un seguimiento de la parte superior de la pila, pude resolverlo en O (n).
Aquí está el enlace al problema: https://medium.com/algorithm-and-datastructure/candy-crush-remove-repeating-numbers-1020e3bddfb
3. Dada una array de enteros y un número k, encuentre todos los pares cuya diferencia sea divisible por k.
Caso de prueba: [3, 7, 11] k=4
Respuesta: 3
Explicación: Transformé la array reemplazando cada elemento con su módulo por k(%k). Luego calculó la frecuencia de cada elemento en la array modificada. Finalmente, agregar toda la frecuencia C2 daría como resultado la respuesta.
https://www.geeksforgeeks.org/count-pairs-in-an-array-whose-absolute-difference-is-divisible-by-k/
Me hicieron una pregunta adicional de probabilidad.
4. Un cubo de tamaño 3X3X3 metros está pintado por todos los lados. Si el cubo se corta en cubos pequeños de tamaño 1X1X1 y selecciona un cubo pequeño al azar. ¿Cuál es la probabilidad de que el cubo pequeño seleccionado no tenga ningún lado pintado?
Solución: Solo hay un cubo pequeño de tamaño 1X1X1 en el medio del cubo más grande que no se pintará. El número total de cubos más pequeños es 27. Por lo tanto, la probabilidad = 1/27.
Ronda 2 (Ronda técnica):
La ronda comenzó con una breve introducción seguida de una discusión sobre mis proyectos. Me hicieron preguntas relacionadas con el proyecto como: ¿Cuál es la diferencia entre autorización y autenticación? ¿A qué te refieres con pruebas de integración? ¿Qué es REST?
1. Dadas dos arrays de enteros, encuentre la suma máxima de rutas en dos arrays, siempre que pueda saltar de una array a otra en elementos comunes.
Caso de prueba: Array 1=> [1 4 5 99 100 ] Array 2 => [ 3 5 8 99 101]
Respuesta: 218
Solución: [(1+4) > (3)] + 5 + [(8) > (0)] + 99 + [(101) > (100)] = 5 + 5 + 8 + 99 + 101 = 218
Resolví esto usando el enfoque codicioso en O(m+n) donde m, n es el número de elementos en la primera y segunda array respectivamente.
https://www.geeksforgeeks.org/maximum-sum-path-across-two-arrays/
2. En una array bidimensional, encuentre todos los caminos posibles de abajo a la izquierda a abajo a la derecha con la restricción de que solo puede viajar hacia el este, noreste y sureste.
Solución: Resolví esto usando un enfoque de programación dinámica, calculando el costo de la ruta para (i,j) a (i+1,j+1), (i-1, j+1) y (i, j+1)
dp[i][j] = dp[i-1][j-1] + dp[i+1][j-1] + dp[i][j-1]; donde todas las celdas [i-1][j-1], [i+1][j-1] y [i][j-1] son celdas válidas (no negativas y sin exceder el límite fila-columna de la array).
El caso base es dp[fila-1][0] = 1;
El cálculo debe hacerse para cada columna comenzando de abajo hacia arriba y de izquierda a derecha, como se puede ver en la ecuación que depende de los datos de la columna anterior.
No pude encontrar ningún enlace exacto para el mismo problema disponible en ninguna parte.
3. Dados dos enteros n1 y n2, encuentre el número mínimo de operaciones requeridas para formar n2 a partir de n1 usando solo dos operaciones: multiplicación por 2 y resta por 1.
Caso de prueba: n1 = 5, n2 = 7
Respuesta: 3
Explicación:
5-1 = 4
4*2 = 8
8-1 = 7
Solución: se me ocurrió una solución para formar un árbol binario como n1 como raíz y llenar los niveles realizando operaciones * por 2 y -1 en los Nodes principales. Luego, encontrar el camino más corto de n1 a n2. Después de reflexionar sobre el problema, me di cuenta de que ni siquiera necesitamos construir un árbol, un mero uso de una cola básicamente bfs funcionaría.
https://www.geeksforgeeks.org/minimum-number-operation-required-convert-number-xy/
Ronda 3 (Ronda Técnica):
1. Dados n trenes con su hora de llegada y salida, encuentre el número mínimo de plataformas requeridas para acomodar a todos los trenes.
Complejidad de tiempo: O(nlogn)
2. Dada una array de números enteros, encuentre el número máximo usando los elementos de la array (https://www.geeksforgeeks.org/given-an-array-of-numbers-arrange-the-numbers-to-form-the-biggest- número/ )
Caso de prueba: [7, 4, 90, 3]
Respuesta: 90743
Solución: Resolví esto asumiendo que los elementos de la array son String y clasificándolos lexicográficamente. El entrevistador quería saber por qué la clasificación de números enteros no funcionaría aquí. Le di al entrevistador un contraejemplo y procedí con la solución basada en el comparador personalizado en Java. Me hicieron muchas preguntas de seguimiento relacionadas con Comparator, Clase anónima, Java 8, Expresión Lambda como una cosa lleva a la otra.
3. Diseñe una estructura de datos que admita la búsqueda de prefijos. Por ejemplo, cuando escribimos cualquier palabra en google.com, recibimos sugerencias basadas en la palabra que escribimos.
Solución: Me sometí a mucha discusión y, gradualmente, en pasos, pude llegar a una estructura de datos que podría cumplir el propósito. En funcionalidad, la estructura de datos no era otra que Trie, de la que no estaba al tanto hasta entonces. El entrevistador estuvo de acuerdo con que subiera hasta allí y no me pidieron que lo codificara porque no conocía a Trie anteriormente.
( https://www.geeksforgeeks.org/trie-insert-and-search/ )
4. Subsecuencia común más larga
Me hicieron esta pregunta porque aún nos quedaba tiempo. Acabamos de discutir el enfoque y el pseudocódigo para este.
( https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/ )
Ronda 4 (ronda del gerente de contratación):
La ronda comenzó con una introducción seguida de preguntas relacionadas con mi empleo anterior. ¿Por qué quiero cambiar tan pronto? ¿Por qué Goldman Sachs?
Basado en mi interés por las finanzas, las acciones y el comercio, el entrevistador me presentó un problema relacionado.
1. Diseñar una negociación de compra venta de acciones para diferentes empresas.
| Compañía | Precio de compra de acciones | Cantidad |
|---|---|---|
| infi | 10 | 100 |
| TCS | 30 | 50 |
| infi | 20 | 200 |
| Compañía | Precio de venta de acciones | Cantidad |
|---|---|---|
| infi | 15 | 120 |
Me pidieron que ideara un diseño que pudiera mantener registros de la transacción.
Para las 120 acciones de Infi que se vendieron, la cantidad se dividiría en 100+20 (según la cantidad de acciones que se compraron al mismo precio que se muestra en la primera tabla)
Entonces, el precio de compra sería 100*10 + 20*20. Después de vender 120 acciones, el registro en la tabla se modificaría mostrando las 100 acciones como agotadas.
Siempre que se vaya a vender una acción, debemos verificar la cantidad actual de existencias disponibles presente en nuestro libro mayor. Se mantienen registros separados para las acciones que se compran en diferentes fechas oa diferentes precios.
Solución: Presenté la idea de crear un mapa con el nombre de la empresa como clave y un objeto de clase personalizada como valor que contendría información sobre el precio de las acciones, la cantidad y la fecha de la transacción.
2. String siguiente permutación
https://www.geeksforgeeks.org/find-the-next-lexicographically-greater-word-than-a-given-word/
3. Dada una array de 0,1,2, clasifíquela.
Caso de prueba: [ 0, 1, 0, 2, 0, 2, 1]
Respuesta: [0, 0, 0, 1, 1, 2, 2]
Solución: Resolví esto manteniendo tres punteros y, en consecuencia, intercambiando 0,1 y 2 en complejidad de tiempo O (n).
( https://www.geeksforgeeks.org/sort-an-array-of-0s-1s-and-2s/ )
Pasé las rondas y fui seleccionado.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA