Get best of the week

Yandexのアナリストインターンシップ：テストタスクの分析



こんにちは、ハブル！

悪名高いデータサイエンスに関する別の本を研究していたときに、蓄積された知識を実践し、分析部門の人生を自分の目で見るときが来るという結論に達しました。幸い、Yandexは適切な方向で6か月のインターンシップの選考を開始しました。2020年の申請の受け入れはすでに終了しているため、この記事では、明確な良心をもって、Yandexが最初の段階で申請者のために解決することを提案したタスクを分析します。Pythonコードがあります。スポイラー：難しいが興味深い。

タスク1.期限


タスク


初心者アナリストが問題を解決しようとしています。問題が解決できなかった場合、彼はやる気を失い、次の試みが成功する確率が下がります。1回の試行には1日かかり、タスクの期限は90日です。アナリストがi番目の試行から問題を解決する確率は次のとおりです。

  1. 1(i+1)
  2. 1(i+1)2

アナリストは締め切り前に問題を解決する可能性がどのくらいありますか？

決定


「@nice_one、難しいと言っていましたが、これは何ですか？」忍耐、友人、これはウォームアップするのは簡単な仕事ですが、あなたが状態について考えないと、見逃してしまうことがあります。最初の段落の例を見てみましょう。各i日目の成功確率が与えられている間、アナリストが予備で利用可能な90日間のいずれかで問題を解決する総確率を計算する必要があります。魅力的なオプションは、式の中で、iとaddの代わりに1から90までの数を代入するように見えるかもしれませんが、これは真実ではありません。この式は、特定のi-dayで成功する可能性を示しますが、そのi-dayに到達するには、アナリストは過去（i-1）日間失敗する必要があります。i日目の成功確率が1(i+1)の場合、この日の失敗の確率は次のようになります。 1−1(i+1)=ii+1。ご存知のように、複数のイベントが同時に発生する確率を見つけるには、各発生の確率を掛ける必要があります。したがって、アナリストが正確にn日で対処できる確率は(∏k=1n−1kk+1)⋅1n+1。

作業のサインの下に立っているメンバーは、最初のそれぞれの失敗の責任があります(n−1)日後、製品にn日目の成功確率を掛ける必要があります。
したがって、日数を問わず、この期間が成功する確率がわかります。私たちは、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番目の段落の決定は最初の段落と完全に似ており、式のみが異なります。私は2番目のポイントを解決するコードを残します-私はすべてが明確になると思います。

ポイント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メートルにあるナッツ工場を奪うことにしました。工場には3,000個のナッツが残っていました。ハムスターの頬には最大1000個のナッツが置かれます。どこにいても、ハムスターがどんなものであろうと、彼はすべてのメーターを1つのナットで補強する必要があります。ハムスターはすでに工場にあり危険です。彼がストックできるナッツの最大数はいくつですか？答えは最も近い整数に丸める必要があります。

決定


ジープの仕事を 強く連想させる、 ではない？つまり、私たちの前に次の品種があります。一般的なケースでは、車両（この場合はハムスター）がジープの問題に現れ、燃料コンテナ（ハムスターの頬）の容量が限られている状況で特定の距離を走行する必要があります。このクラスの問題の解決策の根底にあるアイデア-途中で、燃料供給を残したり、新しい燃料供給に戻ったりすることができます。それ以外の場合、初期条件と目標は非常に異なる可能性があるため、単一のソリューションアルゴリズムは存在しません。ここで提案されているオプションは、工場から穴までの距離を移動する必要があるだけでなく（ハムスターは正確に1000ナットを保持できる1000メートルに十分であるため、初歩的です）、できるだけ多くのナットをそこに移動する必要があるため、興味深いものです。図を描くのが最善です1000 mの長さと工場でのナッツのストックを描写し、ハムスターが穴に3000ナッツを輸送したい場合、ハムスターをどのように動かして、食べる量をできるだけ少なくするか、つまり総距離をできるだけ少なくするかを考えます。それぞれ1 mの最小ステップで移動し、数回のトリップで3000個のナットをすべて移動してみましょう。

明らかに、3000個のナッツをどこかに移すためには、ハムスターは少なくとも3回前のものに戻る必要があります。2000個のナッツが残り、残りが途中で食べられると、ハムスターを新しいものに移動するには、前のポイントまで2回の移動が必要になります。燃料が1000ユニット未満の場合は、戻る必要はありません。燃料はすべてハムスターの頬に収まります。したがって、ナットを移動するプロセスは、3つの対応する段階に分けることができます。ハムスターがそれぞれに「燃料消費」を持つものを見てみましょう。ナッツが2,000個以上ある場合、1メートル移動するには、ハムスターは次のことを行う必要があります。

  1. 木の実のほっぺを集めて1 m歩く
  2. 998個のナッツを降ろします（途中で1個、残り1個は戻る）
  3. ナットストックにもう一度1 m戻ります
  4. 2番目の1000個のナッツについて手順1〜3を繰り返します。
  5. 最後の1000を取って、1 m先に進みます

したがって、すべての獲物との1 mの移動には、ハムスター5ナットが必要です。ナットが<2000になり、これが200 mの移動後に発生した場合、アルゴリズムは次のようになります。

  1. 木の実のほっぺを集めて1 m歩く
  2. 998個のナッツを降ろします（途中で1個、残り1個は戻る）
  3. ナットストックにもう一度1 m戻ります
  4. 最後の1000を取って、1 m先に進みます

1 mの変位には、ハムスター3個のナットが必要です。彼が534 mの地点に到達すると、合計2001年のナッツが食べられ、ハムスターは最後の999個のナッツを取り、残りの466メートルを静かにその穴に入れる必要があります。彼がそこに着くと、533個のナッツが頬に残ります-これが問題の答えになります。

このクラスのタスクは、アルゴリズムの理論や大企業でのインタビューで非常に人気があることに注意したい。それらを解決する方法を学ぶ最良の方法は練習です。それを解決するための単一のメカニズムはありません（まあ、または彼は私を通り過ぎました）が、それらを手に入れ、創造的な思考を発達させることはかなり可能です。

タスク3.分析分布


タスク


Yandexが作成したい Mアナリストのチーム。採用時に、各アナリストは自分が働くグループをランダムに選択します。チームリーダーは、グループの可能性を高めるために、最低何千人のアナリストが採用するのに十分であるかを把握したいと考えています。P 少なくなかった N人？

あなたは受け入れるPythonプログラムを書かなければなりませんN、 Mそして P1行で、出力には何千人ものアナリストが表示されます。
1≤N≤100、 1≤M≤100000、 0≤P≤1

決定


統計学の知識、すなわち二項分布が役立ちました。Yandexが採用したアナリストの数を示しますX。採用したアナリストはそれぞれチームを選択します。私たちのチームリーダーの観点から見ると、アナリストを仕事に雇うことは、2つの結果を伴う実験です：新規参入者が私たちのチームに落ちるかどうか。ヒット確率が等しい1M、アナリストが別のグループをそれぞれ選択する確率は、 M−1M。全体として、チームの選択によるそのような実験はX。私たちのチームのヒット数n の Xアナリストの選出は二項分布され、分布関数は次のようになります。

P(n⩽N)=∑k=0N(Xk)(1M)k(M−1M)X−k

この関数は、ヒット数が指定した値以下になる確率を示します N。ヒット数が特定のヒット数以上になる可能性に関心があるため、タスクは次のようになります。

X:1−Px(n⩽N)=P;X−?


つまり、採用したアナリストの数を見つける必要があります。 Xチームが少なくとも得る Nある確率の人 P。

さて、私たちは数学を理解しました-今それを見つける方法X？バスティング。採用したアナリストの数を並べ替えるサイクルを記述し、少なくとも取得する確率までそれを増やします。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.ギフト調査


タスク


サンタクロースはアナスタシアに100個のプレゼントを運び、クリスマスツリーの下に置きました。木は大きくてふわふわなので、アナスタシアはその下をナビゲートするのが困難です。アナスタシアは贈り物をこのように調べます。誤って木のランダムな側からランダムな範囲に手を伸ばし、贈り物を受け取り、調べて元に戻します。アナスタシアがツリーの下に横たわっている人々から同様におそらく贈り物を受け取ることができるたびに、それは判明します。アナスタシアが100回のランダムなストレッチについて検討するギフトのシェアの期待を見つけますか？

決定


一見すると、タスクは非常に単純に見えます。いくつかの基本的な式によって解を見つけることができるという確信さえありますが、すべてがそれほど単純であるとは限りません。それほど単純ではありません。私はこの作業に多くの時間を費やし、オプションをペイントして式を導き出そうとしましたが、成功しませんでした。それからGoogleに行って、驚いたことに、一般的なケースの解決策を見つける前に、フォーラムを深く掘り下げる必要がありました。したがって、戻り値を持つセットから要素をランダムに選択した場合、確率はn からの選択 mセットの要素は正確に引き出します k異なるイコール：

P(m,k,n)=(mk)⋅k!⋅S2(n,k)mn


どこ S2そこにある第二種のスターリング数からセットの順不同のパーティションの数は-n 上のアイテム k空でないサブセット。さて、期待を見つけるために、この公式によって計算された確率を、100分の1から1分の1まで、調査された固有の贈り物の可能な各部分について合計する必要があります。これは、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.同等確率の旅行者


タスク


トラベラーは、ノード全体が厳密に右または上にある2次元グリッドのエッジに沿って動き始めます。彼はポイントから移動します(0,0) 丁度 (100,100)。考えられるすべてのルートが同じ確率であると仮定すると、始点と終点を結ぶ直線で川を横断する可能性はどのくらいありますか？旅行者が川の真上と真下で同じルートにいた場合、旅行者は川を渡ったと考えられています。川の入口は交差点とは見なされません。

決定


古典的なアプローチを通過する確率を見つけます。交差するルートの数を可能なルートの総数で割ります。させてn-正方形グリッドのエッジの長さ。次に、可能なルートの総数：

N=(2n!)(n!)2


ここでは、式の導出について説明します。しかし、それぞれの河川横断ルートの数を知る方法n？この質問に戸惑ったので、グリッドの長さを少し減らしてフィールドを描画し、依存関係を追跡するために川を横断するルートの数を手動で計算することにしました（今、紙とペンを取り、小さなグリッドとパスの描画を試すことを強くお勧めします）。

サイズ3 x 3セルのグリッドがあるとします。グリッドの対角線は川で占められており、旅行者は左下隅にいます。

画像
絵は完璧ではありませんが、正直に試してみました



描いた途端、川が横断しないルート、つまり川の下のルートを追跡する方がはるかに簡単であることに気付きました。次に、それらの数に2を掛けて、川の上のミラーパスを考慮に入れることができます。ルートの総数もわかっているので、川を渡る人の数がわかります。しかし、メインタスクに戻ります-間の関係が必要ですn川を渡る道の数。

上の図の3x3の場合、私は旅行者がアクセスできるいくつかの「陸」ルートを青でマークしました。マークされたルートは、水平座標2でセルのエッジに沿って通過し、旅行者は以前にセルの左端と上端に進入しません。このようなルートは3つあります。n。次に、列1のセルを通過するルートを特定します。

画像


新しいパスを赤でマークしました。したがって、旅行者がセルの左端、次に上端（1、0）に向かう場合、水平方向の座標が2のセルを通る3つのパスのうち2つだけがアクセスできます。これは、上と右にしか移動できないためです。3番目のパスは下にあります。 。したがって、列1からルートに新しいセルを追加すると、新しいセルよりも低くない列2のセルを通過するルートの数だけパスの総数が増えます。

4 x 4グリッドを取り、もつれを解明し続けます。新しいセルを列に追加すると、次の列を通過するルートの数だけパスの数が増加し、追加したセルの上端以上になることが明らかになりました。ルートを色でマークすることはせず、テキストによる説明に限定しますが、必要と思われる場合は描画します。解決の過程で、自信を持って依存性を感じることができるようになる前に、さまざまなグリッドを描きました。

画像


右端の列はまた私たちに与えます nルート。セルの上端（2、0）が追加されますn−1ルート。セルの上端（2、1）が追加されますn−2ルート。セルの上端（1、0）は、セル（2、0）と（2、1）が合計したルートと同じ数だけルートを追加します。必要に応じて、より大きなグリッドを描画し、同じアルゴリズムでルートを引き続き検討できます。私たちのタスクは、100x100グリッドのルートを計算することです。これを行うには、入力を受け入れるプログラムを書くことができますn マトリックスを作成します 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.線形分布の状態


タスク


線形分布状態は多数の都市であり、そのいくつかは道路で接続されています。

国王がブレークポイントの人々が国境に侵入しようとしていることに気づくと。国が防衛の準備ができていないので、国王は難しい決定をしました-国を多くの小さな国に分割することです。それぞれを独立して国境を守ります。

たとえブレイクポイントの人々が線形分配州の2つの都市の間の1本の道路を占領したとしても、2つの都市は1つの都市から2番目の都市に到達することが可能であれば、1つの州に残すことができるし、残すべきであると決定されました。他のすべての場合では、都市は異なる州にある必要があります。

新しい2つの州の境界を横切る各道路には、要塞を配置する必要があります。これは、これらの状態のいずれかがブレイクポイントの人々によってキャプチャされた場合に必要です。その後、2番目はその国境を防衛し続けることができます。つまり、要塞はさまざまな州の都市を結ぶ道路に配置されます。

王は、要塞を配置する必要がある道路のリストを彼に与えるように頼みました。

プログラムの入出力フォーマット
入力フォーマット

nm— . (1≤n≤20000,1≤m≤200000). m . i bi,ei— , (1≤bi,ei≤n)


b — , . b — , , . , .

, , , , — .


決定


そして、これがグラフ理論の問題です。線形分布の状態の運命についての長い物語のために、起草者は、ノードが都市であり、端が道路であるグラフで橋を見つけるというかなり興味深いタスクを隠しました。簡単に言うと、ブリッジはグラフのこのようなエッジであり、ブリッジを削除すると、このグラフの特定の部分が他の頂点から切り離されます。これは道路をキャプチャするアイデアです-橋がキャプチャされた場合、いくつかの都市間の通信が切断されます。それ以外の場合は、常に都市間に代替道路が存在するため、州が分割するのは橋であり、橋に要塞を配置する必要があります。深さ検索に

基づくブリッジ検索アルゴリズム（深さ優先検索、DFS）-最初の頂点から来るすべてのエッジが調べられるグラフトラバーサルメソッド。エッジがまだ考慮されていない頂点につながる場合、アルゴリズムはすぐにこの頂点から再帰的に開始します。次の事実は、ブリッジの検索に役立ちます

。ここで、頂点Vからすべてのエッジを探して、深く検索してみましょう。次に、現在のエッジ（V、U）が、頂点Uとトラバーサルツリー内のその子孫からのものである場合、逆はありません。 Vまたはその祖先のピークへのパス、考慮されるエッジはブリッジです。

頂点Vについてこの事実を確認する方法を学習するために、頂点ディスクへのエントリ時間を紹介します[V]（英語から。発見された）。この変数には、頂点が処理されたアルゴリズムのステップが記録されます。また、各頂点Vには、最低の[V]変数が関連付けられ、そこに頂点Vから到達できる最も早い頂点Uの発生時刻が書き込まれます。頂点の初期処理中に、最低の[V] =ディスク[V]（より前の頂点にあなたは自分自身を取得しません）、しかし、後で詳細に検索する過程で、Vの祖先につながるそのエッジの1つである息子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時間与えられた-私の意見ではかなり短い時間ですが、誰もが自分のペースで作業します。

私の決定はテストされ、正しい答えが得られましたが、提案されたタスクに対処するより効果的な方法があることは間違いありません。より速く、またはより理解しやすい解決策を提供する準備ができている場合、または私に間違いを見つけた場合は、遠慮なくそれについて書いてください。

皆さんが自分の立場を見つけてほしいです！

More articles:


All Articles