エンジニアの採用面接におけるコーディングテストとフィボナッチ数列

ソフトウェア開発者採用面接のコーディングテストについて。最低限のコーディング能力があるかどうかを見極めるのに、フィボナッチ数を求める関数が出題される事がある。というか自分も出題した事がある。

ホワイトボードに書く形式だと、どうしても行数の少ない実装になってしまうが。手元の端末で自由に書いて良いとなれば、いろいろな解法が出てきて、想定していないコミュニケーションが生まれるかもしれない。最近は専ら採用する側になってしまったのだが、とりあえず自分ならどう書くかなと列挙してみた。使った環境はIPython Notebookである。

定義

• f(0) = 0
• f(1) = 1
• f(n) = f(n-1) + f(n-2)

1. 再帰を使うもの

ナイーブな実装。見たまんまで理解しやすい。まあ計算量がアレだよねーという奴

In [53]:

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

map(fib, range(15))

Out[53]:

$$\begin{bmatrix}0, & 1, & 1, & 2, & 3, & 5, & 8, & 13, & 21, & 34, & 55, & 89, & 144, & 233, & 377\end{bmatrix}$$

2. forループ

計算オーダーがO(n)になった。自分が書くなら上を書いてから、追記でこちらも書くかな。

In [54]:

def fib(n):
    a, b = 0, 1
    for i in xrange(n):
        a, b = b, a + b
    return a

map(fib, range(15))

Out[54]:

$$\begin{bmatrix}0, & 1, & 1, & 2, & 3, & 5, & 8, & 13, & 21, & 34, & 55, & 89, & 144, & 233, & 377\end{bmatrix}$$

3. 行列と内積を使う

numpy使いはこう解くかもしれない。

In [55]:

from numpy import array

def fib(n):
    A = array([[0,1],[1,1]])
    tmp = array([0,1])
    for i in xrange(n):
        tmp = tmp.dot(A)
    return tmp[0]

map(fib, range(15))

Out[55]:

$$\begin{bmatrix}0, & 1, & 1, & 2, & 3, & 5, & 8, & 13, & 21, & 34, & 55, & 89, & 144, & 233, & 377\end{bmatrix}$$

4. 逐次平方して計算量O(log₂n)で解く

SICPでやった奴だ!! だが、面接の場でこのコードを捻り出せる自信は無い。
速く動作する実装を求められたら10分ぐらい時間をもらって導き出すかも。

In [56]:

def fib(n):
    a, b = 1, 0
    p, q = 0, 1

    rest = n
    while rest > 0:
        if rest % 2 == 0:
            p, q = p**2 + q**2, q**2 + 2*p*q
            rest /= 2
        else:
            a, b = b*q + a*q + a*p, a*q + b*p
            rest -= 1
    return b

map(fib, range(15))

Out[56]:

$$\begin{bmatrix}0, & 1, & 1, & 2, & 3, & 5, & 8, & 13, & 21, & 34, & 55, & 89, & 144, & 233, & 377\end{bmatrix}$$

5. 一般項を使って解く

一般項を記憶している場合のみ可能とも言える。ただし、計算機に優しくない見た目の通り、fib(2000)とやるとOverflowErrorになってしまう。
プロダクション環境に突っ込むとしたらこのコード使いますか?? みたいな話になりそう。

In [57]:

def fib(n):
    return int(1/5**0.5*(((1+5**0.5)/2)**n - ((1-5**0.5)/2)**n))

map(fib, range(15))

Out[57]:

$$\begin{bmatrix}0, & 1, & 1, & 2, & 3, & 5, & 8, & 13, & 21, & 34, & 55, & 89, & 144, & 233, & 377\end{bmatrix}$$

6. 方程式 f(n) - f(n-1) - f(n-2) = 0 をf(n)について解く

面接で緊張して頭が真っ白になってしまった場合は、数学的な宣言をそのまま利用すれば良い

In [102]:

%load_ext sympy.interactive.ipythonprinting
import sympy as sym
from sympy.abc import n

In [127]:

# 関数fibを定義
fib = sym.Function('fib(n)')

# fib(n) = fib(n-1) + fib(n-2) を変形して
# fib(n) - fib(n-1) - fib(n-2) = 0 の方程式とする
f = fib(n) - fib(n-1) - fib(n-2)

# fib(0) -> 0, fib(1) -> 1 である事を利用して fib(n) について解く
fib_term = sym.rsolve(f, fib(n), {fib(0):0, fib(1):1})
sym.Eq(fib, fib_term)

Out[127]:

$$fib(n) = \frac{1}{5} \sqrt{5} \left(\frac{1}{2} + \frac{1}{2} \sqrt{5}\right)^{n} - \frac{1}{5} \sqrt{5} \left(- \frac{1}{2} \sqrt{5} + \frac{1}{2}\right)^{n}$$

解けた。5.と同じfib(n)の一般項が導出できたので、あとは実行するだけ。

In [125]:

map((lambda i: int(fib_term.evalf(subs={n:i}))), range(15))

Out[125]:

$$\begin{bmatrix}0, & 1, & 1, & 2, & 3, & 5, & 8, & 13, & 21, & 34, & 55, & 89, & 144, & 233, & 377\end{bmatrix}$$

最後のは極端だが、方程式を解くという行為を数値計算ライブラリに丸投げすると、プログラミングの特徴である平叙文的な記述を命令文的な記述に変換するという行為がどこにも無いという事態になる。メモ化すると計算量がうんたらとか、末尾最適化がほげほげというコミュニケーションが取りたい場合は、そういった誘導が必要だろう。

最近は面接の前にその人のコードが読める事も増えてきて、最低限の力を見極めるのならそれが一番楽なんだけど、せっかくコーディングテストやるなら解法がいろいろあってコミュニケーションの選択肢が多くなるようにしたい。エラー処理の有無、読み易さ、メモリ使用量、入力値の想定 etc... 。手書きよりも解答の幅が広がりそうな端末持ち込みライブコーディング面接、一度やってみたい。

計算機プログラムの構造と解釈 ジェラルド・ジェイ サスマン,ジュリー サスマン,ハロルド エイブルソン,Gerald Jay Sussman,Julie Sussman,Harold Abelson,和田 英一 ピアソンエデュケーション 売り上げランキング : 100220 Amazonで詳しく見る by AZlink