Yandexでの夏のインターンシップのテスト割り当てに合格した方法

画像






こんにちはHabr、今日は、Yandexでの夏のインターンシップのテスト課題に合格した方法についてお話します。 この出版物は、初心者開発者、Olympiadプログラミングの愛好家、C ++やJavaに無関心でない人、または忙しい一日の後に興味深い記事を読みたい人に役立ちます。



この記事に何を期待しますか?





はじめに



Yandexでのインターンシップの選択システムに詳しくない人のために、簡単に説明します。 夏の数か月前のYandexのウェブサイトで、仕事をしたい部門(Yandex.Disk、Yandex.Alisaなど)の初心者デベロッパー向けの空席が発表されました。 参照により、あなたはどこで勉強しているか、何をしているのか、仕事の経験は何であったのか、論文について何を書いたのかなどのフォームに記入する必要があります。 フォームへの記入後、テストタスクがメールに送信されます。テストタスクは、この手紙を受け取った瞬間から1週間以内の任意の日に6時間で完了します。



今回は選ぶのが難しかったので、ほぼ最終日になりました。 すべての理由は、どのようなテストタスクを期待すべきかわからなかったからです。 多くの記事を読み終えた後、Yandexがインターンシップにどのようなタスクを設定するかについての単一の例やアドバイスは見つかりませんでした。 それが、私がこの記事を書くことにした理由です。 これらの問題に対する正しい解決策を提供するのではなく、割り当てられた6時間でなんとかなることしかできません。



テストタスクには、被験者が異なり、複雑さが異なる6つのタスクがありました。 時間と浮動小数点数のフォーマットに関するグラフ、線、動的プログラミング、およびアドホックに関するタスクがありました。



タスク1.エラー



職務条件
ウェブサイトを維持し、新たな問題を追跡します。 クライアントは、システムに投稿を追加しようとした後にエラーを受け取りました。 このエラーが発生したサーバーを把握する必要があります。



n個のサーバーがあり、それらのi番目にaiパーセントの要求があり、そのうち2パーセントが失敗します。 サーバーごとに、エラーが発生した確率を見つけます。



入力形式

入力ファイルの最初の行には、1つの整数n(1≤n≤100)-サーバーの数が含まれています。



次のn行にはそれぞれ、2つの整数ai bi(0≤ai、bi≤100)が含まれます-リクエストがi番目のサーバーに送信される確率(パーセント)と、パーセントエラーがi番目のサーバーで発生する確率。



すべてのaiの合計が100であり、システムでエラーが発生する可能性があることが保証されています。



出力形式

n行を印刷します。 各行には、1つの実数(0≤pi≤1)-対応するサーバーでエラーが発生した確率を含める必要があります。



各回答の絶対誤差または相対誤差は10-9を超えてはなりません。

例1

入る



2

50 1

50 2

おわりに

0.333333333333

0.666666666667



例2

入る



3

10 100

30 10

60 2

おわりに

0.704225352113

0.211267605634

0.084507042254



この問題を解決するために、Javaを使用することにしました。



演算アルゴリズムは非常に単純です。n個の場合にa、bを読み取り、a とbを乗算し、乗算の結果をarr [i]に保存し、結果を変数totalに合計して100%を計算します。

出力するには、arr [i]を100%で割るだけです。



解決策
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Locale; import java.util.StringTokenizer; public class Main { public static void main(String[] args)throws IOException { Locale.setDefault(Locale.US);//     (0.3333,  0,333) String line; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); //Buffered Reader     Scanner,      ,      StringTokenizer tk;//       int n = Integer.parseInt(br.readLine()); int arr[] = new int[n]; int total = 0; for(int i = 0; i< n;++i) { line = br.readLine(); tk = new StringTokenizer(line); int a = Integer.parseInt(tk.nextToken()); int b = Integer.parseInt(tk.nextToken()); arr[i] = (a*b); total += arr[i]; } for(int i = 0; i< n;++i) { System.out.printf("%.12f\n", (double)arr[i]/ total); } } }
      
      







それだけです、それは私が完全に解決することができた最初と最後のタスクでした。 残りのタスクは、残念ながら時間がありませんでした。私はリラックスして、後続のすべてのタスクが同じレベルになると考えていたためです。 悲しいかな、これは間違っていることが判明しました。 次のタスクのためにあなたと私のコードを作成しようとします。



タスク2.ミーティング



職務条件
大声で話し合うことで職場の同僚に迷惑をかけないようにするために、彼らは一定の時間の予約を取り、会話を予約します。 予約時には、会議の日時、会議の期間、参加者のリストを指定する必要があります。 参加者の1人が同時に2つの会議を開催する場合、会議は他の会議と重複する人のリストの表示で予約が拒否されます。 このようなシステムのプロトタイプを実装する必要があります。



入力形式

入力ファイルの最初の行には、1つの数値n(1≤n≤1000)-要求の数が含まれています。



次のn行には、1行に1つずつクエリが含まれます。 クエリには2つのタイプがあります。



APPOINT日中時間k names1 names2 ... namesk

曜日名を印刷

日-2018年の日数(1≤日≤365)



time-会議時間、HH:MM形式の文字列(08≤HH≤21、00≤MM≤59)



期間-分単位の会議の期間(15≤期間≤120)



k-会議の参加者の数(1≤k≤10)



namesi、name-参加者の名前、小文字のラテン文字で構成される文字列(1≤| name |≤20)。 すべての同僚には一意の名前があります。 さらに、1つの会議の参加者間で、1つの名前が2回検出されることはありません。



出力形式

予定を作成できる場合(最初の種類の要求)、[OK]を印刷します。



それ以外の場合、最初の行にFAILを出力し、次の行に、会議の時間が他の会議と交差する参加者の名前のリストを、名前がリクエストで与えられた順に入力します。



2番目のタイプのリクエストの場合、この日と参加者に対して、その日に現在発生しているすべてのイベントのリストを時系列で、行ごとに1つの形式で表示します。



HH:MM期間names1 names2 ... namesk



参加者の名前は、会議の元の説明と同じ順序で続きます。 この人にこの日にイベントがない場合、何も表示する必要はありません。

例1

入る

7

APPOINT 1 12:30 30 2アンドレイ・アレックス

APPOINT 1 12:00 30 2アレックスセルゲイ

APPOINT 1 12:59 60 2アレックスアンドレイ

プリント1アレックス

プリント1アンドレイ

1セルゲイの印刷

プリント2アレックス

おわりに

わかった

わかった

不合格

アレックス・アンドレイ

12:00 30アレックスセルゲイ

12:30 30アンドレイ・アレックス

12:30 30アンドレイ・アレックス

12:00 30アレックスセルゲイ



この問題の解決策を考えるのに多くの時間を費やし、多くのオプションを試しましたが、時間+日+人の数を最も効果的に詰め込む方法を決めませんでした。 構造体を書きたかった{int day; int time_ms; string people [];}、しかしそれはメモリ使用量が非効率的です。



別のオプションは、すべての曜日と時間を線形に表し、3つの変数を保存する構造(会議)を作成することです-会議の開始(日* 24 * 60)(時間* 60 +分)、会議の終了(開始+期間)、この会議の人々の名前。 この構造のすべてのオブジェクトは、ベクトル(vec)にパッケージ化できます。 次に、新しいアポイントメントを作成するときに、次のステートメントが当てはまるベクトルに存在する会議に会議があるかどうかを確認します。

 vec[i] -> start<= meeting->start && vec[i] -> end >= meeting->start or vec[i] -> start <= meeting->end && vec[i] -> end >= meeting->end
      
      





「はい」の場合、この時間がかかっていると言い、そうでない場合は、ベクトルに新しい要素を追加します。

また、Pythonのdictを使用してこの問題を解決しようとしましたが、他のタスクに多くの時間を費やしたことに気付きました。 6時間の終わりの10分前に文字通りこのタスクに戻りました。ほとんど考える力がなかったので、時間があると書いて、少なくとも何かを渡しました。 おそらく、この問題の2番目の解決策だけを完成させたら、OnlineJudgeは受け入れたでしょう。 しかし、私は次のJavaコードを渡しました。 安全にスキップできますが、実際には何もしません。



解決策
 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class p2 { public static void main(String[] args) throws IOException { String line; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer tk; long unixTime = System.currentTimeMillis() / 1000L; System.out.println(unixTime); int n = Integer.parseInt(br.readLine()); for (int i = 0; i < n; ++i) { line = br.readLine(); tk = new StringTokenizer(line, " :"); String cmd = tk.nextToken(); if (cmd.compareTo("APPOINT") == 0) { int day = Integer.parseInt(tk.nextToken()); int hour = Integer.parseInt(tk.nextToken()); int minute = Integer.parseInt(tk.nextToken()); int duration = Integer.parseInt(tk.nextToken()); int peopleN = Integer.parseInt(tk.nextToken()); String people[] = new String[peopleN]; for (int j = 0; j < peopleN; ++j) { people[j] = tk.nextToken(); } int start = (hour * 60) + minute; int end = start + duration; } } } }
      
      







タスク3.自動補完



職務条件
Arkadyはインタラクティブなオートコンプリートシステムを実装しました。これにより、卒業証書を含む大学の作品のテキストをすばやく入力できるようになります。



システムは、すでにテキストにあるすべての単語を記憶します。 Arkadyが別の単語を入力し、その空でない部分がすでに入力された単語の正確に1つのプレフィックスと一致する場合、特別なキーの組み合わせを押すと、入力された部分に既存の単語がすぐに追加されます。



たとえば、Arkadyはすでにさまざまなシステムで論文と自動補完という言葉を入力しています。 彼が入力する必要がある次の単語のいくつかのオプションを検討してください。



  • 卒業証書-最初の文字を入力すると、システムは卒業証書の修了を受け入れますが、適合しません。
  • 仕事-最初と2番目の文字を入力した後、システムは何も提供しません。 テキストには現在のプレフィックスで始まる2つの異なる単語がありますが、3番目の文字を入力した後は1つの単語のみが残ります(提案されたオートコンプリートを受け入れる必要があります)。
  • 違い-オートコンプリートを使用したオプションは、3番目の文字を入力した後にのみ表示されますが、今回は提案されたオプションは受け入れられません。


Arkadyには、入力した文字の削除キーがないため、テキストから文字を削除できません。



Arkadyは、提案された単語がダイヤルの始まりである場合、オートコンプリートを使用しないことも決定しましたが、完全には一致しません。



Arkadyがアルファベット文字に対応するキーボードキーのキーストローク数を最小限に抑えたい場合、オートコンプリート機能を使用する回数を決定するのに役立ちます。



入力形式

入力の最初の行には、1つの整数n(1≤n≤100 000)-Arkadyが入力する単語の数が含まれます。 2行目には、n個の単語si(1≤| si |≤1000)が含まれます。 文字列内のすべての単語は小文字の英字のみで構成され、単一のスペースで区切られます。



すべての単語の合計長は1,000,000文字を超えません。



出力形式

1行に1つの整数(キーボードの文字キーのキーストローク数)を出力します。

例1

入る

3

こんにちは、こんにちは

おわりに

11

例2

入る

5

りんごりんご

おわりに

13

例3

入る

5

aaaaa aaaab aaaaa abaaa abaaa

おわりに

22



このタスクは、トートロジーに申し訳ありませんが、実際に行われることが判明したよりもはるかに簡単に思えました。 その結果、私の決定は完了しませんでした-WAは14回目のテストで出てきました。 ここでは、どこに間違いがあるのか​​を理解しようとしても多くの時間を費やしましたが、何もできませんでした。 セットデータ構造を使用してこの問題を解決するのは簡単だと思ったので、C ++で書くことにしました。



解決策
 #include <iostream> #include <set> using namespace std; int main() { set<string> myset; string in; int n; cin >> n; int count = 0; for(int i = 0;i<n;++i) { cin>>in; if(myset.empty()) { count += in.length(); myset.insert(in); } else if(myset.find(in) != myset.end()) { //if a word is in set //check if other words in set contain similar chars //count += the greatest common subsequence int max = 0; for(auto e: myset) { int temp = 0; //case when entered sequence is less than element in set if(e == in) { ++count; } if(e.length() > in.length()) { for(int j = 0; j< in.length(); ++j) { if(e[j] == in[j]) { ++temp; } else { break; } } if(temp > max) { max = temp; } } else if(e.length() <= in.length() && e != in) { for(int j = 0; j< e.length(); ++j) { if(e[j] == in[j]) { ++temp; } else { break; } } if(temp > max) { max = temp; } } } count += max; } else if(myset.find(in) == myset.end()) { //case when entered word is not in the set count += in.length(); myset.insert(in); } } cout << count<<endl; return 0; }
      
      







一般に、この問題は2つの大きなケースに分けられます。新しい単語が導入される(単語がセットに含まれない)と、すでに入力されている単語が入力される(セットに含まれる単語)。



2番目のケースは他のいくつかのケースに分割され、1。入力単語と同じ文字(シンボル)で始まるセットに単語があるかどうか、2。単語サブシーケンスがセット内の他の単語であるかどうかがチェックされます。 コードでわかるように、それぞれの場合、count変数の異なる量のキーストロークが合計されます。



タスク4.チームビルディング



職務条件
チームビルディングは楽しい集会イベントです。 同僚はコンテストやクエストに積極的に参加し、一緒にゲームの難しさを克服します。 時々、人々は非常に夢中になり、いくつかの新しい活動のために彼らを再編成することは非常に困難です。 現在、ファシリテーターはすべての同僚を2つのチームに分けて、同じチームの2人がお互いをよく知っているようにする必要があります。これは簡単な作業ではありません。



各人に1つの頂点が関連付けられているグラフが表示されます。 エッジ(u、v)は、同僚uが同僚vをよく知っていることを意味します(同時に、同僚vは同僚uをよく知っています)。 グラフの頂点を必要な方法で2つのセットに分割できるかどうかを確認し、可能であれば、適切なパーティションを印刷します。



入力形式

最初の行には、2つの整数nとm(2≤n≤5000、0≤m≤200000)-グラフの頂点の数とエッジの数が含まれています。



次のm行は、エッジの説明を示します。1対の整数ab(1≤a、b≤n、a≠b)は、頂点aとbの間にエッジが存在することを示します。



頂点の各ペアが1つ以下のエッジで接続され、頂点がそれ自体に接続されていないことが保証されます。



出力形式

必要な方法で頂点を分割できない場合は、-1を印刷します。



それ以外の場合、最初の行に数値k(1≤k <n)-パーティションのいずれかの部分の頂点の数を出力します。



次の行にk個の数字-パーティションのこの部分の頂点を印刷します。



次の行では、パーティションの2番目の部分の頂点-n-kの数字を印刷します。



各頂点は、これらのパーツのいずれか1つに属している必要があります。

例1

入る

3 1

1 2

おわりに

2

1 2

3

例1

入る

3 0

おわりに

-1



それから私はすでにパニックに陥り始め、最初の問題を解決した後に感じた自信は跡形もなく消えました。 私はどのタスクに集中すべきか分からず、いずれかのタスクの状態を読むことを急いだ。 パニックに対処するのに約20分かかりました。 これは、コンテストの問題を解決するために壊滅的に多くのことです。



ここで、私もセットを使用することにしました。 より正確には、3 Set'a:initial-1からnまでの値が格納される場所、グラフの最初のリンクが追加されるteamA、teamAに接続されていないリンク、およびinitialの残りのすべてのリンクが追加されるteamB。



私のアルゴリズムはシンプルですが、明らかにYandexは私にもっと期待しています。 3番目のケースのWA。



決定
 #include<iostream> #include<set> using namespace std; int main() { int people; cin >>people; int pairs; cin >> pairs; set<int> initial; set<int> teamA; set<int> teamB; int a; int b; if(pairs == 0) { cout<<"-1"<<endl; } else { //fill set with people for(int i = 1;i<=people;++i) { initial.insert(i); } for(int i = 0;i<pairs;++i) { cin >> a; cin >> b; // case when a and b aren't in teamB if(initial.find(a) != initial.end() && initial.find(a) != initial.end() && !teamA.empty()) { teamB.insert(a); teamB.insert(b); initial.erase(a); initial.erase(b); } else if(teamB.find(a) == teamB.end() && teamB.find(b) == teamB.end()) { teamA.insert(a); teamA.insert(b); initial.erase(a); initial.erase(b); } else if ((teamA.find(a) != teamA.end() && teamB.find(b) != teamB.end()) or (teamA.find(b) != teamA.end() && teamB.find(a) != teamB.end())) { for(auto e: teamB) { teamA.insert(e); teamB.erase(e); } } } } cout <<"teamA"<< endl; for( auto e: teamA) { cout << e<<" "; } cout <<endl<<"teamB"<< endl; for( auto e: teamB) { cout << e<<" "; } cout << endl; return 0; }
      
      







タスク5.ライブラリ



職務条件
Kolyaは本を読むのが大好きで、毎日図書館に行きます。 夕方までに、彼は昨日よりも正確に1冊以上本を読んだ場合にのみ満足しています。 ただし、残念ながら、土曜日と日曜日は図書館が閉鎖されます。 そのため、Kolyaは毎日仕事に行き、一度にk冊の本を取ります-あなたはもはやルールに従うことができません。 ただし、Kolyaは、以前に撮影した書籍から本を配らなかった場合でも、新しいk本を撮影できることを嬉しく思っています。 Kolyaは、自宅の図書館にm本の本があることも喜んでいます。



今日は何曜日かわかります。 Kolyaは最近起きて、今日ちょうど1冊の本を読むようになりました。 Kolyaは、今日から可能な限り毎回図書館に行く場合、どれくらい満足できますか? 図書館での本の供給は無限であると想定できます。



入力形式

入力ファイルの最初の行には3つの整数k、m、dが含まれています。1日あたりの図書館で持ち込める本の数の制限、Kolyaの家の本の数、現在の曜日(1≤k≤109、0≤m≤109、 1≤d≤7)。 土曜日と日曜日は、数字6と7で示されます。



出力形式

1つの数字を印刷します-Kolyaが毎日非常に多くの本を読んで満足を維持できる期間の最大日数。

例1

入る

4 2 5

おわりに

4

例2

入る

4 3 5

おわりに

5



この問題を解決して、どれだけ見逃しているかに気づきました

uDebug 。 私の決定は10回目のテストでWAを投げました。



解決策
 #include<iostream> using namespace std; int main() { int bks; cin >> bks; int lib; cin >> lib; int day; cin >> day; int total = bks + lib; int count = 0; int read = 0; while(true) { ++count; ++read; if(day>=1 && day <= 5) { total -= read; if(total == 0) { break; } else { total += bks; } } else if(day == 6) { total -= read; if(total == 0) { break; } } else if(day == 7) { total -= read; if(total == 0) { break; } day = 0; } ++day; } cout << count; return 0; }
      
      







タスク6.動員



私は基本的にコンテスト中にこのタスクを取りませんでした。 読み取りと出力専用のコードを書きました。 コンテストを完了した後、これ以外のすべてのタスクを整理しました。 正直なところ、私はまだ何をする必要があるかを正確に理解できません。 私はあなたのコメントに喜んでいるでしょう。



職務条件
プロジェクト "Mobilization"がYandexで再び開始されます! 同社は、3か月間のトレーニングのために、モバイル開発に熱心なn人の若者を採用しています。 プロジェクトの開始時に、開発の参加者iのスキルがai、管理のスキルがbiとして評価されるテストが実施されました。



プロジェクトの期間中、参加者は、開発者とマネージャーという参加者の数に等しい2つのチームに分割する必要があります。 すべての参加者がもたらす総利益を最大化するような方法でこれを行うことが計画されています。 参加者が開発者の役割を取得する場合、彼の利益はai、そうでない場合はbiになります。



しかし、プロジェクトに関係する人々でさえ、参加者は新しい知識を得る時間を見つけます! 参加者が修了証を提出する場合があります。開発または管理の参加者iのスキルがdi増加したと言われています。 このような場合、チーム全体を最大限に活用するためにチームを改革することが有利な場合があります(チームのサイズを等しく維持する必要があります)。



あなたの仕事は、Yandexを支援することであり、参加者によってもたらされたそれぞれの新しい証明書を検討した後、チームの現在の総利益を計算します。



入力形式

入力ファイルの最初の行には、番号n(2≤n≤2⋅105、nは偶数)-プロジェクト参加者の数が含まれています。 2行目は、n個の整数ai(0≤ai≤109)を定義します-開発の各参加者のスキル。 同じ形式の次の行は、biコントロールの参加者のスキルを設定します(0≤bi≤109)。



次の行には、整数m(1≤m≤105)-参加者によってもたらされた証明書の数が含まれています。 次のm行のそれぞれには、3つの整数numi、typei、di(1≤numi≤n、1≤typei≤2、1≤di≤104)が含まれています-参加者の数、スキルの種類(1-開発、2-管理)および対応するスキルの増加の値。



出力形式

新しい証明書の各要求を処理した後、すべての参加者の現在の総利益を印刷します。

例1

入る

4

7 15 3 4

10 10 0 6

3

1 1 4

4 1 6

2 2 10

おわりに

34

35

43



私がなんとか書いたコード
 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class p6 { public static void main(String[] args)throws IOException { String line; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer tk; int n = Integer.parseInt(br.readLine()); int a[] = new int[n]; int b[] = new int[n]; tk = new StringTokenizer(br.readLine()); int aSum = 0; for(int i = 0;i<n;++i) { a[i] = Integer.parseInt(tk.nextToken()); aSum += a[i]; } int bSum = 0; for(int i = 0;i<n;++i) { b[i] = Integer.parseInt(tk.nextToken()); bSum += b[i]; } } }
      
      







まとめ



全体として、私はこの経験が好きでした。 最善を尽くせなかったのは少し残念です。 しかし、今では、Yandexでのインターンシップのタスクがどのようなものであるかがわかりました。この記事を読んだ後、あなたも知っています。 この記事がおもしろくて、少なくとも少しはお役に立てば幸いです。 私はコメントや提案を心から喜んでいます。 この記事を書いている間、私はあなたがこれらの問題を解決するためのオプションを共有することを期待しました。



みんなありがとう!



All Articles