Google予習

参考のために『“Greetings from Google” (Googleの面接)』を読んでみる。

ま、最初のPhone Interviewですので、人事的な内容だろうと思い、特に準備もしないで臨みました。内容は、職の説明から始まり、私が現在転職活動をしているか？どの勤務地に興味があるか？など聞かれました。その後、自分のスキルについて自己採点しろということで、C, C++, Java, SQLなど全部で10項目くらいを0〜10のどのレベルかを問われました。Googleで働いている技術者のレベルは大体4〜7のレベルだと言うので、ま、コメントを加えながら適当に答えました。

CとかC++の技能というものはあるのだろうか。C/C++は言語が簡素で標準ライブラリが乏しい。だから普通に使えていれば8くらいあってもいい。足りないとしたらアルゴリズムとか数学とかライブラリ（フレームワーク）類のスキルであってC/C++ではない。

JavaはC/C++と違って巨大なフレームワークがついていて、これの理解なしに「私はJavaができます」とは言えない。自分だとJDK 1.0とかのころしか知らないので2か3くらいだろうか。ただC/C++の知識があるからリファレンス片手にあれこれすることはできると思う。

SQLはほとんど使ったことがない。基礎知識はあるけど、1か2だろうか。0ではない。しかしこれからSQLってどうなのだろうか。直接SQLを叩くのってRuby on Railsとかでもやらないと聞いたけど、パフォーマンスを追求するといじるようになるのかな。あとNoSQLも流行っている。

その後、技術的な質問をしたいから、以下の3つのどれが自分にふさわしいものか選べといわれます。

• ソフトウェア技術
• システム管理
• データベース技術(だったかな？忘れた)

私はソフトウェア技術と答えました。すると、ソフトウェア技術関連の質問を3つすると言われました。

最初の質問は、◯◯◯ソートとはどういうもので、どれくらいの時間が掛かるものか？というものでした。学生の頃習ったのは思い出せますがアルゴリズムは忘れました。大体、ソートにも色々なアルゴリズムがあります。大学を卒業したばかりの人の方なら答えられるでしょうか。これは困りました。のっけからつまずくのも嫌なので、とにかく頭に浮かぶ限りそれっぽいのを説明しました。

ソートはずっとライブラリを使っているのであんまり覚えていない。復習をしておこう。

まず単純なバブルソート。n番目とn+1番目を比較して大きい方（小さい方）をn番目に持ってくる。これを何度も繰り返すとソートできる。実行時間はO(N^2)

選択ソート。一番大きい（小さい）のを先頭に持ってくる処理を繰り返す。実行時間はO(N^2)

クイックソート。ピボットを適当に選び配列を分割する。ピボットより大きい（小さい）ものが前に、小さい（大きい）ものを後ろになるように分割する。分割された配列をソートする。この過程で再帰が適用できる。

あとは挿入ソートなんかがあったっけ。あまり高速なイメージはないけどほぼソートされている配列に対して適用する場合には非常に高速なので一部の分野で人気である。

次の質問は「2の◯◯乗は何か？」というもので、いきなり簡単になりました。

Wolfram Alphaでも開いて待とう。

3つ目の質問は次の4つを速い順に並べろというものでした。

• ◯◯◯◯アクセス
• ◯◯◯◯スイッチ
• ◯◯◯◯シーク
• ◯◯◯◯リード

これはわからないなー。スイッチって何だ？コンテクストスイッチ？リードとどう比較するのか。

最後の質問は、巨大な配列があり、それらのどのビットが立っているかを調べる最速のアルゴリズムを説明しろ、というものでした。

これも適当に答えると、相手はそれが最速か？などと不満そうで、考え直して、別の解答をしましたが、それもダメでした。。

「どのビットが立っているかを調べる」の意味によるけど、たとえば6ビット目が1かどうかならANDして0と比較すればいい。問題はどのビットが立っているかわからず、たとえば「1,2,8,17ビット目が立っています」と判定する場合。1(0x01)でANDを取って0と比較、順次ビットシフトでところてんのように押し出してやればわかるが、最速かどうかはわからない。

巨大な配列の意味によるけどテーブルを使うといいかもしれない。8ビットは256パターンだから全てのパターンを列挙しておく。32ビットCPUならばもしかするとテーブルを4バイトまで大きくしてもいいかもしれない。

なおどのビットが立っているかではなく、立っているビット数を数えるアルゴリズムには見事な物がある。

int bitcount(long bits)
{
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}

IBMの人が1960年代に考えたらしい。すごい（・o・*）