Recientemente tomé una prueba de HackerRank para un puesto de Data Science y me equivoqué con esta pregunta. Vine a 1/200
. Así es cómo:
Hay 50 combinaciones que lo harán realidad. (es decir, {1,2}, {2,4}, {3,6} ... {50,100}). La probabilidad de que se elija un número específico es 1/100
. La probabilidad de que se elija el conjunto específico es (1/100 * 1/100)
.
Como hay 50 juegos,
P=50*(1/100)*(1/100)=1/200
Por supuesto, supongo que se incluyen 1 y 100. Pero esta fue la respuesta incorrecta. ¿Alguien puede ayudarme a entender mi error?
probability
combinatorics
Jo Bennet
fuente
fuente
Respuestas:
Su primer error es que hay 50 resultados, en realidad hay 100 (Editar: vea el comentario a continuación para obtener una aclaración). Esto se debe a que obtener (1,2) y (2,1) son el resultado de dos resultados separados, pero en cada caso el número mayor es exactamente el doble del número menor.
Entonces, las formas totales posibles de obtener esto en realidad están dadas por el conjunto:
{(1,2), (2,1), (2,4), (4,2), ..., (50,100), (100,50)}
Que es una lista de 100 posibles resultados.
El número total de posibles resultados es100 × 99
Dado que hay 100 números posibles para elegir la primera vez, y luego 99 para la segunda, ya que deben ser distintos.
Por lo tanto, la respuesta viene dada por:
Usando el mismo argumento, es sencillo demostrar que la probabilidad para el caso más general de elegir números de1 , 2 , . . . , n dónde norte es un número par positivo dado por:
fuente
El "Hacker" en el nombre de la prueba sugiere que intentemos encontrar una solución orientada a la informática.
Comencemos por lo tanto con un programa para la enumeración por fuerza bruta de (a) los casos "favorables" en los que un número entero es dos veces el otro y (b) todos los casos posibles. La respuesta sería su relación. He codificado una solución general. Su entrada es un entero positivo
n
y su salida es la probabilidad.(La prueba de corrección se basa en el hecho de quei ≠ 2 i para cualquier número positivo yo .)
Este programa requiere3 pruebas y hasta 3 incrementos para cada iteración del bucle interno. Por lo tanto, necesita entre3 n y 6 n cálculos cada vez que se realiza el bucle interno, o 3norte2 a 6 6norte2 en general. Eso esO (norte2) rendimiento: OK para pequeños norte me gusta n = 100 pero terrible una vez norte excede 10000 más o menos.
Como hacker, una de las primeras cosas que querrá hacer es eliminar el rendimiento cuadrático simplificando el bucle interno (si es posible). Para este fin, revise sistemáticamente las líneas en el bucle interno (como numeradas) y observe lo siguiente:
La línea 1 se ejecuta todo menos una vez para cada valor den - 1 veces. En consecuencia, para el cálculo de
i
y, porall
lo tanto, se incrementaall
, el buclej
puede reemplazarse incrementandoall
porn-1
.La línea 2 se ejecuta exactamente una vez cuando2 i ≤ n y de lo contrario no del todo. Por lo tanto, se puede reemplazar incrementando 1 cuando 2 i ≤ n .
all
porLa línea 3 se ejecuta una vez que se proporciona
i
es par.Aquí está el programa transformado.
¿Podemos ir más allá y eliminar su ciclo?
La línea 1 'se ejecutanorte veces. Por
all
lo tanto, se incrementa enn*(n-1)
.La línea 2 'se ejecuta solo cuando2 i ≤ n . Una forma de contar esto es⌊ n / 2 ⌋ (el mayor entero menor o igual que n / 2 )
La línea 3 'se ejecuta solo para valores pares deyo . De nuevo, eso pasa⌊ n / 2 ⌋ veces.
La segunda transformación del programa es:
Esto ya es un logro tremendo: unO (norte2) algoritmo se ha reducido a un O ( 1 ) algoritmo (que puede considerarse una "fórmula cerrada" para la respuesta).
Finalmente, hay algunas transformaciones algebraicas simples que podemos hacer al pasar la inicialización (línea 0) al primer uso de cada variable y combinar las líneas 2 '' y 3 '':
En este punto, un humano podría ejecutar el programa. Hagámoslo conn = 100 :
La salida por lo tanto es1 / 99 .
Para resumir, un algoritmo de fuerza bruta puede transformarse sistemáticamente usando reglas simples de reescritura de programas en un diseño elegante, elegante,O ( 1 ) programa.
fuente
En primer lugar, está tomando muestras sin reemplazo. Por lo tanto, hay 100 * 99 resultados diferentes, por ejemplo (1,1) no es un resultado válido.
En segundo lugar, el orden no importa. El más grande debe ser exactamente dos veces, no el segundo. Por lo tanto, elimine los pares simétricos.
Por lo tanto, 50 de (100) * 99/2 son positivos, o 1/99
fuente