黒板や紙にコードを書くアルゴリズムセクションは、開発者がYandexで仕事を得るための就職面接の最も重要な段階の1つです。 これらのセクションがどのように構成され、将来の候補者が準備に役立つかについて、より詳細に話すことにしました。 さらに、この物語が現実にすべてがそれほど怖くないということを理解した後、あまりにも難しいテストを恐れて、インタビューのためにYandexに来ることを敢えてしない人の多くが願っています！
そこで、次の資料を用意しました。
- 面接で行うものと同様のタスクを含む特別なコンテスト 。
- この投稿 。 コンテストのすべてのタスクを理解するだけでなく、そのようなセクションを実施する必要がある理由についても説明します。
- コンテストのタスクを整理した2つのビデオ： 最初の -タスクはより単純で、 2番目の -2つのタスクはより困難です。 これらのビデオから、アルゴリズムのセクションを通過するときと、プロダクションコードを記述するときに起こる典型的な間違いについて学びます。
開発者にインタビューする方法
開発者とのインタビューは、いくつかの段階で構成されています。
- リクルーターとの予備セクション。
- スカイプの技術面接。
- いくつかのフルタイムセクション。
- 採用マネージャーとの最終インタビュー。
予備セクションでは、リクルーターは候補者と知り合い、候補者を検討することが理にかなっている立場を理解するために、彼の興味と動機を学びます。 テクニカルスカイプインタビューは、候補者のスキルを予備的に評価することを目的としており、フルタイムのセクションに確実に対処できない人を排除します。
フルタイムセクション-メインステージ。 候補者が何ができるかという質問に答えるのは、フルタイムのセクションです。 アルゴリズムセクションは、フルタイムの技術セクションの1つです。 アルゴリズムテストに加えて、他の対面テストがあります。たとえば、上級開発者の候補者はアーキテクチャセクションを通過する必要があり、将来のリーダーもチームとプロジェクトの管理に関する質問に答えます。 一般に、候補者が特定の分野（機械学習、低レベルの最適化、負荷の高いシステムの開発、モバイル開発など）で何らかの強みを持っている場合、専門のスペシャリストでセクションを確実に編成します。
アルゴリズムセクションでは、テストの質とソリューションの速度のバランスを保ちながら、候補者が単純な問題を解決するためのアルゴリズムを考え出し、これらのアルゴリズムの複雑さを評価し、エラーなく実装できるかどうかをチェックします。
黒板や紙にコードを書く理由
プログラマにとって自然な状態は、構文の強調表示とトレーサビリティを備えた統合開発環境でのプログラミングです。 したがって、最初に黒板や紙にコードを書くというインタビューのアイデアは、あまりにも自然に思えません。 ただし、この方法では、各開発者にとって非常に重要な2つのプロパティを確認できます。
その1つは、コードのパフォーマンスを「目で」すばやく処理する機能です。 プログラムに表示される各サイクルを作成するとき、開発者はトレースによって機能することを確認しようと時間を費やす必要があると想像してください。 または、サービスが実稼働環境でクラッシュした場合、常にデバッガーの下でコードを実行する必要があります。 単純なプログラムの作成とデバッグでも、許容できないほど長い時間がかかることは明らかです。 もちろん、コードレビューでコードを読むことができると便利です。
2番目の重要な特性は、ソリューションプランを事前に検討し、それに従うことです。 計画がない場合、多数の修正、取り消し線（紙上）、および大きなコードの書き直しにつながります。 実際には、これはすべて開発を大幅に遅くしますが、コードエディターでの作業速度によって部分的に隠されます。 この意味でのボードと紙は容赦ない表面です。
当然、手作業でコードを書くのは速すぎません。 したがって、私たちのタスクは通常、数十行以内で解決する必要があり、1つのセクションで解決する必要があるタスクの数は通常2つまたは3つです。
アルゴリズムセクションとスポーツプログラミング
スポーツプログラミングは、とりわけ将来の開発者で開発されており、迅速かつエラーなしで、所定の計画に従って簡単なアルゴリズムを実装する機能です。 したがって、スポーツプログラミングの経験がある候補者は、実際、インタビューのアルゴリズムセクションで良い仕事をします。 多くの場合、将来の研修生がアルゴリズムセクションに簡単に対応でき、15〜20分ですべての問題を解決できる一方で、経験豊富なプログラマが同じタスクに1時間を費やす状況を観察できます。
同時に、コードを記述するアルゴリズムセクションは、開発者に必要な最小限のスキルをテストするセクションの1つにすぎません。 olympiadプログラマーのみがこのセクションに対処するだけでなく、経験豊富な産業開発者も対応します。 将来のシニア開発者またはチームリーダーは、彼が自分の最強のポイントを明らかにできるアーキテクチャセクションを確実に待っています。 もちろん、このセクションは研修生やジュニア開発者には決して使われません。
面接準備コンテスト
特に、アルゴリズムセクションで説明するタスクの内容を大まかに想像できるように、インタビューの準備に使用できるコンテストをまとめました。 デバッガーを実行しないで、すべての問題を解決してください。 構文を強調せずにメモ帳でソリューションを作成します。 すべてのテストに合格する最短の解決策を考え出す。 考えられるすべての問題を事前に考え、最初に解決策を渡します。
コンテストには5つのタスクが含まれます。 それらを自分で解決するか、事前に分析を読むことができます。 既知のアルゴリズムのエラーのないコーディングのスキルを訓練することができます。
文字列Jと文字列Sの2行の小文字ラテン文字が与えられます。文字列Jに含まれる文字は「宝石」であり、文字列Sに含まれる文字は「石」です。 Sから同時にいくつのキャラクターが「宝石」であるかを判断する必要があります。 簡単に言えば、Sの文字がJにいくつあるかを確認する必要があります。
これは非常に単純なウォームアップタスクであり、参加者がテストシステムに慣れることができるように、いくつかのプログラミング言語のソリューションが含まれています。
アルゴリズムは非常に単純です。「宝石」のある行からセットを作成し、「石」のある行に沿って進み、このセットに入るために各文字をチェックする必要があります。 このようなセットの実装を使用して、入力ラインが非常に短いため、結果の解の線形複雑度を保証します。したがって、複雑度が2次のアルゴリズムでも渡すことができます。
バイナリベクトルで最も長い単位のシーケンスを見つけて、その長さを出力する必要があります。
解決アルゴリズムは次のとおりです。配列のすべての要素を調べます。 一致する場合は、現在のシーケンスの長さのカウンターを増やす必要があり、ゼロになる場合は、このカウンターをリセットする必要があります。 最後に、カウンターが取得した値の最大値を表示する必要があります。
配列が目的のユニットのシーケンスで終了する状況を処理していることを確認してください。 慎重に実装すれば、この状況では特別な処理は必要ありません。
一定量の追加メモリのみを使用するようにしてください。
減少しない順序で並べられた32ビット整数の配列が与えられます。 すべての繰り返しを削除する必要があります。
正しいアルゴリズムは、配列の要素を順番に処理し、それらを最後の出力と比較します。 表示された最後の要素を含む変数を更新することを忘れないでください。さらに、最後の要素を処理するときに間違えないようにしてください。
この問題を解決するとき、追加のメモリを使用する必要もありません。
整数が与えられた 。 長さの正しいブラケットシーケンスをすべて印刷する必要があります。 辞書順に並べられます （ https://ru.wikipedia.org/wiki/Lexographic_orderを参照）。 タスクでは括弧のみが使用されます。
これは、比較的複雑なアルゴリズム問題の例です。 1文字のシーケンスを生成します。 各瞬間に、現在のシーケンスに開始ブラケットまたは終了ブラケットを割り当てることができます。 前にn個未満の開始ブラケットが追加されている場合は開始ブラケットを追加でき、現在のシーケンスで開始ブラケットの数が終了ブラケットの数を超える場合は終了ブラケットを追加できます。 このようなアルゴリズムは、慎重な実装により、回答の辞書式順序を自動的に保証します。 nに対する応答の要素数の積に比例した時間で動作します。 これには、線形の追加メモリが必要です。
無効なアルゴリズムの例は次のとおりです。すべての可能なブラケットシーケンスを生成し、正しいと判明したもののみを出力します。 同時に、答えの量によっては、上記のアルゴリズムよりも速く問題を解決することはできません。
このかなり単純なタスクは、連想配列を使用する必要があるソリューションの典型的な問題の例です。 決定するときは、文字を繰り返すことができることを考慮する必要があるため、セットではなく辞書を使用する必要があります。 したがって、解決策は次のようになります。各行から、各文字の繰り返し回数を格納する辞書を作成します。 次に、結果の辞書を比較します。 一致する場合は1つ、そうでない場合は0を印刷する必要があります。
代替ソリューション：入力行をソートしてから、それらを比較します。 このソリューションは、実行速度が遅く、入力も変化するという点で悪いです。 しかし、このソリューションは追加のメモリを使用しません。
インタビュー中に、特性が異なるいくつかの解決策があった場合、それについて教えてください。 開発者が問題を解決するためのいくつかのオプションを知っていて、それぞれの長所と短所について話すことができれば、それは常に素晴らしいことです。
与えられた それぞれが100を超えない、非減少順でソートされた非負整数の配列。合併の結果を作成する必要があります。元のすべての要素を含む非減少順でソートされた配列 配列。 各配列の長さは超えません 。
配列ごとに、ポインターを作成します。 最初は、各ポインターは対応する配列の先頭にあります。 最小値の抽出をサポートする任意のデータ構造内のポインターの位置に対応する要素を配置します-それはマルチセットまたは、例えば、束にすることができます。 次に、この構造体から最小要素を抽出し、応答して、対応する配列内のポインターの位置をシフトし、この配列から次の要素をデータ構造体に配置します。
このタスクでは、多くの人が入力形式に問題を抱えています。 行の最初の要素は配列の要素を記述するのではなく、配列の長さを記述することに注意してください！
コンテストFAQ
A： 私は間違いなく正しいコードを書きましたが、テストは失敗します。 おそらくそれらの間違い？
Q：いいえ、すべてのテストは正しいです。 考えてみてください。あなたはおそらく異常な状況を予見しなかったでしょう。
A： 私はXで書いていますが、タスクYでは間違いなくより多くのメモリが必要です。制限を引き上げてください！
Q：すべての制限は、利用可能な言語のいずれかを使用してソリューションが可能になるように設定されます。 メモリ制限が厳しいタスクで入力ファイル全体を誤って読み取っていないかどうかを確認してください。
A： 指定された制限により、一部のタスクははるかに簡単に解決できます。 なぜこれをしているのですか？
Q：参加者がアルゴリズムの実装に集中しやすくなり、たとえば、データのダウンロード速度やスポーツプログラミングで重要なその他のことを考えずに済むように、一部のタスクの入力を明確に簡素化しました。 推奨されるアルゴリズムを正確に実装してください。この状況でのみ、コンテストから最大限の利益を得ることができます。
A： コンテストに合格したくありません。 できませんか？
Q：もちろんです！ コンテストはすべての候補者を拘束するものではありません。 ただし、それを解決することをお勧めします。どのような場合でも有用です。
A： 準備には他に何をお勧めしますか？
Q：Yandexでのインタビューに関する公式ページ（ https://yandex.ru/jobs/ya-interview）でヒントを読んでください 。 私自身、leetcode.comの問題を解決することは、近い将来インタビューを行うか、プログラミングコンテストに参加するかどうかに関係なく、開発中の開発者にとって非常に役立ちます。 少しでも練習すれば、仕事の課題をより自信を持って感じることができます。
おわりに
私は開発者や開発マネージャー向けの会議に頻繁に出席し、多くの開発チャットのメンバーであり、数百のインタビューを実施し、Yandexで膨大な数の開発者を雇いました。 経験上、ボードまたは紙にコードを書くアルゴリズムのセクションではしばしば疑問が生じることが示唆されています。 結論として、私はそれらの最も人気のあるものに答えます。
開発者の実際の条件とは非常に異なる条件でインタビューを行うのはなぜですか？
これにより、候補者がデバッガを起動せずにプログラムの問題を見つけることができるかどうかを理解できます。 彼が事前にアルゴリズムの計画を考え出し、それを正確に追跡できるかどうか。 小さいが十分なテストセットを考え出し、このテストセットに対して実装を確認できますか。
そのようなセクションは、スポーツプログラマに不公平な利点をもたらしますか？
スポーツプログラミングは開発者に非常に有用なスキルを開発するため、オリンピックのプログラミングの参加者はアルゴリズムセクションで非常にうまく機能します。 利点はありますが、公平です。 アルゴリズムセクションは多くのセクションの1つにすぎないため、各候補者は自分の強みを示すのに十分な機会があります。
すべてのアルゴリズムがすでに長い間実装されており、既成のライブラリで実装を探す必要がある場合に、なぜアルゴリズムセクションを実行するのですか？
すべての開発者に共通のアルゴリズムセクションで、最小限の必要なスキルのみをテストします：ループを含み、条件をチェックし、場合によっては連想配列の使用を必要とする単純なアルゴリズムを実装するために、エラーの有無にかかわらず能力をテストします。 このタイプのコードは、ユーザーサービスの実装用に常に記述されています。
膨大な量の開発者スキルをテストしないセクションのポイントは何ですか？
実際、アルゴリズムセクションは、開発者に必要な最小限のスキルセットのみをチェックします。 他のセクションの助けを借りて、他のスキルをテストします。
すべての専門分野の開発者向けにアルゴリズムセクションを実施していますか？
はい アルゴリズムセクションは、バックエンド開発者、アナリスト、モバイルおよびフロントエンド開発者、インフラストラクチャおよび機械学習方法の開発者などのために開催されます。