2014-03-15

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

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

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

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}$$

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

目的が決まっていないとコーディングテストの問題を考えるのは難しいが、目的が「足切り」となるとどういった問題が良いのだろう。足切りチェックのために10分も使うのは勿体無いし、すぐに判断できて簡潔な物。コーディングテストじゃないけど、事前にその人のコードを読んでおく、というのが一番楽そうだ。

追記

エントリ公開してから思ったのだが、面接で重要なのは、書いているコードの意図をちゃんと聴き出せる事かなと。「方程式を解いて一般項が出せたので、このコードでいけます」と「テストファーストで開発を行なうために、一般項をそのまま実装した物をテストコードで使います」では全く違う。となるとこのレベルの問題でも十分コミュニケーションは取れる。エラー処理の有無、読み易さ、メモリ使用量、入力値の想定 etc... 。手書きよりも解答の幅が広がりそうな端末持ち込みライブコーディング面接、一度やってみたい。
計算機プログラムの構造と解釈計算機プログラムの構造と解釈
ジェラルド・ジェイ サスマン,ジュリー サスマン,ハロルド エイブルソン,Gerald Jay Sussman,Julie Sussman,Harold Abelson,和田 英一

ピアソンエデュケーション
売り上げランキング : 100220

Amazonで詳しく見る by AZlink

2014-02-16

山城とお別れをした

昨日はymsr送別会、彼と親しかった面々とLTや花火で盛大に山城先生とお別れをしてきた。

人間は死ぬ

身近な友人が死ぬというのは人生初めての経験だった。送別会は悲しい一方で最高に楽しかったのは事実で、印象的だったのは参加者がくちぐちに「気持ちに区切りがついた」と言っていた事だ。自分は一昨日まで葬儀の存在意義がわからず、葬式など必要無いと考えていたのだが、それは死者のためでは無く、生き残った人々のためにあるというのが理解できた。弔いの儀式は人類が古くに編み出した文化的な行為であると。

Bye Bye Yamashiro.

この様なバカ騒ぎをしながら氏を偲ぶのはjava-jaに必要な儀式なのだ。

俺と山城

彼とは職場が一緒になった事は無いが、java-ja.jsというイベントを一緒にやったりしていた。歯に衣を着せぬ物言いをしてくれる貴重な友人でもあった。

最後にちゃんと話をしたのは、同じビルで働いていた時に、職場の近くでランチをした時だ。彼は「Google AnalyticsをGoogleアナルティックスと言い間違えないのは難しい」等と下ネタばかり展開したあげく、「同僚(キラキラ女子)がこない様な店でメシが食いたい、この店は霊圧を感じる。リラックスできない。」と主張しており、この人はなんでサイバーエージェントに転職したのかなと疑問に思ったのを覚えている。

その後、渋谷のキラキラ女子がこない店で一緒にランチを食うという約束が果せなかったのが今でも心残りだ。

2014-01-30

UIWebViewのスクロール減速率の初期値がUIScrollViewDecelerationRateNormalでは無いのは何故か

iOSのUIWebViewのスクロールの減速率について。人に説明していると何故かややこしい話になってしまうのは初期値がノーマルじゃないせいな気がした。

UIWebViewの慣性スクロールの減速率を決める _webview.scrollView.decelerationRateの値だが、初期値は UIScrollViewDecelerationRateFast (以降RateFastと表記)になっている。これはUITableView等が 
UIScrollViewDecelerationRateNormal (以降RateNormalと表記)となっているのと違って、より早く減速するためスクロールして指を離した後に進む距離が短かい。変更するには
_webview.scrollView.decelerationRate = UIScrollViewDecelerationRateNormal;
とすれば良いが、これはWebViewの内容によって使い分けるのが良いだろう。一覧リストの様に、目的の物が見つかるまでスクロールし続ける画面であれば、よりスムーズにスクロールできる RateNormal 。記事を読ませるような画面であれば、1画面分づつスクロールできれば良いので RateFast といった具合に。

decelerationRateの型はCGFloatなので任意の実数をセットできそうだが、0.1等をセットしても無視されてしまう。ドキュメントにある様に UIScrollViewDecelerationRateNormal と UIScrollViewDecelerationRateFast しか効果が無い。

ちなみにfacebookアプリで外部リンクを踏んだ時のUIWebViewは RateNormal で、SmartNewsだと RateFast になってる模様。どちらも違和感を感じないので、Webの記事を読む時はどちらでも気にならないのかも。

タイトルの問いに対する答えは、AppleはUIWebViewに表示するコンテンツはWebの記事が多いだろうという仮説でもって、記事が読みやすいようにスクロールがすぐに止まるようにしたのでは無いかと。

2014-01-19

瞑想システムのフィードバックはどうあるべきか

瞑想を日々の生活に取りいれる事にした。しかし一度も瞑想をした事が無いため、どのようにして瞑想状態に入るか、また瞑想状態に入ったかどうかを判断する方法がわからない。まずはそこからである。

瞑想のやり方はWebを検索するといくらでも見つかるので、それらを参考にする。そして瞑想の計測方法だが、幸い手元に脳波ヘッドセットのEPOC neuroheadsetと開発者SDKがあるので、これを使う。コードを書くまでもなく欲しい物そのものである Meditation という値が付属ツールで表示できる。

上のスクリーンショットは瞑想に初めて挑戦した時の物、Meditaionの値が平常時と同じ = つまり失敗しているのがわかる。瞑想の修行を積む必要がある様だ。

しかし、瞑想に入ろうとしている際にこの Meditation のグラフに目をやると、同時に Instantaneous Excitement の値が跳ね上がり、所謂雑念に気を取られてしまうのがわかる。瞑想できているかどうかを気にした時点で負けかもしれない。なんらかの方法で瞑想状態のフィードバックを送るとしても、それに気をとられないような工夫が必要だろう。
既にある特許で瞑想装置(ミサワホーム株式会社. 瞑想装置. 特開平5-253302. 1993-10-05)があるが、これは背もたれ後方に配置した照明がアルファ波によって変化するとある。製品化されたかは不明だが、今ならhueを使えば簡単に実現できそうだ。

ミサワホーム株式会社. 瞑想装置. 特許公開平05-253302 より

とりあえず今はリアルタイムでフィードバックするのでは無く、Meditation の値の経過を後で参照できれば良いのでGrowthlForecastに投げるコードを書くとする。

2014-01-18

vim-python-pep8-indentプラグインで幸福実現した

Pythonのコーディングスタイルチェックにはflake8を使っていたのだが、インデントルールの次の二つは守れないでいた。
E126 continuation line over-indented for hanging indent
E128 continuation line under-indented for visual indent
具体的にはvimのインデント(Visualモードで範囲選択して = )だとpep8のインデントルールになってくれないので、ignore = E128,E126 していた。

そこで、@seizansに教えてもらった vim-python-pep8-indent を入れたらvimのインデントがpep8準拠になり、ほぼノーコストでpep8対応が完了できるようになった。これは良い。

.vimrcの記述は次の通りにした。
" flake8
NeoBundleLazy 'hynek/vim-python-pep8-indent', {
    \ "autoload": {"insert": 1, "filetypes": ["python", "python3", "djangohtml"]}}