Experiencia de entrevista de Goldman Sachs | Set 31 (Para Prácticas)

• Hay 36 caballos. Tenemos que encontrar los 3 caballos más rápidos. En una carrera, máximo 6 caballos pueden correr. ¿Cuántas carreras se requieren como mínimo para obtener el resultado sin usar un cronómetro?

  Primero podemos hacer 6 carreras tomando 6-6 caballos y obtener el caballo más rápido en cada carrera.
  A1, A2, A3, A4, A5, A6
  B1, B2, B3, B4, B5, B6
  C1, C2, C3, C4, C5, C6
  D1, D2, D3, D4, D5, D6
  E1, E2, E3, E4, E5, E6
  F1, F2, F3, F4, F5, F6
  Aquí A1>A2>A3>A4>A5>A6 y de la misma manera para los demás.
  Ahora tomemos el caballo más rápido en cada carrera y luego hagamos una carrera entre ellos. Deje que el resultado sea A1>B1>C1>D1>E1>F1. Obtenemos el caballo más rápido (A1).
  Ahora necesitamos encontrar el segundo y tercer caballo más rápido. Los caballos disponibles para la 2.ª posición son B1 y A2 y para la 3.ª posición son A3, B2 y C1. Todos los demás caballos no pueden estar entre los 3 primeros. Tengamos una carrera entre estos caballos y los 2 primeros serán el segundo y el tercer caballo más rápido respectivamente.
  

• Qué estructura de datos es la más adecuada para encontrar la mediana de un flujo continuo de números (algoritmo en línea)

  Heap
  La idea es usar max heap y min heap para almacenar los elementos de la mitad izquierda inferior a la mediana actual y la mitad derecha superior a la mediana actual, respectivamente. El número de elementos en los montones difiere como máximo en 1 elemento para cada entrada. Cuando ambos montones contienen la misma cantidad de elementos, elegimos el promedio como mediana, de lo contrario, seleccionamos la mediana del montón que contiene más elementos.
  Para obtener más detalles, consulte aquí .

• Hay N personas en un grupo, pueden o no conocerse los nombres.
  Hay una celebridad en el grupo, la celebridad no conoce a nadie y todas las personas conocen a la celebridad. Solo podemos hacer preguntas como «¿A conoce a B?». ( Problema de la celebridad )
  ¿Cuál es la complejidad temporal en el peor de los casos de la solución óptima para encontrar la celebridad?

  O(n)
  Digamos que preguntamos “¿A conoce a B?”. Si A conoce a B, A no puede ser una celebridad. Si A no conoce a B, entonces B no puede ser una celebridad. Entonces, después de cada pregunta, podemos rechazar a una persona. Por lo tanto, debemos hacer un máximo de n preguntas para descubrir correctamente a la celebridad.
  Para obtener más detalles, consulte aquí .

• Dadas 2 strings A y B, devuelve una string en la que los caracteres de A y B se completan alternativamente en el mismo orden que en las strings originales que comienzan con un carácter de A, ejemplo A = «Hola», B = «Adiós», entonces la salida debe ser “HBeyelelo”. (|A|,|B|<25000)

  Crea una nueva string vacía. Ejecute un bucle de tiempo min(|A|,|B|) y agregue el carácter iésimo de A y luego el carácter iésimo de B a la string de respuesta. Por último, agregue la parte restante de la string A o B a la string de respuesta.

• Dado un número N, encuentre el número de formas de escribir N como una suma de dos o más enteros consecutivos positivos, ya que si N es 7, por ejemplo, solo hay 1 forma, es decir, 3+4. (0<N<10^12)

  Supongamos que comenzamos nuestra serie de sumas desde 1, es decir, 1+2+3+…..
  Max no. de números cuya suma será menor o igual que N: piso(X)
  donde X*(X+1)/2=N
  Así que N como suma de enteros consecutivos positivos consistirá como máximo en X números.
  Aquí podemos comprobar cada posibilidad k(asumir) entre 2 y X (ambos inclusive) y para comprobar podemos utilizar el concepto de AP ya que la serie sumatoria es un AP cuya suma es N. Conocemos el no
  . de término en AP, n: k
  Suma de AP, S: N
  Diferencia común, d: 1
  Podemos calcular fácilmente el primer término a, usando la fórmula:

          S=n/2*(2a + (n-1)d)

  Si a es un número entero, entonces N se puede representar como una suma de k números enteros continuos; de lo contrario, no es posible. Cuente el número de ocurrencias cuando a es un número entero y esa es nuestra respuesta.
  Complejidad de tiempo: bucle de ejecución X tiempo que es O (sqrt (N)) y en cada iteración, tomamos O (1) tiempo. Entonces, la complejidad del tiempo general es O(sqrt(N)) .

PD: La prueba escrita también contenía preguntas relacionadas con ML y Quant .

Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo 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.