サマーインターン2011問題

岡野原 大輔

2011-07-27 20:20:01

今年のインターン2011の応募者には書類選考後に次の問題を解いてもらいました。

長さnの文字列中で出現回数が最大の文字をO(n)時間で答えるプログラムを書いてください。但し、出現回数が最大の文字の出現回数はn/2より大きいとします。
条件として、文字列を格納しているバッファは書き換え可能で文字列以外に利用できるバッファサイズはc log n bits (cは任意の定数)であり、文字種類数は可変(最大n)であるとします。

#これはオプション問題で、解けなくても選考としては問題ありませんでした。
#指摘を受けまして、バッファサイズの条件をきちんと書きました。計算量はlog nビットのRAMモデル(連続するlog nビットの操作は定数時間)で考えています。

例えば、単純に各文字毎に頻度を数えるのにはバッファサイズが定数ですので記録できませんし、文字をソートするのもO(n log n)時間必要なので条件を満たしません。

これに対する正しい回答はこれまで3通り分かっています。
興味のある方は考えてみてください。

乱択アルゴリズム紹介(Color-Coding)

oxy
エンジニア

2011-07-26 20:13:08

吉田です。今まで数解に渡って乱択アルゴリズムを紹介してきました。そろそろ解析やアイデアがシンプルかつ結果が綺麗な乱択アルゴリズムは尽きてきたかと思っていましたが、もう一つとても素敵な手法が有るのを思い出しましたので解説します。Color Codingと呼ばれる手法です。
続きを読む »

PFIセミナーUSTREAM配信のお知らせ

祢次金 佑
エンジニア

2011-07-26 16:50:03

こんにちは。祢次金です。

PFIでは、毎週木曜に社内セミナーを開催しており、コンピュータサイエンスやITにかかわる様々な情報を社内で共有しています。また2009/2010年には、その様子をUSTREAMの弊社チャンネルを通じて度々ストリーミング配信し、より多くの方々にご覧頂こうという試みも行って参りました。

2011年8月より、本セミナーのストリーミング配信を再開致します。次回、および次々回の放映予定は以下のようになっております。

  • 2011年8月4日 19:10-20:00(予定) 発表者: 西川徹 タイトル: 未定
  • 2011年8月11日 19:10-20:00(予定) 発表者: 西鳥羽二郎 タイトル: 未定

セミナーに関するアナウンスは本ブログの他、弊社公式Twitterアカウントにてハッシュタグ#pfiseminarでもお知らせしていきます。また、セミナーの開催時間や内容は急遽変更になることがございますが、その際も公式アカウントよりアナウンスを行っていきます。

STL風に使えるマップ型コンテナの紹介と性能比較

preferred

2011-07-20 09:47:36

最近スマートフォンに乗り換えました。徳永です。

C++は世に数あるプログラミング言語の中では比較的メモリを食わない方ですが、それでもメモリ使用量が問題となる場合はあります。そのような場合の対処方法はいくつか有りますが、手軽に選択できる方法として、今日はSTLのmapやunordered_mapと同じ感じで使えるデータ構造をいくつか紹介したい思います。

続きを読む »

ユニークなクラウドソーシング・プロジェクト

祢次金 佑
エンジニア

2011-07-11 11:51:03

こんな暑い日はTDSに行きたい祢次金です。

機械には難しい大量のタスクを不特定多数の人間に依頼できる、クラウドソーシング。有名どころはAmazonのMechanical Turk(以下、Mturk)かと思いますが、最近では機械学習や自然言語処理の研究で、学習データへのアノテーションタスクに活用されることもあるそうです。

機械学習とは関係ありませんが、先日見たTEDのプレゼンテーションの中に、クラウドソーシングを利用した面白いプロジェクトがありましたので紹介したいと思います。

このプレゼンテーションは現在Google Creative Labに所属するAaron Koblin氏によるものです。プレゼン中の、クラウドソーシングが絡むプロジェクトから幾つかピックアップします。

続きを読む »

ソフトな推論Markov Logic Networkの紹介

海野 裕也
リサーチャー

2011-07-05 12:10:24

予約したもののインフォバーを手に入れられない海野です.
人間の高度な知的処理の一つが、推論処理です.今日はその推論を、述語論理と機械学習の組み合わせで模倣したMarkov Logic Networkという手法と、そのOSS実装であるAlchemyの紹介です.

続きを読む »