Python で 「ソフトウェアエンジニアが一時間で解くべき5つの問題」 に挑戦した話

ソフトウェアエンジニアが一時間で解くべき5つの問題

5つの問題のソースはこちら。英語です。

blog.svpino.com

 

5つの問題を和訳して下さっている記事はこちら。 

http://www.softantenna.com/wp/software/5-programming-problems/www.softantenna.com

 

 

5つの問題

ソースコードの前に、5つの問題文を引用しておきます。

 

問題1

forループ、whileループ、および再帰を使用して、リスト内の数字の合計を計算する3つの関数を記述せよ。

問題2

交互に要素を取ることで、2つのリストを結合する関数を記述せよ。例えば [a, b, c]と[1, 2, 3]という2つのリストを与えると、関数は [a, 1, b, 2, c, 3]を返す。

問題3

最初の100個のフィボナッチ数のリストを計算する関数を記述せよ。定義では、フィボナッチ数列の最初の2つの数字は0と1で、次の数は前の2つの合計となる。例えば最初の10個のフィボナッチ数列は、0, 1, 1, 2, 3, 5, 8, 13, 21, 34となる。

問題4

正の整数のリストを与えられたとき、数を並び替えて可能な最大数を返す関数を記述せよ。例えば、[50, 2, 1, 9]が与えられた時、95021が答えとなる(解答例)。

問題5

1,2,…,9の数をこの順序で、”+”、”-“、またはななにもせず結果が100となるあらゆる組合せを出力するプログラムを記述せよ。例えば、1 + 2 + 34 – 5 + 67 – 8 + 9 = 100となる(解答例)

(引用元:http://www.softantenna.com/wp/software/5-programming-problems/

 

 5つの問題はどれも「リストに対する基本的な操作の実装」を要求しています。
3問目までは非常に単純な問題で、4問目以降は少し難しいと感じました。
問題の詳細については上記のリンクを参照してください。

実装したのは二か月ほど前になりますが、なんとか50分で実装できました。
かなり手に馴染んでいる Python で実装したので当然といえば当然でしょうか。
もうちょっと早く出来るようになりたいな、というところです。

 

ソースコード

I tried "Five programming problems every Software ...

 

各問題を実装してみて

問1

問題は、「 for と while と再帰を用いてリスト内の数値の和を求める関数を実装せよ」ですが、for と while については関数を定義していません。
しかも今気づきましたがリスト内に数値以外のものが含まれるとエラー出そうです。
ソフトウェアエンジニア失格のようです。

 

問2

問題は、「二つのリストを交互に連結せよ」ですね。
最初にcombine_alternately() を実装したのですが、二つのリスト長が等しくない時に長い方のリストの末尾側が連結されませんでした。
そこで慌てて combine_alternately2() を実装しました。

問3

問題は、「フィボナッチ数列の第100項までのリストを計算せよ」です。
フィボナッチ数列を単純に再帰的に実装すると、関数呼び出しの回数が指数爆発して現実的な時間で計算できなくなるので注意しましょう。
たまたま大学の講義で習ったのを思い出して、再帰的な実装を回避できてよかったです。

 

問4

問題は、「正の整数のリストを与えられたとき、数を並び替えて可能な最大数を返す関数を記述せよ」です。
今回は数値の並べ方を全探索して、並び替えた際の最大数を計算しましたが、もっと良いアルゴリズムがありそうです。

 

問5

問題は、「1,2,…,9の数をこの順序で、”+”、”-“、またはななにもせず結果が100となるあらゆる組合せを出力するプログラムを記述せよ」です。
これも問4と同様に組み合わせを全探索して解きました。
問2で実装した combine_alternately2() が使えそうだったので使っています。
問2で「二つのリストのリスト長が異なる場合」のテストをしておいてよかったです。

 

感想

結果としては失格でしたが、自分の能力を振り返るのにいい機会になりました。
これからもがんばっていきます。