オットセイの経営日誌

データサイエンス系ベンチャーを経営してます。経営のこと、趣味のことつぶやきます。

LeetCodeのすヽめ ~フィボナッチ数列を例に~

LeetCode

唐突ですが、私のマイブームを紹介します。

leetcode.com

LeetCodeという、コーディングの問題集的サイトです。
最近はここで毎日問題を解いているんですが、せっかくなら何かしらアウトプットした方がペースメーカーにもなると思い、ブログ記事にします。

LeetCodeでは、エンジニアの面接で行われるCoding Interviewで実際に出題された問題が掲載されているそうです。
実際にGoogle等のCoding Interviewを受けた人の話では、全く同じ問題は出ないが、LeetCodeをやっておけば解ける問題が出た、とのことでした。
難易度のレベルがEasy/Medium/Hardとあり、C/Java/Python/Rubyなど多くの言語に対応しています。
各問題にDiscussionページが設けられ、他のユーザーの解法を見て勉強できます。
一部問題には公式のSolutionページもあります（無料会員と有料会員で見られる範囲が異なります）。

ビジネスパーソンの方々、なんだエンジニアの話か、と思うなかれ。
特に小中高校時代に算数が得意だった方にとっては、なかなか面白いサイトだと思います。
これを機会にコーディングデビューしてみては？と思うくらい。

例えば以下の問題。

https://leetcode.com/problems/climbing-stairs/

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

階段を上っていて、１段ずつないしは１段飛ばしでしか上れないとしたとき、n段目まで上る方法はいくつある？という問題です。
こんな問題、どこかで聞いたことありませんか？


n段目まで上るには、n-1段目から１段上るか、n-2段目から１段飛ばしで上るかのどちらかになります。
つまり、n段目までの上り方の数を f(n)とすると、 f(n)=f(n-1)+f(n-2)になるわけです。
「フィボナッチ数列」という言葉を聞いたことはありませんか？「前の２つの数を加えると次の数になる」という数列で、まさにそれにあたるわけです。

これをコードで書くと、以下のようになります。

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        elif n == 2:
            return 2
        else:
            i = 3; a = 1; b = 2
            while i < n:
                a, b = b, a+b
                i += 1
            return a+b

もっと簡単に書くと以下の通り。

class Solution:
    def climbStairs(self, n: int) -> int:
        a = b = 1
        for _ in range(n):
            a, b = b, a + b
        return a

エンジニア目線では、LeetCodeは処理時間とメモリ使用量について、計算量オーダー（あるアルゴリズムを使った演算の性能を表す指標）も示してくれるので助かります。
ただsubmitごとに値が大きく変わっていて（特に処理時間）、LeetCode側のサーバー側がどれだけ混んでるかに依っていそうなので、あくまで参考値ですが。

最後に、私がLeetCodeを知るきっかけになったTweetを紹介します。

とある理由でKaggleを注視しているんですが、なかなか敷居が高いですし、世の中の大半を占めるであろう、機械学習活用度 Low ~ Middle 層では、ここまでのスキルが必要か？と思っていました。
そう思っていたところでこのTweetを見て、我が意を得たり、と思ったわけです。

さて、このLeetCodeについてですが、今後は不定期ながらもこのBlogやQiita上で面白いと思った問題を取り上げていこうと思います。

~以下余談~

LeetCodeのもとになっているCoding Interviewですが、、日本では全くと言っていいほど行われていないそうですね。
今をときめく○ルカリのエンジニア面接に臨んだ米国大学卒の子（LeetCodeヘビーユーザー）が、「あなたの志望動機は〜」「強みは〜」など通り一遍の質問だけ聞かれて落とされ、納得いかない・・・と言ってました。
単純に評価できる人がいないということなんでしょうが、日本のITリテラシの低さの一端がまた見えてしまった気がします。