PFIサマーインターン2011問題

PFIという検索エンジンのベンチャー企業でインターンシップの募集があったようです。その選考過程で次のような問題*1が出たそうです。

長さnの文字列中で出現回数が最大の文字をO(n)時間で答えるプログラムを書いてください。但し、出現回数が最大の文字の出現回数はn/2より大きいとします。

条件として、文字列を格納しているバッファは書き換え可能で文字列以外に利用できるバッファサイズはc log n bits（cは任意の定数）であり、文字種類数は可変（最大n）であるとします。

この問題が解けたので、解答を書いておきます。

#include <cassert>
#include <algorithm>
#include <string>

char PFI(std::string& s)
{
    assert(!s.empty());

    typedef std::string::iterator iterator;

    iterator const begin = s.begin();
    iterator const mid = begin + s.size()/2;

    std::nth_element(begin, mid, s.end());

    return *mid;
}

これが何をしているかというと、文字列の中央値を求めています。見つけたい文字が文字列の半分以上を占めているので、それでいいわけです。中央値を求めるのを実際に行っているのがstd::nth_elementで、ある範囲のうちm番目に小さいものをm番目に置く操作を行います。std::nth_elementは平均的には対象とする範囲の要素数に比例した時間しかかからないことが、C++の規格で定められています。また、std::nth_elementの典型的な実装はメモリの条件も満たしています。

*1:サマーインターン2011問題 : Preferred Research