コーディングテスト - 練習編

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

最初のヤマであるマネージャーとの電話は驚くほどつつがなく終わったので、その次の日曜日に、Amazon の最初のステップとなったコーディングテストを行った。

コーディングテストには、きちんと作動するコードが要求される。ブラウザーでテストサービスにアクセスし、専用のエディター上で要求されるコードを実装する。エディターにはテスト機能が付いていて、これを使うと前もって決められた入力パターンを試していき、正しい出力が得られるかどうかを確認する。要はユニットテストである。もしも正しい出力が得られない場合は、時間が許す限りコードを修正することができる。入力テストのパターンには大体エッジケース（特別な例外的な処理が要求される場合）や、入力データのサイズがとても大きい場合等が含まれていて（効率の悪い方法であれば時間内に処理が完了しないので不正解扱いになる）、これらを正しく処理できることが合格の要件になる。

このような課題はソフトウェアエンジニアの分野ではよくあるもので、インターネット上には練習に使えるサイトがたくさんある。リクルーターによってはそのようなサイトのリストと練習する際に気をつけることのリストなんかを一緒に送っくれて、受験者にどのように対策をすればいいか助言してくれる。というか、リクルーターの仕事はなるべく多くの採用者を出すことなので、大体のリクルーターがこのような対策用の資料を送ってくれる。例えば Facebook は専用ページで詳しい流れを説明してる。（Google は脚注参照）だからテストや面接が始まって予期していなかったということはまずない。

練習用サイトでよく名前が挙がる中†では leetcode.com が使いやすいと思う。日常的にコーディングを行なっている人は、練習する際には要求されていることが普段のエンジニアリングと違うということを意識するとよいだろう。エンジニアリングで重要なことは必ずしも課題を説く上では重要ではない。（メンテのしやすさとか。）僕は leetcode.com でまず Easy を解きながら、一通りのトピックをカバーして、その後 Medium を毎日一問一週間ほど続けた。この時、大事なのはコードを書き始める前にアルゴリズムの全体のプロセスをノートに書きだして整理しておくことだ。これは後のオンサイトインタビューの練習にも通じる。

例えば、38 Count and Say を見てみよう。

The count-and-say sequence is the sequence of integers with the first five terms as following:
1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.
Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence.

与えられた文字列を「何が」「何回」繰り返されるかによって書き直す。この処理を n 回繰り返したら得られる文字列を出力せよという問題だ。どのようにアプローチすればよいだろうか？

まず問題を分析して、必要なコンポーネントを洗い出そう。この問題は Easy なだけあって、全体の流れは簡単だ。まず処理する文字列を “1” で初期化し、与えられた n 回だけ書き換え処理を実行すれば良い。この処理はメインの関数とは別の補助の関数として実行すると良さそうだ。

では、どのようにして書き換え処理を実装すれば良いだろうか？まず、ルールを細かく見てコードに直して組み合わせでみよう。

まず、文字列全体の書き換えは、部分部分を独立に書き換える処理の組み合わせでできていることが分かる。

では、どうやって全体の文字列を個別の部分に分割すれば良いだろうか？しばらく図を眺めていると、これは単純に同じ文字の集合で分割すれば良いことがわかる。なるほど、与えられた文字列を前から順番に見ていき、次の文字が前と違っていればそこが分割箇所となるようだ。

ここの分割の部分がこの問題の中で最も複雑なので、先に取り出して実装してみよう。以下では Python の Generator 構文を使って分割を実装してみる。多分、普通に初見でこの問題を説く際には Generator を使わずに、全てを一つの関数で処理するだろう。実際僕もそうしたが、ここでは問題を細部まで分割して分析すること主眼におくのでこのような形をとった。関数を分けない場合の回答も後に述べる。

def _split(string):
    char, count = string[0], 1
    for c in string[1:]:
        if char == c:
            count += 1
        else:
            yield char, count
            char, count = c, 1
    yield char, count

この分割ではまず初めに、取り出す文字 char とその文字が連続して出現する回数 count を、与えられた文字列 の最初の文字 string[0] と 1 で初期化する。そして、順番に残りの文字を確認していき、もし同じ文字が見つかったら回数を 1 増やし、違う文字が見つかった場合は、そこまでで分割が完了しているので、今保持している文字 char とその回数 count を放出する。分割ができれば、文字列変換のプロセスは簡単に以下のように書ける。

def _process(string):
    return_value = ''
    for char, count in _split(string):
        return_value += '%d%s' % (count, char)
    return return_value

分割された文字と回数をそのまま文字に変換して繋げるだけの簡単なロジックになる。あとはこれを課題の規定する入出力の形式に揃えるだけで良い。課題では入力は n すなわち変換処理を実行する回数で、文字列の初期値は ‘1’ なので、

def countAndSay(n):
    string = '1'
    for _ in range(n-1):
        string = _process(string)
    return string

となる。 先述した通り、普通に課題に説く場合は Generator を使わないで、新しい文字列の生成と、それに必要な文字の分割、数え上げを一緒に実行するだろう。その場合の実装は以下のようになる。

def _process(string):
    return_value = ''
    char, count = string[0], 1
    for c in string[1:]:
        if char == c:
            count += 1
        else:
            return_value += '%d%s' % (count, char)
            char, count = c, 1
    return_value += '%d%s' % (count, char)
    return return_value

全体のコードをまとめると以下のようになる。

def _split(string):
    char, count = string[0], 1
    for c in string[1:]:
        if char == c:
            count += 1
        else:
            yield char, count
            char, count = c, 1
    yield char, count


def _process(string):
    return_value = ''
    for char, count in _split(string):
        return_value += '%d%s' % (count, char)
    return return_value


class Solution:
    def countAndSay(self, n: int) -> str:
        string = '1'
        for _ in range(n-1):
            string = _process(string)
        return string

このようにして、問題を分析し、1. なるべく簡単な基本要素を定義し、2. 基本要素を組み合わせてフロー全体を組み立てることが出来るとコーディングテストはうまくいく。練習初めは実装を行わなくても、よいだろう。問題を見て、一晩かけて解法を考えて翌日取り掛かってもいい。文法やデータ構造の知識も大切だが、練習する際に大事なのは分析することなのだ。

第七話「コーディングテスト - 実践編」に続く。

脚注

Google

Google は全部 YouTube ビデオになっている。

Prep Videos:
How to: Prepare for a Google Engineering Interview
How to: Work at Google — Example Coding/Engineering Interview
Interview tips from Google Software Engineers

More general about hiring at Google:
How to: Work at Google — How We Hire
Ask a Google Engineer — How to Work at Google: Prospective Employee Qualities

練習サイト

Google リクルーターが送ってくれたリンク集。

Websites recommended by Google Software Engineers:
Top Coder: https://www.topcoder.com/
(If you can handle the DIV I 250 level questions on TopCoder getting around 220+, then you are in good shape.)
HackerRank: https://www.hackerrank.com/
Project Euler: https://projecteuler.net/
LeetCode: https://leetcode.com
500 Data Structures and Algorithms practice problems/solutions: Quora
Competitive Programmer's Handbook: https://cses.fi/book/index.html