Hola Habr!Una vez, después de estudiar otro libro sobre la notoria ciencia de datos, llegué a la conclusión de que sería hora de poner en práctica el conocimiento acumulado y ver la vida del departamento de análisis con mis propios ojos. Afortunadamente, Yandex lanzó una selección para una pasantía de seis meses en la dirección adecuada, y no pude pasar. La aceptación de las solicitudes 2020 ya ha finalizado, por lo que en este artículo analizaré, con la conciencia tranquila, las tareas que Yandex propuso resolver para los solicitantes en la primera etapa. Habrá código de Python. Spoiler: difícil, pero interesante.Tarea 1. Plazo
La tarea
El analista novato está tratando de resolver el problema. Si no se puede resolver el problema, pierde la motivación y disminuye la probabilidad de éxito en el próximo intento. Un intento lleva un día, y el plazo de la tarea es de 90 días. La probabilidad de que el analista resuelva el problema desde el i-ésimo intento es:
¿Qué posibilidades hay de que el analista resuelva el problema antes de la fecha límite?Decisión
Es posible que ya haya llegado a escribir: "@nice_one, usted dijo que sería difícil, pero ¿qué es esto?" Paciencia, amigos, esta es una tarea simple para calentar, pero hay algo que se debe perder si no piensan en la afección. Examinemos el ejemplo del primer párrafo. Es necesario calcular la probabilidad total de que el analista resuelva el problema en cualquiera de los 90 días disponibles en la reserva, mientras se da la probabilidad de éxito en cada i-ésimo día. Puede parecer que una opción tentadora sustituye en la expresión un número del 1 al 90 en lugar de iy suma, pero esto no es cierto. Esta expresión indica la probabilidad de éxito en un día particular, pero para llegar a ese día, el analista debe fallar en el pasado (i - 1) días. Si la probabilidad de éxito en el i-ésimo día es, entonces la probabilidad de falla en este día es por lo tanto igual a . Como sabe, para encontrar la probabilidad de la ocurrencia simultánea de varios eventos, es necesario multiplicar la probabilidad de cada ocurrencia. Por lo tanto, la probabilidad de que el analista pueda hacer frente en exactamente n días es.Los miembros que se encuentren bajo el signo del trabajo son responsables del fracaso en cada uno de los primerosdías, entonces necesita multiplicar el producto por la probabilidad de éxito en el enésimo día.Entonces, para cualquier número de días, sabemos la probabilidad de éxito para exactamente este período. Estamos interesados en la probabilidad total de éxito para cada período posible de hasta 90 días inclusive. Ahora puede sustituir números del 1 al 90, pero ya en la fórmula resultante. La forma más fácil es escribir un bucle en alguna pitón que calcule y agregue probabilidades, lo cual hice.El códigoimport numpy as np
n = 90
probs = []
for i in range(1, n+1):
prob_now = 1/(i+1)
prob_not_before = []
for k in range(1, i):
prob_not_before.append(k/(k+1))
prob_not_before = np.array(prob_not_before).prod()
probs.append(prob_not_before * prob_now)
s = sum(probs)
print(s)
La decisión del segundo párrafo es completamente similar a la primera, solo la fórmula difiere. Dejaré el código resolviendo el segundo punto: creo que todo estará claro.Punto 2import numpy as np
n = 90
probs = []
for i in range(1, n+1):
prob_now = 1/((i+1)**2)
prob_not_before = []
for k in range(1, i):
prob_not_before.append(1 - (1/((k+1)**2)))
prob_not_before = np.array(prob_not_before).prod()
probs.append(prob_not_before * prob_now)
s = sum(probs)
print(s)
Tarea 2. El destino del hámster
La tarea
Para sobrevivir en invierno, el hámster hambriento y codicioso decidió robar una fábrica de nueces ubicada a 1000 metros de su hoyo. Quedaban 3.000 nueces en la fábrica. Se colocan un máximo de 1000 nueces en las mejillas del hámster. En todas partes y sin importar con qué vaya el hámster, cada metro necesita ser reforzado con 1 tuerca. El hámster ya está en la fábrica y es peligroso. ¿Cuál es el número máximo de nueces que puede almacenar? La respuesta debe redondearse al entero más cercano.Decisión
Recuerda mucho la tarea de un jeep, ¿no es? Así es, ante nosotros está su próxima variedad. En el caso general, un vehículo (en este caso, un hámster) aparece en el problema del jeep, que necesita recorrer una cierta distancia en condiciones de capacidad limitada del contenedor de combustible (mejillas del hámster). La idea subyacente a la solución a cualquier problema de esta clase: en el camino, puede dejar los suministros de combustible, así como regresar por uno nuevo. De lo contrario, no existe un algoritmo de solución única, ya que las condiciones y objetivos iniciales pueden ser muy diferentes. La opción propuesta aquí es interesante porque es necesario no solo recorrer la distancia desde la fábrica hasta el hoyo (lo cual es elemental, porque el hámster puede contener exactamente 1000 nueces, que es suficiente para 1000 metros), sino transferirle la mayor cantidad posible de nueces. Es mejor dibujar un diagrama,representando una longitud de 1000 my un stock de nueces en la fábrica, y piense en cómo actuar el hámster si quiere transportar 3000 nueces en el hoyo, comiendo lo menos posible, es decir, pasando la menor distancia posible. Intentemos movernos en los pasos más pequeños, 1 m cada uno, transfiriendo las 3000 nueces con usted en varios viajes.Obviamente, para transferir 3000 nueces en algún momento, el hámster deberá volver a la anterior al menos 3 veces. Cuando quedan 2000 nueces y el resto se come en el camino, el hámster necesitará 2 viajes al punto anterior para moverlos a uno nuevo. Cuando el combustible es inferior a 1000 unidades, no tiene que regresar, todo cabe en las mejillas del hámster. Por lo tanto, el proceso de transferencia de frutos secos se puede dividir en tres etapas correspondientes. Veamos qué tendrá el "consumo de combustible" en cada uno. Cuando hay más de 2,000 nueces, para mover 1 metro, el hámster tendrá que:- Recoge las mejillas llenas de nueces y camina 1 m
- Descarga 998 nueces (1 comió en el camino, 1 dejó para volver)
- Regrese 1 m nuevamente al caldo de nueces
- Repita los pasos 1-3 para el segundo mil nueces
- Toma los últimos mil y ve con ellos 1 m adelante
Por lo tanto, el desplazamiento de 1 m con todas las presas le cuesta al hámster 5 nueces. Cuando las nueces se vuelven <2000, y esto sucede después de 200 m de movimiento, el algoritmo será el siguiente:- Recoge las mejillas llenas de nueces y camina 1 m
- Descarga 998 nueces (1 comió en el camino, 1 dejó para volver)
- Regrese 1 m nuevamente al caldo de nueces
- Toma los últimos mil y ve con ellos 1 m adelante
El desplazamiento de 1 m le cuesta al hámster 3 nueces. Cuando alcance el punto de 534 m, se comerá un total de 2001 nueces, y el hámster tendrá que tomar las últimas 999 nueces y pasar tranquilamente los 466 metros restantes en su hoyo. Cuando llegue allí, 533 nueces permanecerán en las mejillas, esta será la respuesta al problema.Quiero señalar que las tareas de esta clase son bastante populares en la teoría de algoritmos, así como en entrevistas en grandes empresas. La mejor manera de aprender a resolverlos es practicando. No existe un mecanismo único para resolverlo (bueno, o él pasó a mi lado), pero es muy posible echarles una mano y desarrollar un pensamiento creativo.Tarea 3. Distribución analítica
La tarea
Yandex quiere crear equipos de analistas. Al contratar, cada analista elige al azar un grupo para sí mismo donde trabajará. El líder del equipo quiere determinar qué cantidad mínima de miles de analistas es suficiente para contratar para que su grupo sea más probable no fue menos ¿persona?Debes escribir un programa Python que acepte, y en una línea, y la salida da el número de miles de analistas., , Decisión
Bueno, el conocimiento de las estadísticas, es decir, la distribución binomial , fue útil . Denotamos el número de analistas contratados por Yandex para. Cada uno de los analistas contratados elige un equipo. Desde el punto de vista del líder de nuestro equipo, contratar a un analista para el trabajo es un experimento con dos resultados: un recién llegado cae en nuestro equipo o no. La probabilidad de golpe es igual, la probabilidad de que el analista elija otro grupo, respectivamente, es . En total, tales experimentos con la elección del equipo serán. El número de visitas en nuestro equipo. de la elección de analistas se distribuye binomialmente, la función de distribución es igual a:
Esta función muestra la probabilidad de que el número de visitas sea menor o igual al especificado . Estamos interesados en la probabilidad de que el número de visitas sea mayor o igual que el dado, por lo que la tarea se ve así:
Es decir, necesita encontrar el número de analistas contratados. en el que el equipo obtiene al menos persona para una probabilidad dada .Bueno, descubrimos las matemáticas: cómo encontrarlas ahora? Revienta Puede escribir un ciclo que clasifique el número de analistas contratados, incrementándolo hasta la probabilidad de obtener al menos Los analistas no serán satisfactorios.El códigodef c(n, k):
if 0 <= k <= n:
nn = 1
kk = 1
for t in range(1, min(k, n - k) + 1):
nn *= n
kk *= t
n -= 1
return nn // kk
else:
return 0
def bin_prob(trials, k, m):
return c(trials, k) * ((1/m)**k) * ((1 - 1/m)**(trials - k))
def cdf(maximum, trials, m):
value = 0
for i in range(maximum + 1):
value += bin_prob(trials, i, m)
return value
n, m, p = [(float(i)) for i in input().split()]
n = int(n)
m = int(m)
x = 1000
while (1 - cdf(n, x, m)) < p:
x += 1000
print(int(x / 1000))
Tarea 4. Investigación de regalos
La tarea
Papá Noel trajo a Anastasia 100 regalos y los colocó debajo del árbol de Navidad. El árbol es grande y esponjoso, por lo que es difícil navegar por Anastasia. Anastasia examina los regalos de esta manera: accidentalmente se extiende desde el lado aleatorio del árbol a un rango aleatorio, toma un regalo, lo examina y lo devuelve. Resulta que cada vez que Anastasia puede tomar cualquier regalo de quienes yacen debajo del árbol. ¿Encuentra la expectativa de la cantidad de regalos que Anastasia considerará para 100 tramos al azar?Decisión
A primera vista, la tarea parece muy simple, incluso la confianza parece ser que una fórmula elemental puede encontrar una solución, pero no todo es tan simple. No es tan simple. Pasé mucho tiempo indecente en esta tarea, tratando de pintar opciones y derivar una fórmula, pero no tuve éxito. Luego fui a Google y, para mi sorpresa, tuve que profundizar en los foros, antes de encontrar una solución para el caso general . Entonces, si seleccionamos al azar elementos de un conjunto con un retorno, la probabilidad es selecciones de elementos del conjunto sacan exactamente diferentes iguales:
Dónde hay un número de Stirling del segundo tipo : el número de particiones desordenadas del conjunto de artículos en subconjuntos no vacíos. Bueno, para encontrar la expectativa, es necesario sumar las probabilidades calculadas por esta fórmula para cada posible fracción de los regalos únicos examinados, de una centésima a un todo. Esto se puede hacer usando un bucle en Python.El códigoimport math
import numpy as np
import sys
import sympy
sys.setrecursionlimit(10**9)
def c(n, k):
return (math.factorial(n))/(math.factorial(k) * math.factorial(n-k))
def s(n, k):
return sympy.functions.combinatorial.numbers.stirling(n, k)
def p(m, k, n):
return c(m, k) * math.factorial(k) * s(n, k) / (m**n)
pr = []
for j in range(1, 101):
pr.append(p(100, j, 100))
pr = np.array(pr)
frac = np.array([i for i in range(1, 101)]) / 100
print(sum(pr*frac))
Tarea 5. Viajero equiprobable
La tarea
El viajero comienza a moverse a lo largo de los bordes de una cuadrícula bidimensional con nodos enteros estrictamente a la derecha o hacia arriba. Se mueve desde un punto exactamente . ¿Qué tan probable es cruzar un río en línea recta que conecta los puntos de inicio y final, si suponemos que todas las rutas posibles son igualmente probables? Se cree que el viajero cruzó el río si estaba en la misma ruta estrictamente por encima y por debajo del río. Una entrada de río no se considera una intersección.Decisión
Encontramos la probabilidad de cruzar el enfoque clásico: dividimos el número de rutas con intersección por el número total de rutas posibles. Permitir- la longitud de los bordes de la cuadrícula cuadrada. Luego el número total de rutas posibles:
La derivación de la fórmula se describe aquí . Pero cómo averiguar el número de rutas de cruce de ríos para cada? Después de haber quedado perplejo por esta pregunta, decidí tomar algunas cuadrículas más pequeñas, dibujar campos y calcular manualmente cuántas rutas cruzan el río, con la esperanza de rastrear la dependencia (le recomiendo que también tome un pedazo de papel y un bolígrafo ahora y experimente dibujando pequeñas cuadrículas y caminos).Que haya una cuadrícula de tamaño 3 por 3 celdas. La diagonal lateral de la cuadrícula está ocupada por el río, el viajero está en la esquina inferior izquierda.ImagenEl dibujo no es perfecto, pero lo intenté, sinceramente
Tan pronto como hice el dibujo, me di cuenta de que sería mucho más fácil rastrear las rutas que el río no cruza, es decir, las rutas debajo del río. Entonces será posible multiplicar su número por 2, teniendo en cuenta los caminos espejo sobre el río. Como también sabemos la cantidad total de rutas, encontramos la cantidad de personas que cruzan el río. Pero volviendo a la tarea principal: necesitamos una relación entrey el número de caminos de cruce de ríos.En la figura anterior para el caso de 3x3, marqué en azul algunas rutas "terrestres" accesibles para el viajero: las rutas marcadas pasan a lo largo de los bordes de las celdas con una coordenada horizontal de 2, el viajero no ingresa antes en los bordes izquierdo y superior de las celdas. Hay 3 rutas de este tipo, es decir. Ahora veamos las rutas que pasan por la celda en la columna 1.Marqué los nuevos caminos en rojo. Por lo tanto, está claro que si un viajero gira a la izquierda y luego al borde superior de la celda (1, 0), entonces solo 2 de los tres caminos a través de las celdas con una coordenada horizontal de 2 serán accesibles para él, porque solo puede moverse hacia arriba y hacia la derecha: el tercer camino se encuentra más abajo . Por lo tanto, al agregar una nueva celda de la columna 1 a la ruta, aumentamos el número total de rutas por el número de rutas que pasan a través de las celdas de la columna 2 que no son más bajas que nuestra nueva celda.Tome una cuadrícula de 4 por 4 y continúe desenredando el enredo. Quedó claro que agregar una nueva celda a una columna aumenta la cantidad de rutas en la cantidad de rutas que pasan a través de la siguiente columna no más abajo que el borde superior de la celda agregada.. No marcaré las rutas con color, me limitaré a una descripción textual, pero si lo considera necesario, dibuje; en el proceso de resolución, dibujé una docena de cuadrículas diferentes antes de lograr sentir con confianza la dependencia.La columna de la derecha nuevamente nos da rutas. El borde superior de la celda (2, 0) nos agregaráruta. El borde superior de la celda (2, 1) agregaráruta. El borde superior de la celda (1, 0) agregará tantas rutas como las celdas (2, 0) y (2, 1) hayan agregado juntas. Si lo desea, puede dibujar una cuadrícula más grande y continuar considerando las rutas con el mismo algoritmo. Nuestra tarea es calcular las rutas para una cuadrícula de 100x100. Para hacer esto, puede escribir un programa que acepte la entrada y construir una matriz a partir de la columna y luego para cada celda de las columnas anteriores, contar el número de rutas agregadas por la celda en función de los datos de la columna anterior. Por lo tanto, se encontrará el número de caminos que no cruzan el río.El códigoimport numpy as np
import math
def routes_total(n):
return math.factorial(2*n) / (math.factorial(n)**2)
def fill_matrix(n):
net = np.zeros((n, n))
net[0, 0] = n
for i in range(n-2):
net[1, i] = n - i - 1
for i in range(2, n):
for j in range(n - i - 1):
net[i, j] = 0
for g in range(j, n - i + 1):
net[i, j] += net[i - 1, g]
return (2 * sum(sum(net)))
print(1 - fill_matrix(100) / routes_total(100))
Tarea 6. Estado de distribución lineal
La tarea
El estado de distribución lineal es una multitud de ciudades, algunas de las cuales están conectadas por carreteras.Una vez que el Rey del Estado se dio cuenta de que la Gente de los Puntos de Interrupción estaba a punto de invadir sus fronteras. Como el Estado no estaba listo para la defensa, el rey tomó una decisión difícil: dividir el Estado en muchos pequeños, cada uno de los cuales defenderá sus fronteras de manera independiente.Se decidió que dos ciudades pueden y deben dejarse en un estado si es posible llegar a la segunda desde una ciudad, incluso si la Gente de los puntos de interrupción toma una carretera entre dos ciudades del Estado de distribución lineal. En todos los demás casos, las ciudades deben estar en diferentes estados.En cada camino que cruzará la frontera de dos estados nuevos, es necesario poner un bastión. Esto es necesario en caso de que uno de estos estados sea capturado por People of Breakpoints. Entonces el segundo podrá continuar defendiendo sus fronteras. En otras palabras, el bastión se pondrá en el camino que conecta ciudades de diferentes estados.El rey te pidió que le dieras una lista de caminos en los que necesitas poner bastiones.Formato de entrada y salida del programaFormato de entrada
— . . m . i — ,
b — , . b — , , . , .
, , , , — .
Decisión
Y aquí está el problema de la teoría de grafos. Para largas historias sobre el destino del Estado de distribución lineal, los redactores ocultaron la tarea bastante interesante de encontrar puentes en un gráfico cuyos nodos son ciudades y los bordes son carreteras. Brevemente, un puente es el borde de un gráfico, cuya eliminación cortará una cierta parte de este gráfico de otros vértices. Esta es la idea de capturar el camino: si se captura el puente, la comunicación entre algunas ciudades se interrumpirá, de lo contrario siempre habrá un camino alternativo entre las ciudades, por lo tanto, son los puentes que los estados dividen, es necesario poner bastiones en los puentes.Algoritmo de búsqueda de puente basado en la búsqueda de profundidad(Búsqueda de profundidad primero, DFS): un método de recorrido de gráfico en el que se examinan todos los bordes que provienen del vértice inicial, y si el borde conduce a un vértice que aún no se ha considerado, el algoritmo comienza inmediatamente de forma recursiva desde este vértice. El siguiente hecho ayudará en la búsqueda de puentes:Supongamos que estamos mirando en profundidad, mirando ahora todos los bordes desde el vértice V. Entonces, si el borde actual (V, U) es tal que desde el vértice U y de cualquiera de sus descendientes en el árbol transversal, no hay inverso camino al pico de V o cualquiera de sus antepasados, el borde considerado es un puente.Para aprender a verificar este hecho para el vértice V, introducimos el tiempo de entrada en el disco del vértice [V](del inglés. descubierto). En esta variable, se registrará el paso del algoritmo en el que se ha procesado el vértice. Además, con cada vértice V, se asociará la variable más baja [V] , en la cual escribimos el tiempo de ocurrencia del vértice más antiguo U, que se puede alcanzar desde el vértice V. Durante el procesamiento inicial del vértice más bajo [V] = disco [V] (al vértice anterior a no te entiendes), pero más adelante en el proceso de búsqueda en profundidad podemos encontrar a un hijo V, uno de cuyos bordes conduce al antepasado de V (vamos a llamarlo S). En este caso, actualizaremos el más bajo [V]: el más bajo [V] = disco [S]. ¿Y cuándo podemos enganchar el puente? Luego, cuando buscamos en profundidad, llegamos a la cima, que no tiene hijos que aún no se hayan considerado (Nuevamente, lo llamamos U). En este caso, comprobaremos qué vértice más temprano se puede alcanzar desde U, y si este vértice más temprano ocurre más tarde que el padre inmediato de U (Esto es posible, por ejemplo, cuando U no tiene hijos, entonces el más bajo [U] = disco [U ] ), entonces la conexión de U con el padre es un puente.El código del algoritmo implementado con comentarios se adjunta a continuación. Es conveniente no crear variables separadas para el disco y la más baja de cada vértice, sino colocar matrices para cada valor, donde el índice es el número del vértice al que pertenece el valor.El códigoimport sys
from collections import Counter
import numpy as np
sys.setrecursionlimit(10**6)
n, m = [int(i) for i in input().split()]
roads = [None]
graph = {}
for i in range(1, n+1):
graph[i] = []
for i in range(1, m+1):
twns = [int(j) for j in input().split()]
graph[twns[0]].append(twns[1])
graph[twns[1]].append(twns[0])
roads.append(frozenset([j for j in twns]))
disc = [0] * (n+1)
lowest = disc.copy()
used = disc.copy()
c = Counter(roads)
timer = 0
nbridges = 0
bridges = []
def dfs(v, parent):
global timer
global nbridges
global bridges
timer += 1
disc[v] = timer
lowest[v] = timer
used[v] = True
for u in graph[v]:
if u == parent:
continue
if used[u]:
lowest[v] = min(lowest[v], disc[u])
else:
dfs(u, v)
lowest[v] = min(lowest[v], lowest[u])
if lowest[u] > disc[v]:
twns = []
twns.append(u)
twns.append(v)
if c[frozenset(twns)] > 1:
continue
nbridges += 1
bridges.append(roads.index(set(twns)))
dfs(1, 0)
print(nbridges)
bridges = np.sort(bridges)
for bridge in bridges:
print(bridge)
La siguiente fuente me ayudó a tratar el problema de muchas maneras , por lo que considero que es necesario dejar un enlace. Vale la pena verlo y aquí está este video : hay una buena animación del algoritmo.Conclusión
Estas son las tareas que un especialista que solicita una pasantía en Yandex debe resolver con confianza. El conjunto de tareas anterior recibió 5 horas, en mi opinión, un tiempo bastante corto, pero todos trabajan a su propio ritmo.Mis decisiones han sido probadas y dan las respuestas correctas, sin embargo, no tengo dudas de que hay formas más efectivas de hacer frente a las tareas propuestas. Si está listo para ofrecer una solución más rápida o más comprensible o si encuentra un error conmigo, no dude en escribir al respecto.¡Deseo que todos encuentren un puesto por sí mismos!