修正版~Googleの入社試験(非公式)にチャレンジしてみた~

Googleの入社試験(非公式)にチャレンジしてみたで、チャレンジしたGoogleの入社試験(非公式)。
久しぶりに見直してみたら、間違ったソースコードだったので修正しました。

さらに、ソースを見ていると、長ったらしくてイライラしたので書き直すことにしてみました。

とりあえず、以下が問題文。

▼問題文

整数nが与えられたとき、0からnの間の全ての数を書くのに必要とされる「1」の数を返す関数があります。たとえば、『f(13)=6』になります。また、『f(1)=1』に注意。『f(n)=n』となるような、2番目に大きいnを求めなさい。

前回のソースは色々と無駄だらけなので、2番目に大きいnを探すだけに書き直してしまいます。


▼以下、問題にチャレンジ


とりあえず、まとめてソースを書いちゃいます。

class GoogleTest {
    private $anw;        // 1.答えを格納するプライベート変数

    /**
     * 答えを返す
     *
     * @param    $search     int    検索する値を整数値で指定
     * @param    $start      int    検索を開始する値を整数値で指定
     * @param    $cnt        int    検索を開始する値までに必要な$searchの数を整数値で指定
     * return    int    『f(n)=n』となるような、2番目に大きいnを返す
     */
    public function getAnw() {
        // 2.答えがセットされていない場合、nを求める。
        // 3.f(1)=1になる事は分かっているので、2から数える
        if(!$this->anw) $this->setAnw(2, 1);

        return $this->anw;
    }

    /**
     * 引数nの中にある「1」の数を返す
     *
     * @param    $n        int    検索を開始する値を整数値で指定
     * @param    $count    int    0から$nの間の全ての数を書くのに必要とされる「1」の数を整数値で指定
     */
    public function setAnw($n, $count) {
        $count += substr_count($n, 1);

        if($n == $count) {
            // 4.答えを変数に格納する。
            $this->anw = $n;
        } else {
            // 5.再帰でもう一度計算する
            $this->setAnw($n+1, $count);
        }
    }
}

$gT = new GoogleTest();
echo $gT->getAnw();

【ソースコードの説明】


ざっとソースを説明します。

1.まずは答えを格納する変数を用意します。

2.答えが変数に格納されていない場合、答えを求めます。

3.『f(1) = 1』となるのは分かっているので、2からカウントします。
この時、1を書くのに必要な1の数は1なので、第2引数には1を指定します。

(文字にするとややこしいですね。。。)

4.nを書くのに必要な1の数がnと等しくなった場合、答えを変数に格納します。

5.nを書くのに必要な1の数がnと等しくない場合、再帰処理を行います。

これで終了です。
前回より見やすいソースになったと思います(たぶん・・・)

このままじゃ、0からnの間の全ての数を書くのに必要とされる「1」の数がnと等しい2番目に大きいnしか求めれないのでダメダメな感じですけど・・・
とりあえず、ソースも短くなったし、実行時間も早くなったので、よしとしておきます><

『CakePHP2.0.1』がリリースされたんですね

いつの間にか『CakePHP2.0.1』がリリースされたんですね。
最近は仕様書ばっかり書いていたし、PHPが恋しくなってきたので少~しだけ触ってみることにしました。


(『CakePHP2.0.1』は、マルチバイト関係の問題があるらしいので2.0.1は使わずに次のリリースを待つか、最新の2.0ブランチを使うほうが良いみたいです。
詳しくは、【CakePHP2.0.1がリリースされましたが、ちょっと待ったほうがいい】cakephperの日記(CakePHP, MongoDB))


触ってみるにしても、何が変わったのかも良く分からないので、とりあえずCakePHP2.0のマニュアルを読んでみることに。
どうやらCakePHP2.Xは、PHP4は完全にサポート外、PHP5も5.2.6以上になったみたいです。
PHP4を使用してサイトを構築している人の為に、CakePHP1.3.Xの開発もしばらくは続くみたいですね。

ってな感じで、マニュアルを読み進めていくと、『2.0移行ガイド』なるものが。

ファイル名の命名規約がアンダースコアからキャメルケースに、ディレクトリ名の命名規約もキャメルケースになったんですね。
コンポーネントのスーパークラスも『Object』クラスから『Component』になったり、『Authコンポーネント』が書き直されてたり、テスト環境が『SimpleTest』から『PHPUnit』に変更になってたりと、結構な量の変更が。

まあ、今日は2.Xを触ってみたいだけので詳しくは後で見ることにして、実際に動かしてみることにします。

まずは、ダウンロード
いつものようにディレクトリを配置していき、いつものようにアクセス。

すると、いつもの見慣れたトップページが表示されました。
『Security.salt』や『Security.cipherSeed』の変更も1.Xと同じですね。
『/app/Config』に新しくできた『email.php』は、多分Eメールを送る新しいライブラリクラスに関わる設定なんだろうと思います。

ためしに、コントローラーとビューを作成。
ファイル名とディレクトリ名の命名規約がキャメルケースになったのを注意するぐらいで、簡単なコントローラーなどは作成できました。
がっつりしたアプリケーションを開発する場合に、1.Xとの差を感じるんでしょうね。

マルチバイト関係の問題もあるみたいですし、実際の案件で使用するのはもうしばらく先だと思うんで、テストで色々と作成してみよ~。

『Google +1 ボタン』とか『いいね!』ボタンとかをつけてみた

せっかくブログを書いているので、気になったことは色々試したいと思います。

というわけで、『Google +1 』ボタンをつけてみます。
ついでに、『いいね!』ボタン(facebook)・『ツイートする』ボタン(twitter)・『B!』ボタン(はてなブックマーク)もつけちゃいます。

では、WordPressを例に説明していきます。


1・『Google +1』ボタン

まずは、『Google +1』ボタンから。

以下のリンクから簡単にソースコードを取得できます。

「Google +1 をウェブサイトに表示」

基本的には、ボタンのサイズや使用する言語を選択するとソースコードが変更されていきますので、指示にしたがって張り付けるだけです。
詳細オプションをクリックすると、コールバック関数や『+1』をつけるサイトのURLを指定したりすることができます。

▼『Google +1 』ボタンを記事一覧に設置

記事ごとに『Google +1』ボタンを設置したい時は、『+1』をつけるURLを変更します。
私の場合、記事一覧で記事ごとに『+1』をつけれるようにしたかったので、『content.php』に以下のコードを追加しました。

<!--▼Google+1 ここから-->
<g:plusone href="<?php the_permalink(); ?>" size="medium"></g:plusone>
<!--▲Google+1 ここまで-->

『the_permalink』テンプレートタグで記事のURLを取得しているだけです。
私は、『content-single.php(記事詳細)』にも同じコードを追加しました。

あとは、『header.php』に以下のコードを追加するだけです。
『head』要素の最後に貼り付ければオッケーです。

<script type="text/javascript" src="https://apis.google.com/js/plusone.js">{lang: 'ja'}</script>

これで、『Google +1』ボタンの設置は終了です。


2・『ツイートする』ボタン

次は、有名な『ツイートする』ボタンです。

これも以下のリンクから簡単にソースコードを取得できます。

「Twitter/ツイートボタン」

指示にしたがって、色々選択するとソースコードが変更されますのでコピペするだけです。

▼『ツイートする』ボタンを記事一覧に設置

記事ごとに『ツイートする』ボタンを設置したい時は、『a』要素の『data-url』の値を変更します。

ツイート内テキストを変更したい場合は、『a』要素の『data-text』の値を変更します。

私は、以下のようにしました。

<!--▼twitter ここから-->
<a href="https://twitter.com/share" class="twitter-share-button" data-url="<?php the_permalink(); ?>" data-text="『あなたのブログ名に変更』 <?php the_title(); ?>" data-count="none" data-lang="ja">Tweet</a>
<!--▲twitter ここまで-->

上記のコードを、『Google +1』ボタンのソースコードと同じ場所に追加します。

あとは、以下のコードを『header.php』に追加します。
これまた『head』要素の最後に貼り付ければオッケーです。

<script type="text/javascript" src="//platform.twitter.com/widgets.js"></script>

これで、『ツイートする』ボタンの設置は終了です。


3・『B!』ボタン

次は、『B!』ボタンです。

『B!』ボタンのソースコードは、以下のリンクから取得できます。

「はてなブックマークボタンの作成・設置について」

しつこいようですが、指示にしたがって色々選択するとソースコードが変更されますのでコピペするだけです。

▼『B!』ボタンを記事一覧に設置

記事ごとに『B!』ボタンを設置したい時は、『a』要素の『href』の値の『http://b.hatena.ne.jp/entry/』の後を変更します。

タイトルを変更したい場合は、『a』要素の『data-hatena-bookmark-title』の値を変更します。

私は、以下のようにしました。

<!--▼はてブ ここから-->
<a href="http://b.hatena.ne.jp/entry/<?php the_permalink(); ?>" class="hatena-bookmark-button" data-hatena-bookmark-title="『あなたのブログ名に変更』 <?php the_title(); ?>" data-hatena-bookmark-layout="simple" title="このエントリーをはてなブックマークに追加"><img src="http://b.st-hatena.com/images/entry-button/button-only.gif" alt="このエントリーをはてなブックマークに追加" width="20" height="20" style="border: none;" /></a>
<!--▲はてブ ここまで-->

上記のコードを、『Google +1』ボタン、『ツイートする』ボタンのソースコードと同じ場所に追加します。

あとは、以下のコードを『header.php』に追加します。
これも『head』要素の最後に貼り付ければオッケーです。

<script type="text/javascript" src="http://b.st-hatena.com/js/bookmark_button.js" charset="utf-8" async="async"></script>

これで、『B!』ボタンの設置は終了です。


4・『いいね!』ボタン

最後は、『いいね!』ボタンです。

『いいね!』ボタンのソースコードは、以下のリンクから取得できます。

「Like Buttom」

英語ですが、指示にしたがって色々選択していき、『Get Code』ボタンをクリックするとソースコードが表示されます。
ソースコードが表示されているウインドウの『実装』を変更すると、選択した実装方法のソースに変更されます。
私は、『iFrame』を選択しました。

▼『いいね!』ボタンを記事一覧に設置

私は、『iframe』を選択したので『iframe』にあわせて説明します。
記事ごとに『いいね!』ボタンを設置したい時は、『iframe』要素の『src』の『?href=』の値を変更します。
私は、以下のようにしました。

<!--▼facebook ここから-->
<iframe src="http://www.facebook.com/plugins/like.php?href=<?php the_permalink(); ?>" scrolling="no" frameborder="0" style="border:none; overflow: hidden; width: 80px; height: 25px;" allowTransparency="true"></iframe>
<!--▲facebook ここまで-->

上記のコードを、『Google +1』ボタン、『ツイートする』ボタン、『B!』ボタンのソースコードと同じ場所に追加します。

『いいね!』ボタンはこれで終了です。


ほとんどコピペで、簡単に実装できるのがいいですよね><

私は、はてブの数やツイート数は表示しないアイコンを選択しましたが(数が増えなかったら寂しいから・・・)、色々なアイコンが用意されているので、ご自分にあったアイコンを選択して実装してください^^

「PHPer」って響き

「PHPer」って「ペチパー」って読むらしいです。
なんかね・・・ちょっと力抜ける感じ。
「Flasher(フラッシャー)」とか、かっこいい感じ。
まあ最近は、「ペチパー」って響きが気に入ってきたんですけどね!!

ちなみに、PHPでよく使われるライブラリ「PEAR」は「ペアー」って読むらしいです。
僕は長い間「ピアー」って思ってました。

「ピアー」って響きのほうが好きだったのに・・・
徹夜の時、「ピアー」って叫ぶと元気がでたのに・・・

Googleの入社試験(非公式)にチャレンジしてみた

プログラマーを目指す前の話なんですが、大阪の『ちちんぷいぷい』という番組で『Googleの入社試験を紹介』というコーナーを見たことがありました。
その時は、「この人たちの頭の中はどうなっているんだ・・・」と思うだけだったのですが、僕も今ではプログラムを嗜む身。
1問ぐらいは解いてやろうと思い、ググってみると面白そうな問題がありました。

▼問題文
整数nが与えられたとき、0からnの間の全ての数を書くのに必要とされる「1」の数を返す関数があります。たとえば、『f(13)=6』になります。また、『f(1)=1』に注意。『f(n)=n』となるような、2番目に大きいnを求めなさい。

面白そうな問題でしょ?
さっそくチャレンジしてみましょ。
僕は、PHPerなのでPHPで解いてみます。


2012/01/06  追記

ソースコードを間違っていました・・・。
修正版に書き直しています。


▼以下、問題にチャレンジ


2番目に大きいnってことは、『f(1)=1』の次の整数nを探せばクリア(って事ですよね・・・?)
とりあえず、関数f(n)を作成しない事には答え合わせもできないので、先に関数f(n)を作っちゃいます。

/**
 * 引数nの中にある「1」の数を返す
 *
 * $n		int	整数値を指定
 * return	int	0からnの間の全ての数を書くのに必要とされる「1」の数を返す
 */
function f($n) {
    $count = 0;

    for($i = 1; $i

substr_countを使って、1の文字を数え、出現回数を返すだけの簡単な関数です。
これで、「0からnの間の全ての数を書くのに必要とされる1の数」を数える事ができました。
あとは、「2番目に大きいn」を探すだけです。
関数f(n)を使って総当りで調べてもいいんですが、さすがにそれはスマートじゃないし、タイムオーバーしちゃう。
ってわけで、こんな関数を作りました。

/**
 * 引数$startから引数$endの中にある「1」の数を返す
 *
 * $start	int	1の出現回数を調べる範囲の開始値を整数値で指定
 * $end		int	1の出現回数を調べる範囲の終了値を整数値で指定
 * return	int	$startから$endの間の全ての数を書くのに必要とされる「1」の数を返す
 */
function fEx($start, $end) {
    $count = 0;

    for(; $start

1~10までの数を書くのに必要とされる「1」の数を返す関数です。
この関数で、「1」を数える範囲を小分けにします。
次は、「2番目に大きいn」を探す関数を作ります。

/**
 * 0からnの間の全ての数を書くのに必要とされる「1」の数の2番目に大きいnを返す。
 *
 * return	int	2番目に大きいnを返す。
 */

function main() {
    $allCnt = 0;	// 『1』の数
    $start  = 1;	// 『1』の数を数える開始範囲
    $end    = 10;	// 『1』の数を数える終了範囲
    $i      = 0;	// ループ回数をカウント(ログ用のオマケ)

    // 1・結果が見つかるまで無限ループを開始
    while(true) {
        // 2・$startから$endの範囲の『1』の数を数え、前回の検索範囲の『1』の数と足す
        $allCnt += $this->fEx($start, $end);

        /* 3・「f(n) = n」となるということは、検索範囲の中に答えがあるはず(答えが「n == 1」なら1~10の間に答えがある)なので、検索範囲の中に『1』の数があればチェックする
         *    「f(1) = 1」は除外
         */
        if($allCnt >= $start && $allCnt <= $end && $start != 1) {
            // 4・開始範囲から1づつ足して確認したいため、開始の数を代入
            // 5・「f(n) = n」になれば終了。falseなら終了範囲を超えるまで1を足す
            for($tmp = $start; $tmp <= $end; $tmp++) {
                if(($this->f($tmp) == $tmp)) {
                    echo "
ヒットしました。    答えは、『 $tmp 』です。"; return $tmp; } } // 6・ヒットしなかったので、ログを出力。 $i++; echo "『 $start ~ $end 』の間ではヒットしませんでした。$i 回目のループに入ります
"; } // 7・3の条件にあてはまらなかったので、次の検索範囲を指定してループ再開 $start += 10; $end += 10; } }

【ソースコードの説明】


1・結果が見つかるまで無限ループを開始。


2・関数fEx($start, $end)を使って『1』の数を数え、前回検索した範囲の『1』の数と足す。


3・「f(n) = n」になるなら、検索した範囲の中にnがあるはずなので、『1』の数が検索範囲内ならチェック。
(f(1)=1になる事は分かっているので、$startが「1」の場合はチェックしません)


4・開始範囲から1づつ足して確認したいため、開始の数を代入
(2番目に大きい数なので、検索開始範囲から探した方が早いと思う)


5・「f(n) = n」になれば終了。falseなら終了範囲を超えるまで1を足す。


6・検索範囲内に答えがなければ、ログを出力。


7・『1』の数が検索範囲内になければ、次の検索範囲を指定してループを再開する。

これで、「2番目に大きいn」が見つかるはず・・・
んで、PHPを実行。


【実行結果】
『 11 ~ 20 』の間ではヒットしませんでした。1 回目のループに入ります
『 199911 ~ 199920 』の間ではヒットしませんでした。2 回目のループに入ります
『 199921 ~ 199930 』の間ではヒットしませんでした。3 回目のループに入ります
『 199931 ~ 199940 』の間ではヒットしませんでした。4 回目のループに入ります
『 199941 ~ 199950 』の間ではヒットしませんでした。5 回目のループに入ります
『 199951 ~ 199960 』の間ではヒットしませんでした。6 回目のループに入ります
『 199961 ~ 199970 』の間ではヒットしませんでした。7 回目のループに入ります
『 199971 ~ 199980 』の間ではヒットしませんでした。8 回目のループに入ります

ヒットしました。 答えは、『 199981 』です。

答え合わせに関数fで確認したところ、ちゃんと『f(n)=n』になってました^^
いや~。解けてよかった><
また問題にチャレンジしてみよ~。


追記
まあ、本当にこれで正解なのかは分かりませんが・・・。
「間違ってるよ」とか「無駄な処理してるよ」という方。ご指摘頂けたら嬉しいです。