世界で闘うプログラミング力を鍛える150問 Cracking The Coding Interview

という本を買いました。 IT企業の採用でしばしば実施されるコーディング面接をどのように攻略するか、 また実際のコーディング問題にどのようにアプローチすべきかを解説した書籍です。

導入部分(書籍の1/4くらい)は主にIT企業に就職するための対策について書かれています。
その後、各章で特定のデータ構造やアルゴリズムについて取り上げて、注意すべき点をまとめ、 コーディングの問題を解くという形式。

問題の解法にかなりページを割いており、書籍(450ページくらい)の半分が解法になっている。

プログラミングの勉強もかねて読んでいこうかなぁと思います。

第一章は配列と文字列  

記念すべき最初の問題は以下


1.1 ある文字列が、すべてユニークであるかチェックするアルゴリズムを実装せよ。またそれを実装する際に新たなデータ構造が使えない場合どうすればよいか


はじめに思いついたのが出現した文字をカウントするという方法。
たとえば文字をkey,文字の出現回数をvalueとするディクショナリをつくり、 valueが2以上になるkeyがあった場合にfalseを返すというもの
簡単に書いてみると以下のような感じ

import java.Util.*

boolean checkStringDuplication(String str){
    Map<Charactor,Integer> CharCountMap = new Map<Charactor,Integer>();
    for (int index=0;index<str.length();index++){
        char c = str.charAt(index);
        if(CharCountMap.containsKey(c)){
            return false;
        else
            CharCountMap.put(c,1);
    }
    return true;
}

と、書いてみたけれど、途中で文字の出現回数をカウントする必要ないと気づいた(CharCountMapなんてひどい名前をつけてしまった...)

結局のところ、既出の文字を記憶しておいて二回目に同じ文字が出たらFalseを返すだけだから、 MapじゃなくてListとかのほうが適切かな。

import java.util.*

boolean checkStringDuplication(String str){
    ArrayList<Character> CharEncountList = ArrayList<Character>();
    for (int index=0;index<str.length();index++){
        char c = str.charAt(index);
        if(CharEncountList.contains(c))
            return false;
        else
            CharEncountList.add(c);
    }
    return true;
}

あらたなデータ構造使うまでもなく実装してしまったけど、ほかにどんな実装が考えられるだろう?

文字列を先頭から順番に見ていくとして、現在注目している文字が文字列中の別の場所で出現しないか をチェックすると考えると、lastIndexOfとかで後ろから出現個所をチェックする方法も考えられそう。

import java.util.*

boolean checkStringDuplication(String str){
    for (int index=0;index<str.length();index++){
        char c = str.charAt(index);
        if(str.lastIndexOf(c) != index)
            return false;
    }
    return true;
}

うーん、これも別に新たなデータ構造つかわないんだよなぁ
まあ、新しく独自の構造を定義するより既存の物を使った方がわかりやすいしいいか

で、解法をみてみると

模範解答では最初に文字列がASCIIと仮定していて、初めに文字列が256を超えるかチェックをしている。
もし文字列が256より大きいなら(ASCIIの文字種より大きいなら)鳩の巣原理的に文字に重複がある。
256より小さい場合は256サイズのboolean配列(各要素がASCII文字に対応)で既出かどうかをフラグだててチェックする
といった形になっている

確かに文字コードについては初めに気にしておくべきかもしれない。
文字コードがわかっていれば必要となる配列サイズがわかり、プログラムがどれくらいのメモリを必要とするのかわかる。
その点を意識しないと実行時にメモリ食ってあぼーんするかもしれないもんなぁ

別解として文字列をソートして頭から比較していく方法とすべての文字を互いに比較する方法について言及してあったが、 いずれにしても「新たなデータ構造を使えない場合」に関しては解法でも触れてないのか。 なんなんだろう

とりあえず今後の課題図書としてチマチマ読み進めようと思います。
面白い問題や解法が思いついたら記事にするかも