哈Ha！

有一次，在研究了另一本关于臭名昭著的数据科学的书后，我得出的结论是，该是时候将积累的知识付诸实践，并亲眼目睹分析部门的生活了。幸运的是，Yandex在适当的方向上展开了为期六个月的实习选择，但我不能错过。2020年申请的接受已经结束，因此在本文中，我将以明确的良心分析Yandex提议在第一阶段为申请人解决的任务。将有Python代码。剧透：困难，但有趣。

任务1.截止日期

任务

新手分析师正在尝试解决该问题。如果问题无法解决，那么他就会失去动力，并且下一次尝试成功的可能性就会下降。一次尝试需要一天，任务截止日期为90天。分析人员将通过第i次尝试解决问题的概率为：

$\frac{1}{(i+1)}$
$\frac{1}{(i+1)^2}$

分析人员在截止日期之前解决问题的可能性有多大？

决断

您可能已经输入以下内容：“ @ nice_one，您说过会很困难，但这是什么？” 耐心，朋友，这是一个很简单的热身任务，但是如果您不考虑这种情况，则可能会错过一些东西。让我们研究第一段的例子。必须计算出分析师在储备金中可用的90天之内解决问题的总概率，同时给出在第i天获得成功的概率。一个诱人的选项似乎在表达式中替代了一个从1到90的数字，而不是i并加了，但这是不正确的。该表达式表示在特定的i-day上成功的可能性，但是要达到该i-day，分析师必须在过去的（i-1）天失败。如果第i天成功的概率是

\frac{1}{(i + 1)}

$\frac{1}{(i+1)}$ ，那么这一天失败的概率等于

1 - \frac{1}{(i + 1)} = \frac{i}{i + 1}

$1 - \frac{1}{(i+1)} = \frac{i}{i+1}$ 。如您所知，要找到同时发生多个事件的概率，必须将每次发生的概率相乘。因此，分析师可以在n天之内应对的概率为

(\prod_{k = 1}^{n - 1} \frac{k}{k + 1}) \cdot \frac{1}{n + 1}

$\biggl(\prod\limits_{k=1}^{n-1}\frac{k}{k+1}\biggr)\cdot\frac{1}{n+1}$ 。

站在工作标志之下的成员应对第一次失败的原因负责

(n - 1)

$(n - 1)$ 天，则需要将乘积乘以第n天的成功概率。
因此，对于任何天数，我们都知道确切地在此期间内成功的概率。我们对长达90天（含90天）的每个可能期间的成功总概率感兴趣。现在您可以将数字替换为1到90，但是已经在结果公式中。最简单的方法是在某些python中编写一个循环，该循环将计算并添加概率，而我做到了。

编码

import 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)

第二段的决定与第一段完全相同，只是公式不同。我将离开代码来解决第二点-我认为一切都会变得清楚。

点2

import 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)

任务2.仓鼠的命运

任务

为了在冬天生存，贪婪的饥饿仓鼠决定抢劫距离其洞口1000米的坚果工厂。工厂剩下了3000个坚果。仓鼠的脸颊上最多放置1000个坚果。无论仓鼠如何携带，无论在哪里，他都需要用1个螺母加固每米。仓鼠已经在工厂里了，很危险。他最多可以储备多少种坚果？答案必须四舍五入到最接近的整数。

决断

强烈让人联想到吉普车的任务，是不是？就是这样，摆在我们面前的是下一个品种。在一般情况下，吉普车问题中出现了车辆（在这种情况下为仓鼠），在燃料容器（仓鼠的脸颊）容量有限的情况下，它需要行驶一定距离。解决此类问题的基本思路-途中，您可以离开燃料供应，也可以回来购买新的燃料。否则，由于初始条件和目标可能非常不同，因此不存在单一解决方案算法。这里提出的选择很有趣，因为不仅需要从工厂到孔的距离（这是基本的，因为仓鼠可以精确地容纳1000个螺母，足够1000米），而且还需要尽可能多地转移螺母。最好画一个图，描绘一个长1000 m的坚果和工厂里的坚果，然后想想如果仓鼠想将3000颗坚果运输到洞中，如何吃仓鼠，即尽可能少地吃东西，即已经越过总距离越少越好。让我们尝试以最小的步距移动，每个步距为1 m，并在几次行程中随身转移所有3000个螺母。

显然，为了将3000个螺母转移到任何位置，仓鼠将需要至少返回3次。当剩下2000个坚果并将其余坚果全部吃掉时，仓鼠将需要2个行程到上一个地点才能将它们移动到新的位置。当燃料不足1000单位时，您不必回头，它们就完全可以放在仓鼠的脸颊上了。因此，螺母的转移过程可以分为三个相应的阶段。让我们看看仓鼠每只将具有“燃料消耗”。当螺母超过2000个时，要移动1米，仓鼠必须：

收集完整的坚果面颊，然后步行1 m
卸下998个螺母（途中吃了1个，剩下的1个返回了）
再返回1 m到螺母座
对第二千个螺母重复步骤1-3
拿最后一千，向前走1 m

因此，在所有猎物的情况下，每位移1 m就要花费仓鼠5个螺母。当螺母变为<2000，并且在移动200 m后发生这种情况时，算法将如下所示：

收集完整的坚果面颊，然后步行1 m
卸下998个螺母（途中吃了1个，剩下的1个返回了）
再返回1 m到螺母座
拿最后一千，向前走1 m

1 m的位移需要仓鼠3个螺母。当他到达534 m的高度时，总共将吃掉2001年的坚果，仓鼠将不得不拿掉最后999个坚果，然后平静地将剩下的466米推入洞中。当他到达那里时，将在脸颊上残留533个坚果-这将是解决问题的方法。

我想指出的是，此类课程的任务在算法理论以及大型公司的访谈中都非常流行。学习如何解决这些问题的最好方法是练习。解决这个问题没有单一的机制（嗯，还是他游了我过去），但是很有可能会帮助他们并发展创新思维。

任务3：分析分布

任务

Yandex想要创造

M

$M$ 分析师团队。聘用时，每个分析师都会随机选择一个工作组。团队负责人想弄清楚哪几千名分析师足以聘请分析师，这样他的团队更有可能

P

$P$ 不少

N

$N$ 人？

您必须编写一个接受以下内容的Python程序

N

$N$ ，

M

$M$ 和

P

$P$ 只需一行，输出就可以提供成千上万的分析师。

1 \leq N \leq 100

$1 \leq N \leq 100$ ，

1 \leq M \leq 100000

$1 \leq M \leq 100000$ ，

0 \leq P \leq 1

$0 \leq P \leq 1$

决断

嗯，统计知识，即二项式分布，派上了用场。表示Yandex聘用的分析师人数

X

$X$ 。每个雇用的分析师都选择一个团队。从我们的团队负责人的角度来看，聘请分析师进行工作是一个有两个结果的实验：要么新来的人都不能加入我们的团队。命中几率等于

\frac{1}{M}

$\frac{1}{M}$ ，则分析师分别选择另一组的概率为

\frac{M - 1}{M}

$\frac{M-1}{M}$ 。总体而言，此类实验由团队选择

X

$X$ 。我们团队的命中数

n

$n$ 的

X

$X$ 分析师的选举按二项分布，分布函数等于：

P (n ⩽ N) = \sum_{k = 0}^{N} (\binom{X}{k}) (\frac{1}{M})^{k} (\frac{M - 1}{M})^{X - k}

$\mathbb{P}(n \leqslant N) = \sum\limits_{k=0}^{ N} \binom{X}{k}\, \biggl(\frac{1}{M}\biggr)^k \biggl(\frac{M-1}{M}\biggr)^{X-k}$

此函数显示命中次数小于或等于指定的概率

N

$N$ 。我们对命中数大于或等于给定命中数的可能性感兴趣，因此任务如下所示：

X : 1 - P_{x} (n ⩽ N) = P; X - ?

$X: 1 - \mathbb{P_x}(n \leqslant N) = P; X-?$

也就是说，您需要找到雇用的分析师人数

X

$X$ 团队至少获得

N

$N$ 给定概率的人

P

$P$ 。

好吧，我们弄清楚了数学-现在如何找到它

X

$X$ ？破坏您可以编写一个周期，该周期将对雇用的分析师数量进行分类，并增加该数量，直到获得至少

N

$N$ 分析师将不会满意。

编码

def 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)) #

任务4：礼物研究

任务

圣诞老人带来了Anastasia 100礼物，并将它们放在圣诞树下。这棵树又大又蓬松，所以阿纳斯塔西娅很难在它下面导航。阿纳斯塔西娅以这种方式检查礼物：意外地从树的随机侧面伸出到随机范围，拿出礼物，检查礼物并将其放回去。事实证明，每一次Anastasia都可以同样地从树下的那些人那里获得任何礼物。找到对Anastasia将考虑随机分配100次礼物的份额的期望吗？

决断

乍看之下，任务似乎非常简单，甚至似乎可以通过一些基本公式找到解决方案，但并不是所有事情都那么简单。没那么简单。我花了很多时间在此任务上，试图绘制选项并得出公式，但是我没有成功。然后我去了Google，令我惊讶的是，我不得不深入研究各个论坛，然后才找到针对一般情况的解决方案。因此，如果我们从具有收益的集合中随机选择元素，则概率为

n

$n$ 从中选择

m

$m$ 集合中的元素完全拉出

k

$k$ 不同等于

P (m, k, n) = \frac{(\binom{m}{k}) \cdot k! \cdot S_{2} (n, k)}{m^{n}}

$P(m, k, n) = \frac{\binom{m}{k}\cdot k! \cdot S_2(n, k)}{m^n}$

哪里

S_{2}

$S_2$ 第二种是斯特林数 -集合中无序分区的数量

n

$n$ 上的项目

k

$k$ 非空子集。好吧，为了找到期望，有必要将通过此公式计算出的概率，用于检查的独特礼物的每个可能部分-从百分之一到整体。可以使用Python中的循环来完成。

编码

import math
import numpy as np
import sys
import sympy #     -   

sys.setrecursionlimit(10**9)

def c(n, k): # C

    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): #    k

    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)
#...    100
frac = np.array([i for i in range(1, 101)]) / 100


print(sum(pr*frac)) #

任务5：等价旅行者

任务

旅行者开始沿着二维网格的边缘移动，整个节点严格向右或向上移动。他从一个角度出发

(0, 0)

$(0, 0)$ 究竟

(100, 100)

$(100, 100)$ 。如果我们假设所有可能的路线都具有相同的可能性，那么在连接起点和终点的直线上越过河流的可能性有多大？可以认为，如果旅行者严格按照同一条路线在河的上方和下方，则他会穿过河。河流入口不视为交叉路口。

决断

我们找到了穿越经典方法的可能性-我们将相交的路线数除以可能的路线总数。让

n

$n$ -方格边缘的长度。然后是可能的路线总数：

N = \frac{(2 n!)}{(n!)^{2}}

$N = \frac{(2n!)}{(n!)^2}$

式的推导进行说明这里。但是如何找出每条河流的过河路线数量

n

$n$ ？对此问题感到困惑后，我决定采用一些较小的网格长度，绘制字段并手动计算过河的路线，以期找到依赖关系（我强烈建议您现在也拿一张纸和一支笔并尝试绘制小网格和路径）。

假设有一个大小为3 x 3的网格。网格的对角线被河流占据，旅行者在左下角。

图片

这幅画不是很完美，但是我诚实地尝试过

绘制完图纸后，我立即意识到，追踪河流未穿越的路线（即河流下方的路线）会容易得多。然后可以将它们的数量乘以2，从而考虑到河流上方的镜像路径。由于我们还知道路线的总数，因此我们可以找到过河的人数。但是回到主要任务-我们需要

n

$n$ 以及河流通道的数量。

在上面的3x3情况下，我用蓝色标记了旅行者可以访问的一些“陆地”路线：标记的路线沿着水平坐标为2的单元格边缘通过，旅行者之前没有进入单元格的左边缘和上边缘。有3条这样的路线，即

n

$n$ 。现在，让我们找出通过第1列中单元格的路线。

图片

我用红色标记了新路径。因此，很明显，如果旅行者向左转，然后转到单元格的上边缘（1，0），那么通过单元格水平坐标为2的三个路径中只有2条路径可供他访问，因为您只能向上和向右移动-第三条路径位于较低位置。因此，将第1列的新单元格添加到路由中，我们增加了路径总数，即通过列2的单元格但不低于我们新单元格的路由数。

取4 x 4格并继续解开缠结。很明显，将新的单元格添加到列中会增加通过下一列的路由数量，且路径数量不低于添加的单元格的顶部边缘。我不会用颜色标记路线，而是将其限制在文字说明中，但是如果您认为有必要，请画图-在解决过程中，我画出了十二个不同的网格，然后才能自信地感到依赖。

图片

最右边的列再次给我们

n

$n$ 路线。单元格的顶部边缘（2，0）将为我们添加

n - 1

$n-1$ 路线。单元格的顶部边缘（2，1）将添加

n - 2

$n-2$ 路线。单元格（1，0）的顶部边缘将添加与单元格（2，0）和（2，1）加在一起的路线一样多的路线。如果愿意，可以绘制更大的网格，并继续使用相同的算法来考虑路线。我们的任务是为100x100的网格计算路线。为此，您可以编写一个接受输入的程序

n

$n$ 并建立一个矩阵

n \times n

$n\times n$ 从专栏开始

n

$n$ 然后针对前几列的每个单元格，根据前一列的数据计算该单元格添加的路径数。因此，将找到非河流穿越路径的数量。

编码

import 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 #    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]
    
    #      2,     
    return (2 * sum(sum(net))) 

#      -    1
print(1  - fill_matrix(100) / routes_total(100))

任务6.线性分布状态

任务

线性分布状态是众多城市，其中一些城市通过公路相连。

一旦国家国王知道断点人民即将入侵其边界。由于国家尚未做好防卫准备，国王做出了一个艰难的决定-将国家分为许多小国，每个小国将独立捍卫其边界。

决定即使可能的人在线性分配州的任何两个城市之间占领一条道路，也可以并且应该将两个城市从一个城市移到第二个城市。在所有其他情况下，城市必须处于不同的州。

在将跨越任何两个新州边界的每条道路上，都必须设一个堡垒。如果断点人员捕获了这些状态之一，则这是必要的。然后第二个将能够继续捍卫其边界。换句话说，堡垒将被放置在连接来自不同州的城市的道路上。

国王要您给他列出您需要放下堡垒的道路清单。

程序输入输出格式

输入格式

n

$n$

m

$m$ — .

(1 \leq n \leq 20000, 1 \leq m \leq 200000)

$(1 \leq n \leq 20000, 1 \leq m \leq 200000)$ . m . i

b_{i}, e_{i}

$b_i, e_i$ — ,

(1 \leq b_{i}, e_{i} \leq n)

$(1 \leq b_i, e_i \leq n)$

b — , . b — , , . , .

, , , , — .

决断

这是图论的问题。对于有关线性分布状态的命运的长篇报道，起草者掩盖了在图形中查找节点为城市而边缘为道路的桥梁这一相当有趣的任务。简而言之，桥就是图的这种边缘，将其删除将使该图的某些部分与其他顶点断开。这就是捕获道路的想法-如果桥梁被占领，一些城市之间的通信将中断，否则城市之间将始终存在替代道路，因此这是国家划分的桥梁，有必要在这些桥梁上放置堡垒。

基于深度搜索的桥梁搜索算法（深度优先搜索，DFS）-一种图形遍历方法，其中检查所有来自初始顶点的边，如果该边导致尚未考虑的顶点，则算法立即从该顶点递归开始。以下事实将有助于搜索桥梁：

让我们进行深度搜索，现在查找顶点V的所有边。然后，如果当前边（V，U）如此，使得从顶点U以及遍历树中的任何后代开始，到V或其任何祖先的峰值的路径，所考虑的边是桥。

为了学习如何验证顶点V的这一事实，我们介绍了进入顶点圆盘[V]的时间（从英语中发现）。在此变量中，将记录已处理顶点的算法步骤。此外，与每个顶点V，该最低[V]变量将被相关联，在其中我们写最早顶点U，可从顶点V.到达在顶点的初始处理的发生时最低[V] =圆盘[V] （对顶点早于自己），但在后来的深入搜索过程中，我们可以找到一个儿子V，其边缘之一指向V的祖先（我们称他为S）。在这种情况下，我们将更新最低[V]：最低[V] =光盘[S]。我们什么时候可以搭桥？然后，当我们进行深入搜索时，我们到达了顶部，该顶部没有尚未考虑的儿子（再次，我们称其为U）。在这种情况下，我们将检查从U可以到达哪个最早的顶点，以及该最早的顶点是否晚于U的直接父节点（例如，当U没有儿子时，则最低[U] =盘[U] ]），那么U与父级的连接是一个桥梁。

下面附有带注释的已实现算法的代码。不为磁盘和每个顶点的最低点创建单独的变量，而是为每个值放置数组是很方便的，其中索引是该值所属的顶点的编号。

编码

import 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) #  discovered
lowest = disc.copy() #  lowest
used = disc.copy() #  used. ,    
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]) # ,       ;  lowest 
        else: #   
            dfs(u, v) #      
            #           cc  U:
            lowest[v] = min(lowest[v], lowest[u])  
            if lowest[u] > disc[v]: #   u    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)

以下消息源以多种方式帮助我解决了该问题，因此我认为有必要与其保持联系。值得观看，这是视频，其中有很好的算法动画。

结论

这些是申请Yandex实习生的专家应自信解决的任务。我认为上述任务分配了5个小时的时间-在我看来是很短的时间，但是每个人都按照自己的节奏工作。

我的决定已经过测试，并且给出了正确的答案，但是，毫无疑问，有更有效的方式来应对建议的任务。如果您准备提供更快或更容易理解的解决方案，或者发现我的错误，请随时写信。

我希望每个人都能找到自己的位置！

Yandex中的分析师实习：测试任务分析