Codility形式のコーディングテスト対策

実際のテストでよく見られる内容

Codilityのテストは1種類ではありません。 Codilityはプラットフォームです。各雇用主が、テストで出題する課題、使用できる言語、制限時間を選びます。受験するテストについては、雇用主から届く案内が最も確かな情報源です。

Codilityが説明している内容。 Codilityによると、各課題は定められた基準に照らして自動採点されます（Codility）。プログラマー向けの無料レッスン（Codility）では、短い問題、作成する関数、明記された入力上限といった課題の形式を確認できます。たとえば、BinaryGapのレッスン課題では、最大2,147,483,647までの入力に対して「効率的なアルゴリズム」を求めています（Codility）。また、Time Complexityというタイトルのレッスンもあります（Codility）。

Codilityテストについて一般に報告されていること（受験者やガイドによる情報で、読み込み可能なCodilityのページでは確認できていません）：

• 1つの制限時間内に複数の課題：テスト全体で使える時間は、30分から2時間のことがよくあります。
• 非公開の正答テスト：課題の例だけでなく、受験者には見えないケースでもコードが検証されます。
• 大きな入力に対する処理性能：アルゴリズム課題では、正しくても遅い解答は減点されることがあります。
• かかった時間：制限時間内であれば、解答にかかった時間は得点に含まれません。

当サイトの模擬テストで扱う内容。 各フル模擬テストは、易しい課題から難しい課題へと進む90分間で3つのコーディング課題です。Python、JavaScript、Java、C++のいずれかで解答を書いて実行できます。解答は非公開のテストケースで検証され、通過したケースごとに得点が加算されます。ノートパソコンの使用をおすすめします。提出するまでは、前の課題に戻って解答を変更できます。

当サイトの模擬テストで異なる点。 実際のCodilityの課題は、一般に正確性が検証され、多くの課題では大きな入力に対する処理性能も確認されると報告されています。当サイトの非公開ケースは小規模で、正確性と境界ケースを確認するため、遅い解答でも時間切れにはなりません。各課題の解説では、大きな入力に対応するために必要な計算量を説明しています。無料の10問は、正確性、計算量、境界ケース、速度についての選択式問題で、こうした検証を通過するために必要な考え方を練習できます。

解き方の例付き問題タイプ

各タイプの問題について、よくある落とし穴を含む例題を1問ずつ紹介します。

1. どの解法が正しいか。 課題: リスト内の異なる値の数を返します。解法: len(set(A))。空のリストを含むすべてのリストで正しく、空のリストの場合は0を返します。落とし穴: ソート済みリストを使って独自のループを書き、最初か最後の項目を見落とすことです。組み込み機能で処理できる場合は、端のケースにも対応できることを確認して使いましょう。

2. 時間計算量。 ある解法ではAをループし、その中でmax(A[:i])を呼び出します。スライスとmaxはいずれも最大i個の要素を処理するため、合計はおよそN squaredを2で割ったステップ数、つまりO(N squared)です。代わりに最大値を順次更新すればO(N)になります。落とし穴: ループが1つあるだけでO(N)と判断することです。ループの中にスライス、合計、カウント、検索がないか確認しましょう。

3. どの入力で失敗するか。 課題: Aに含まれない最小の正の整数を返します。ある解法はmax(A) + 1を返します。A = [1, 2, 3]なら4を返すので正解です。A = [1, 3]なら4を返しますが、2が抜けているため答えは2です。A = [-3, -1]なら0を返しますが、答えは1です。落とし穴: うまくいくケースを1つ試しただけで終えることです。抜けがある場合、すべて負の値、許可されていれば空、要素が1つ、すべて同じ値、許可される最大値など、端のケースを意識して挙げましょう。

4. Nが最大100,000でも十分に速い解法。 大まかな目安として、このサイズならO(N)またはO(N log N)を目指しましょう。O(N squared)では約10 billionステップとなり、一般的な制限時間を大幅に超えてしまいます。落とし穴: 10個の要素でテストすることです。その程度のサイズでは、どの方法も瞬時に終わるように見えます。Nが大きくなるにつれて処理量がどう増えるか考えましょう。

5. 制約を読む。 値が最大1,000,000,000で、Nが100,000の場合、合計は100 trillionに達することがあります。Pythonの整数なら処理できますが、整数のサイズが固定されている言語ではオーバーフローします。落とし穴: 値の範囲を無視することです。値の範囲からは、オーバーフローの可能性や、カウント配列などの手法が使えるかどうかがわかります。

準備方法

1. まず案内を確認しましょう。 問題数、合計時間、使用できる言語を確認してください。これらは雇用主が決めるため、思い込みで判断しないようにしましょう。
2. よく知っている言語を1つ使いましょう。 リスト、辞書、セット、ソート、文字列メソッドを調べずに使えるようにしておきましょう。
3. コードを書く前に制限を確認しましょう。 問題に示された入力サイズと値の範囲から、必要な処理速度や重要なエッジケースがわかります。Codilityのレッスン問題も同様です（Codility）。
4. まず正しく解き、その後で速くしましょう。 最初に、シンプルで正しい解答を書きます。計算量がO(N squared)で、Nが100,000まで大きくなる場合は、累積合計、辞書、セット、ソートなどを使って計算量を減らせないか考えましょう。
5. エッジケースを自分で試しましょう。 問題の例は、ケースの1つにすぎません。許されていれば、空の入力、要素が1つの場合、すべて同じ値、負の値、最小値と最大値、最大のNを試してください。
6. よく使われるパターンを学びましょう。 累積和、スライディングウィンドウ、辞書を使ったカウント、2ポインター、先にソートする方法、シンプルな貪欲法は、短いアルゴリズム問題の多くで役立ちます。Codilityの無料レッスンで、問題の形式を確認できます（Codility）。
7. 時間を計って解答を書きましょう。 フル模擬テストでは、非公開ケースに対してコードを書いて実行します。自分でも問題を用意して同じように練習すると、時間内に書くことに慣れます。
8. 本番と同じペースで練習しましょう。 制限時間付きのフル模擬テストを受け、1つのタイマーで3問を解くことに慣れておきましょう。

一般的な採点方法

採点方法は各雇用主が設定します。 Codilityによると、各課題は固定された基準に基づいて自動採点されます（Codility）。どの結果を十分とするかは、雇用主ごとに決められています。共通の合格点はありません。

一般に報告されている基準の仕組みは次のとおりです。課題のスコアは、非公開の正確性テストと、多くのアルゴリズム課題では大規模な入力データを使った処理速度テストに基づいて算出され、課題ごとのパーセンテージとなり、その後テスト全体のスコアにまとめられます。小さな入力データでは正しくても、大きな入力データでは処理が遅すぎる解答は、速度の点数を失うことがあります。また、特殊なケースで失敗すると、正確性の点数の一部を失います。そのため、模擬テストでは「正しいか」と「十分に速いか」を分けて尋ねています。

練習スコアは、当サイト独自の問題のうち正解した数を課題ごとにまとめたものです。どこに重点を置けばよいかを確認できます。これは練習用のスコアであり、Codilityのスコアや雇用主による結果ではありません。また、合格するかどうかを予測するものでもありません。

よくある間違い

• 例だけを信じる。 課題の例は、非公開の多数のケースのうちの1つにすぎません。例を通過しても、ほとんどの得点を失うことがあります。
• Nを無視する。 正しいO(N squared)の解法でも、N = 100,000での性能チェックに失敗することがあります。まず制約を確認しましょう。
• ループ内に隠れた処理がある。 ループ内でリストに対してスライス、合計、件数のカウント、インデックスの検索、または"in"による検索を行うと、処理コストが増大します。
• 最後の項目を見落とす。 範囲の境界を1つ間違えたり、リストの末尾で終わる処理を書いたりするのは、よくある失敗です。最後のステップを手作業で追ってみましょう。
• 初期値が間違っている。 最大値を0から始めたり、最小値を根拠のない大きな数から始めたりすると、負の値や非常に大きな値で問題が起きます。最初の項目を初期値にしましょう。
• 課題が前提とする順序を変えてしまう。 ソートは便利ですが、答えが位置や「リストの最初の項目」に左右される場合には使えません。
• 1つの課題に時間を使い切る。 まずすべての課題に正しい解答を提出し、その後、時間に余裕があれば処理速度を改善しましょう。