3が解けなくて悔しかったので復習してみた。問題は要約するとN個のノードからなる有効グラフが渡された時にステップ数Lからなる経路の数が多項式P(L)で表されるか判別するプログラムを書くというのが問題です。本番では英語だし若干複雑なので理解するのに若干時間がかかりましたが...。入力値は個々のエッジを表すYとNの文字の羅列が以下のようにStringのArrayとして渡される。配列長と文字数はグラフの頂点の数と同じです。String[]{"NYN","NNY","YNN"};また、出力は多項式解が存在する場合には"Bounded"、存在しない場合には"Unbounded"をリターンするだけです。この問題は本番時にはコード以前にそもそもどういうアルゴリズムにすれば解けるのかが思いつきませんでした。終了後に以下のようにホワイトボードを使って精査したらやっとひらめいた。Polynomial(多項式解なし)でPがPolynomial(多項式解あり)を表しています。循環して自分に戻ってくるような経路を二つ以上もつノードがある場合に多項式解がなくなるようです。赤のラインで循環を示しているのですが、このラインが一つのノードから2つ以上出ている場合に多項式解がなくなります。N)乗」になるはずです。いう訳でMが1の場合には多項式解、Mが2以上の時には多項式では解けないはず。ルールさえ分かってしまえばコードはこんな感じで簡単に書けました。単純に一つ一つのノードをイテレートして循環が2つ以上ないか確認するだけです。3に費やせる時間は30分程度しかありません。本番でこのレベルの問題がでたらかなりラッキーじゃないと時間内に解ける気がしませんね。2を片付けることを目標とするか。忘れかけたJavaをググりながら書いているので、この辺りのTipsが身に付けば早く解けるようになってもう少しスコアがあがるはず。Labというイギリスのケンブリッジにあるスタートアップ企業でプロジェクトマネジメントやシステム設計から開発までしています。2007年に新卒でJPモルガン証券に入社し債券リサーチやリスク管理システムの開発に携わる。2012年4月からグリーでSNSアプリやMessengerアプリの開発に従事。2013年8月より現職。