コーディングテスト - 実践編

>> 連載トップ > 前回のお話

コーディングテストであれ、次の面接の予定であれ、リクルーターは基本的にはこちらの予定を加味してアポを入れてくれる。毎度毎度予定を詰める段になると、「次のアポまでに予習と準備したいから二週間ぐらい空けるかな。」という発想である程度時間を開けるのだけれど、時間に余裕を持てば持つほどに、本番が近づいてきたときの緊張感とストレスもより一層大きくなる。

そんなこんなで、コーディングの練習は十日ほどで見切りをつけて、Amazon のコーディングテストを受けることにした。Leetcode.com の問題でだいたい Easy を１日３問で一週間。これでメインのトピック†を網羅した後、Medium を１日１問。それぐらいやると「もう十分だろう、もうやりたくない。」という気持ちで、テストから逃げるモチベーションから早くテストを終わらせたいモチベーションにシフトしていった。

コーディングテストではリクルーターが送ってくる専用のリンクにアクセスしてこれらの課題に取り組む。リンクは一週間で失効するので、自分の予定を加味してリクルーターにテストを発行してもらう。Amazon は myamcat.com というオンラインサービス††を使っている。テストを始める際にこのサイトは定期的にスクリーンショットをとる、タイピングを記録するなど、なかなか気持ち悪い要求をしてくる。これを許可しないとテストを受けられないのだがなんともスッキリしない。なんでも、こうしないと課題でズルをする人が後を絶たないからだそうだ。
テストは大体全部で２時間ほどで、コーディングの課題が二問と性格・行動適正診断がある。コーディングテストは全部で二問、合計で最大 90 分かけることが出来る。どちらの問題も「Amazon では、」と、一応問題をそれなりにカスタマイズしたような始まり方だった。一問目は以下のようなものだった。さて、これを読んでいるあなたは何が問われているかお分かりだろうか？

Amazon では、顧客第一をモットーの一つに掲げていて、商品を配達する際には最も早く商品が配達されなければなりません。出発地点、目標地点、通行不可能な道が与えられた場合に、最短経路を求めるプログラムを実装しなさい。経路情報は２次元配列として与えられます。

入力例
[
  ['s', '0', '0', '0'],
  ['0', '0', '1', '0'],
  ['0', '0', '1', 'g'],
]

出力
5

上の例では、s, g はそれぞれ出発地点、目的地点を表し、0 は通行可能な経路、1 は通行不可能な経路を表します。

問題の文章はもう少し説明が丁寧だったかもしれないが、まあ大筋は伝わるだろう。二次元のマップが与えられた場合の最短経路はどのようにして求められるだろうか？これを書いている僕の頭の中ではダイクストラ法という言葉が思い浮かんでいるが、それはこの問題にはオーバーキルだろう。この問題を実際に解いている際にはダイクストラ法のことなど思いもしなかったのだが、それはきっと事前練習のおかげで脳がよりコーディングチャレンジ仕様になっていたからかも知れない。では、どうすればよいかというと、模範解答は幅優先探索 (BFS) だろう。

木構造に関する知識、探索方法（幅優先(BFS)、深さ優先(DFS)）や、深さ優先探索の場合の処理の順番の違いなどは事前に習得していることが期待される知識だ。他にはリンクドリストや、ハッシュマップ、ハッシュテーブル等の特性、ソートアルゴリズムや再帰的な実装がよくテストされる。今回の課題では BFS を使って二次元配列の要素をどのように処理できるかを考える必要がある。

と、ここまで尤もらしいことを述べたが、実際には、この「２次元空間の最短距離」の問題は頻出問題の類なので、練習問題を多くこなした人なら大体みたことあるはずだし、課題に取り組む際にはそうであることが理想だと思う。そんな訳で実装の方法は例えばここで詳しく説明してあるので、ここでは割愛することにする。僕は見た瞬間に「あぁ BFS か。」と思ったので、どのようにしてそこにたどり着いたのかはうまく説明できない。きっと着想方法を説明したサイトも探せばあると思うので、それは読者の皆さんに委ねることにする。

二問目も同じような配送をテーマにした２次元配列を扱う問題だった。動的計画法を使うナップサック問題系の課題だったような気がするが、残念ながら忘れてしまった。

メインのコーディングが終わると、自身の解法に関する記述課題になる。要は自分の実装を評価するわけだが、ここで大切なのは時間とメモリに関する計算量をきちんと記述すること。O記法（ビッグオーノーテーション）を使って、入力のサイズが変わると、計算時間とメモリ消費量にどのような影響が出るのかを評価する。

例えば、上に挙げた最短経路の問題を BFS で解いた場合を考えると、目的地が見つかるまでノードを一つずつ処理していくので、計算にかかる時間は（最悪の場合で）与えられたマップのサイズに比例する。n, m をマップの辺の大きさとすると、O(n*m) となる。メモリ消費量は、辺の長さのうち、短い方に比例するので O(min(m, n)) となる。

頻出アルゴリズムの時間及びメモリ消費量の性質は覚えておくと、問題を解くときの判断の助けになる。忘れてしまった場合はさっと検索すればすぐに出てくる。

さて最後は性格診断である。これは選択問題形式で、日本の就活でよく見る SPI 等とよく似ている。「時間の余裕がない時でも落ち着いて対応できるか」などという実質一択問題がたくさんある。Amazon の場合はリーダーシップ理念というものを公に掲げているので、解答に困ったら、それに即したものを選べばよい。
全てに答えて、提出ボタンを押すとテスト完了となり、リクルーターに結果が送られる。リクルーターは結果を基に次のステップをアレンジする。

第八話「不意打ち」に続く。

脚注

トピック

• Data Structure
  • Array
  • Tree Structure
    • Binary Tree Seach
    • Trie
  • Stack / Queue
    • FIFO / FILO
    • Priority Queue
  • Hash Table
    • Bucket Implementation
  • Linked List
  • Graph
    • Directed acyclic graph
    • Adjacency Matrix
    • Adjacency List
• Algorithms
  • Sort
    • Quick Sort
    • Merge Sort
  • Iteration vs Recursion
  • Dynamic Programming
  • String Hashing
    • Palindrome Detection
• Others
  • Big O notation
  • Stack vs Heap

UI

二年ほど前にもこのテストを受けたことがあるのだけれど、インターフェースが中々分かりにくくて、その時は次の課題に進むボタンだと思って押したボタンが提出ボタンだったことがある。その結果はお察し。