問題を公開のあと、トラックバックやはてブでいろいろ回答や感想を見ました。
　ちゃんとしたコードが書ける人が何人もいることがわかり（まあそういう人がレスポンスを出しているので当たり前か）、一安心です。本当に世間のレベルがあの求人サイトの応募者のレベルだったら、マジで日本のソフトウェア産業は滅びると思っていたからな...

　コメントの中で特に気になったものいくつかについて書いてみます。

●「これは知識問題だ」という指摘
　過去に似たことをやっていれば有利、というのは確かにそうです。
　ただ、そういう予備知識がなくても普通に考えて実装するのに充分な時間として３時間という設定でした。というか、僕も今回の反応を見るまでA*というアルゴリズムは知らなかったよ！
　また、解答は単に正解が出力できるかではなく、「コードの質」も見てます。僕もこの世界は長いので、ある程度ボリュームのあるコードを見ればその人の実力はだいたいわかる。柔道の達人は帯の締め方を見るだけで相手の実力がわかる、というのと似たようなもの。

　なるべく事前知識の有無で結果が変わらないような出題にしたいとは最初から思ってはいたけれども、そうすると本当に無味乾燥なプログラムを書く問題になってしまって面白くないのであきらめました。
　本当はこういう感じで複数題やらせればいいのかもしれないけど、それは手間がかかりすぎるしで。

●「業務には必要ない」「これでプログラマの実力が測れるのか？」という指摘
　もちろんこれと同じアルゴリズムが仕事で必要になるとは思ってませんが、似たような思考力を要することはたくさんある。少なくとも僕の仕事では毎日そうです。
　あとこれは書き忘れていた気がするが、この実技試験はあくまで１次試験であって、これをクリアした人は論述試験と面接を経てはじめて採用です。だからコーディングだけで採用を決めているわけではないです。
　この問題ができたから優秀な人材とは限らないけれど、できない人は"ほぼ確実に"優秀ではない、のではないかと。

　大学入試の問題でもそうだけど、確かに受験勉強はくだらない知識がいろいろ必要にな上に、それは人間の価値とは大して結びつかない。でも、あの程度のことも満足にできないようでは、社会に出てから直面するもっと難しい問題には到底たちうちできないでしょう。
　だから、真の実力を測る問題ではないからといって、その問題に価値がないというわけではないのです。

　さて調子に乗って、口頭試験で使う用の問題の１つを公開します。分野としては数学だけど、こういう論理的思考が得意な人はデバッグ能力も高いと期待できるのではないかと思います。

　６人でミーティングをする。どの２人を取っても、初対面か会ったことがあるかのいずれかである。このとき、「互いに初対面の３人組」か「互いに会ったことのある３人組」のどちらかは存在することを証明せよ

　ちなみに元ネタは最近読んだ本です。
　気がつけば10秒でわかります。

2色以下と3色以上なんで自明ですね。

A*ご存じでなかったですか。うーん。。。

あとその最後の問題は、どの二人についても初対面か会ったことがあるかの何れかって、何の制約でもないですね。
その２つしかありえないでしょう。
ということは、互いに会ったことのない３組がいないなら、それはつまり、互いにあったことがある人間が４人組より多くいるということで、その中から適当な３組を選べばよく・・・以下略。
多少数学的にいうならば「鳩の巣原理による」といったところですか。

就職活動中なので、このくらいでいいのなら少し興味あるなあと思いました。もう遅いだろうけど・・・。

このビックマウス、俺の性格と似てる
オカジマさん、あなたO型ですね ?

> どの２人を取っても、初対面か会ったことがあるかのいずれかである

これ以外の人間関係ってある？

間違ってたら恥ずかしいけど。チャレンジします。

＞どの２人を取っても、初対面か会ったことがあるかのいずれかである

ということは、初対面３人、会ったことがある３人、という事にならないので、初対面ないし合ったことがあるのいづれかで３人組ができます。

面識ある人の面識ある人とは面識があるとは限らないので
単純な塗り分け問題では無理かなあと思い
グラフを描きながら３０分位考えて証明できました。おもしろいパズルでした。

探索問題は素養を見るものとすると、口頭試験では素質が分かりそうですね。
定石は知りませんが、六角形状に配置して任意の3点で三角形を作り、辺を2色で場合分けすると
必ずいずれかの三角形で3辺の色が一致するって感じでしょうか。

きっと定石があるのでしょうけど、、、答え？に辿り着くのに20秒程度かかってしまいました。

ある一人(Aとする)に着目して、その他5人のうち3人(BCDとする)以上が会ったことがあると仮定する。
もしBCDのうちいずれか会ったことがある組(BCとする)があるならば、ABCで互いに会ったことがある。
そうでなければ、BCDは互いに初対面。
もしAが会ったことがある人が2人以下であるとしたら、会ったことがある/ないを入れ替えて考えればOK。

2人の関係を赤・青の2色で考える(どちらが初対面かは言及しない)
命題が成り立たないように考えていくと
ABCの3者間の関係は赤2本と青1本になる(逆でも可)
ここではA-B,A-Cが赤、B-Cが青とする
DEFの関係のうち、青は必ず1本存在する(D-Eと仮定)
ADEの関係でA-D,A-Eのどちらかは必ず赤になる(A-Dと仮定)
ABDのうちA-B,A-Dは赤なのでB-Dは青。同様にACDのうちC-Dは青。
ここでBCDの3辺が全て青になってしまうので、必ず命題は成立する。
こんな感じでしょうかね。

2つ上の解法の方がスマートでしたね。

ラムゼー理論

6人はそれぞれ色がついており、同じ色の人は知り合い同士であるとする
色が3色以上ある場合は、別々の3色を選べば「互いに初対面の3人組」となる
2色以下の場合は、0-6、1-5、2-4、3-3と分かれるので「互いに会ったことのある3人組」が必ず存在する

なんか小難しい理屈捏ねてる人が多いけど、背理法で一発じゃないか

»論理とひらめき [okamoto7の日記]
http://okajima.air-nifty.com/b/2010/01/post-c7b3.html 「気がつけば10秒でわかる」ということと「論理的思考が得意」ということの関連が気になりました．以上です．[続きを読む]

»頭の体操 [Caleidoscopioの日記]
またまた「人生を書き換える者すらいた。」のエントリから http://okajima.air-nifty.com/b/2010/01/post-c7b3.html 　６人でミーティングをする。 どの２人を取っても、初対面か会ったことがあるかのいずれかである。 このとき、「互いに初対面の３人組」か「互いに会った...[続きを読む]