はじめに
前回Codilityでコーディングテストを受けたときの感想と、対策について簡単に書いたので、今回はPHPでテストを受けるときに知っておくと良さそうなポイントをまとめます。
Codilityはアルゴリズムとデータ構造の理解が問われます。特に時間計算量(O記法)を意識した最適なコードを意識することが重要です。
Codilityの問題で求められる力 
- 正確性 : 全てのテストケースを正しく解けるか
- 効率性 : 大きな入力サイズでも高速に処理できるか
- コードの可読性 : 可読性の高いコードになっているか
Codilityでは、提出後に受験者のコードの入力過程が確認できます。そのため、AIで生成したコードをそのままコピペした場合、簡単に判別可能です...
コーディングテストで気をつけること 
1. 時間計算量を意識する
O(n^2)のような時間のかかるアルゴリズムだと、大きいデータセットでは処理に時間がかかり、タイムアウトになってスコアが低なりがちです。
-
O(n)やO(n log n)になるように意識する - ループのネストが深くならないようにする
- 無駄な計算を省く (事前に配列をセット化するなど..)
// 配列$arrに重複する要素がある場合trueを返す処理
// ex. $arr = [3, 2, 9, 5, 6, 8, 2]
// => return true (重複する要素 2)
// 非効率な方法（O(n^2)）
function hasDuplicateSlow($arr) {
for ($i = 0; $i < count($arr); $i++) {
for ($j = $i + 1; $j < count($arr); $j++) {
if ($arr[$i] == $arr[$j]) {
return true;
}
}
}
return false;
}
// 効率的な方法（O(n log n)）
function hasDuplicateFast($arr) {
sort($arr); // O(n log n)
for ($i = 0; $i < count($arr) - 1; $i++) {
if ($arr[$i] == $arr[$i + 1]) {
return true;
}
}
return false;
}
2. 組み込み関数を利用する
PHPには便利な組み込み関数が用意されているので、これらを活用しましょう！
| 操作 | 関数 | 計算量 |
|---|---|---|
| 配列の要素をユニークにする | array_unique($arr) |
O(n) |
| 配列をセット(辞書型)に変換 | array_flip($arr) |
O(n) |
| 文字列の中に要素があるか確認 | in_array($value, $arr) |
O(n) |
| 配列内に要素が存在するか確認 | isset($arr[$key]) |
O(1) |
| 文字列を分割する | explode($delimiter, $string) |
O(n) |
3. ハッシュセットを活用する
連続する数字の最大長を求める問題では、ハッシュセットを活用するとO(n)で解くことができます。
// 最長の連続部分列の長さを求める
// ex. $arr = [100, 101, 102, 103, 104, 4, 200, 1, 3, 2]
// => return 5 (100, 101, 102, 103, 104)
function longestConsecutive($arr) {
$set = array_flip($arr);
$maxLength = 0;
foreach ($arr as $num) {
if (!isset($set[$num - 1])) {
$currentNum = $num;
$currentLength = 1;
while (isset($set[$currentNum + 1])) {
$currentNum++;
$currentLength++;
}
$maxLength = max($maxLength, $currentLength);
}
}
return $maxLength;
}
まとめ
以下のポイントを押さえておくと、スコアアップにつながります。
O(n log n) 以下の解法を探す
PHPの組み込み関数を活用する
isset($arr[$key])やarray_flip()で高速検索
次回は注意点についてまとめていきたいと思います。
参考になれば幸いです