「有名 IT 企業のコーディング面接での出題から選び抜いた最高の 189 問を収録」とある。
日本の IT 企業では、特に大企業では、コーディング面接というのがあるのだろうか。 私の思い込みでは、大企業であればあるほど、自前ではコーディングせずに、 他の協力会社にコーディングを任せる傾向にあるのでコーディング面接は行わない、 と思っているのだがどうだろうか。
ページ数の割に情報量が多いが、これは字が小さいためである。若い人が読むもので、 私のような年寄りが読むものではなさそうだ。
プログラムのほとんどは Java で書かれている。私のようなロートルは C しか書けないので、 なかなか理解できないのがつらいところだ。
急いで翻訳されたのだろうか、稚拙な訳が散見される。また、誤植もある。いくつかの誤植は、 本書のサポートページ (book.mynavi.jp) に正誤情報として掲載されているが、下記はサポートページに載っていないものだ。 誤訳を反面教師としながら読んでいくしかないのだろう。 →以下は私が直したものだが、私の直しのほうが更に稚拙だといわれそうだ。
p. 79 上から 8 行め、
「けれども、小さなケースを使うとバグを発見時間が短くなります。」
→「けれども、小さなケースを使うとバグを発見する時間が短くなります。」
p. 151 「再帰と反復」の項、上から 4 行め、
「再起コードに取り掛かる前に、」
→「再帰コードに取り掛かる前に、」
p. 151 「動的計画法とメモ化」の項、上から 5 行め、
「再起呼び出しのパターンを学び、」
→「再帰呼び出しのパターンを学び、」
p. 151 「動的計画法とメモ化」の項、下から 1 行め、
「再帰的な開放を実装し、」
→「再帰的な解法を実装し、」
p. 206 16.9 演算の項、上から２行め、
「演算子は和算のみを用いてください。」
→「演算子は加算のみを用いてください。」
なお、p.532 の解法では、正しく「加算」となっている。「和算」というと、
日本古来の数学術をいう。
p. 287 「解法」の項、第2段落
「親ノードにつながっているかどうかいるかどうかです。」
→「親ノードにつながっているかどうかです。」
p. 308 「5.1 挿入」の項、上から 1 行めから２行め、
「N の j ビット目から i ビット目を M を挿入するメソッド」
→「N の j ビット目から i ビット目の間に M を挿入するメソッド」
p. 326 下から 3 行め、
「P(同じ方向) = 2 (1/2)n+(1/2)n-1」
→「P(同じ方向) = 2 (1/2)n=(1/2)n-1」
p. 358 「パズルを解くアルゴリズム」の項、上から 1 行め、
「角のピース、橋のピース、中のピース」
→「角のピース、端のピース、中のピース」
p. 397 「基本状態：１文字の文字列」の項、3文字の文字列の場合の１行おいて下、
「生成すればよいでほうか？」
→「生成すればよいでしょうか？」
p. 446 「10.6 大きなファイルのソート」の項、上から 1 行め、
「1 行あたり 1 文字列のデータを持つ 20 GB のファイルがあるのをイメージしてください。」
→「1 行あたり 1 文字列のデータを持つ 20 GB のファイルをイメージしてください。」
p. 446 「10.6 大きなファイルのソート」の項、上から 1 行め、
「1 行あたり 1 文字列のデータを持つ 20 GB のファイルがあるのをイメージしてください。」
→「1 行あたり 1 文字列のデータを持つ 20 GB のファイルをイメージしてください。」
以下、私が本書のコードを実行するまでに至った例を、恥ずかしいがお目にかける。
コードは下記にあるから最初からこれを実行すればいいのだろうが、試行錯誤するのもいい機会だ。
https://github.com/careercup/CtCI-6th-Edition/tree/master/Java
p.270 にある次の問題を解こうとした。
4.1 ノード間の経路：有向グラフが与えられたとき、 ２つのノード間に経路があるかどうかを判定するアルゴリズムを設計してください。
グラフの探索は深さ優先探索（Depth First Search, DFS ）か幅優先探索（Breadth First Search, BFS）を使うということは知っている。 本書では幅優先探索のコードが掲載されている。これを実行しようとして躓いた。
$ javac --version javac 14.0.2
本書の pp.270-271 にあるコードをそのままここに載せると著作権に触れるかもしれないので、エラー表示だけを書く。 このコードは Search.java というファイル名で保存されているとする。最初のコンパイルエラーはこうだ。
$ javac -g Search.java
Search.java:12: エラー: シンボルを見つけられません
boolean search(Graph g, Node start, Node end) {
^
シンボル: クラス Graph
場所: クラス Search
Search.java:12: エラー: シンボルを見つけられません
boolean search(Graph g, Node start, Node end) {
^
シンボル: クラス Node
場所: クラス Search
Search.java:12: エラー: シンボルを見つけられません
boolean search(Graph g, Node start, Node end) {
^
シンボル: クラス Node
場所: クラス Search
（後略）
Graph と Node の定義がないと叱られた。定義をしよう。 これらのクラスの定義は p.124 に掲載されている。
class Graph {
public Node[] nodes;
}
class Node {
public String name;
public Node[] children;
}
これで事態は改善しただろうか。
$ javac -g Search.java
Search.java:27: エラー: シンボルを見つけられません
for (Node u : g.getNodes()) {
^
シンボル: メソッド getNodes()
場所: タイプSearch.Graphの変数 g
Search.java:28: エラー: シンボルを見つけられません
u.state = State.Unvisited;
^
シンボル: 変数 state
場所: タイプSearch.Nodeの変数 u
Search.java:30: エラー: シンボルを見つけられません
start.state = State.Visiting;
^
シンボル: 変数 state
場所: タイプSearch.Nodeの変数 start
Search.java:36: エラー: シンボルを見つけられません
for (Node v : u.getAdjacent()) {
^
シンボル: メソッド getAdjacent()
場所: タイプSearch.Nodeの変数 u
Search.java:37: エラー: シンボルを見つけられません
if (v.state == State.Unvisited) {
^
シンボル: 変数 state
場所: タイプSearch.Nodeの変数 v
Search.java:41: エラー: シンボルを見つけられません
v.state = State.Visiting;
^
シンボル: 変数 state
場所: タイプSearch.Nodeの変数 v
Search.java:46: エラー: シンボルを見つけられません
u.state = State.Visited;
^
シンボル: 変数 state
場所: タイプSearch.Nodeの変数 u
（後略）
シンボル state が見つけられないエラーについては、 定義をすれば大丈夫だ。
class Graph {
public Node[] nodes;
}
class Node {
public String name;
public Node[] children;
public State state; // 追加
}
これでエラーは少なくなるはずだ。
Search.java:28: エラー: シンボルを見つけられません
for (Node u : g.getNodes()) {
^
シンボル: メソッド getNodes()
場所: タイプSearch.Graphの変数 g
Search.java:37: エラー: シンボルを見つけられません
for (Node v : u.getAdjacent()) {
^
シンボル: メソッド getAdjacent()
場所: タイプSearch.Nodeの変数 u
エラー2個
make: *** [Makefile:41: Search.class] エラー 1
シンボル state のエラーは解消したが、getNodes() メソッドのシンボルが見つけられないエラーは残っているし、 今度は getAdjacent メソッドのシンボルが見つけられないエラーが新たに出た。 調べると、これらの for 文は拡張 for 文と呼ばれていること、 拡張 for 文のコロンの右に記すのはコレクションであることがわかった。では、 コレクションとなるメソッドをどのように書いたらよいのか、わからない。 上記のエラーのうち、getNodes メソッドは g にあるノードすべてを列挙するメソッドだろうし、 getAdjacent メソッドは u 自身のノードに隣接するノードすべてを列挙するメソッドなのだろうが、 よくわからない。
少し考えて、どちらの場合も g からたどれるノードすべてを列挙すればいいのだから、
それぞれ、
for (Node u : g.nodes)
と
for (Node v : u.children)
でよい気がしてきた。これでコンパイルをしてみて、通った。以下、やったことを記す。
グラフとノードの定義は次のとおりとなる。
static class Graph {
Graph(int n) {
this.nodes = new Node[n];
}
public Node[] nodes;
}
static class Node {
Node(String name, int n) {
this.name = name;
this.children = new Node[n];
this.state = State.Unvisited;
}
public String name;
public Node[] children;
public State state;
}
Graph 型の変数 g と Node 型の変数 n を初期化するときはこうする。 グラフは 6 つのノードからなり、ノード 0 から ノード 1 へのリンクがあるとする。：
Graph g = new Graph(6);
g.nodes[0] = new Node("0", 1);
g.nodes[1] = new Node("1", 0);
g.nodes[0].children[0] = g.nodes[1];
それにしても、大変だ。
これは Java 11 ではというより Java 9 からなのだが、
new Integer(1) という書き方は非推奨となった。
したがって、
https://github.com/careercup/CtCI-6th-Edition/blob/master/Java/CtCILibrary/CtCILibrary/AssortedMethods.java
の 110 行目にある
Integer lsb = new Integer(a & 1);
は次のように書き直すべきだ。
Integer lsb = Integer.valueOf(a & 1);
中級編の問題 16.3 を紹介する。
2つの線分（始点と終点がある点）が与えられたとき、交点が存在する場合は計算してください。
本書の解法では、線分を定義域と値域のある直線と定義し、直線を傾きと切片からなる直線の方程式で定義した上で、 直線どうしの交点が定義域・値域にあるかどうかで交点の存在とその場所を計算している。 これでもいいが、傾きを求めるときのゼロ除算が気になる。 私が思い出したのは、符号付き三角形の面積を使う方法である。 この方法では、除算が発生しないのでゼロ除算の手当を心配する必要はない。 コンピュータグラフィックスでは常識といってよい方法である。
線分 AB と線分 CD の交点があるとはどういうことか。少し考えると、次のような定義となる。 線分 AB と線分 CD が交わるには、直線 AB と線分 CD が交わり、 かつ直線 CD と線分 CD が交わればよい。つまり線分同士の関係を、直線と線分の関係に変更する。 次に変更した定義で考える。まず直線 AB と線分 CD を考える。 直線 AB と線分 CD が交わる必要十分条件は、点 C と点 D が直線 AB で分けられる２つの半平面で、 異なる半平面に所属することである。直線 CD と線分 AB が交わる必要十分条件も同様である。
では、直線により分けられる２つの半平面があるとき、２つの点がそれぞれ異なる半平面に所属することは、 どのように定式化できるか。これには、符号付き面積を導入するといい。 原点を `O` とする２次元直交座標で、点 `A =(a_x, a_y)` と 点 `B = (b_x, b_y)` があるとき、 三角形 OAB の符号付き面積 `S(△OAB)` は次のようにあらわされる。
`S(△OAB) = 1/2 (a_xb_y - a_yb_x)`
符号を無視すれば、三角形の面積になっている。また、正負の符号は、三角形の内部からみて点 O 、点 A 、点 B がこの順で半時計回りになっているときにプラス、時計回りになっているときにマイナスとなる。 この符号付き面積の考え方を使えば、直線 AB に関して点 C と点 D が異なる半平面にあることは、 次の式と同値である。
`S(△CAB) * S(△DAB) lt 0`
以上の考え方をコードにするのは容易だろう。
この議論では、一つの線分の端点がもう一つの線分上にある場合などについては議論しなかった。
この場合は、交点があると解釈すると、上の不等式を次にするだけでよい。
`S(△CAB) * S(△DAB) le 0`
考えてみれば、上の式は交点があるかないかを判定するだけであった。 交点の座標を求める式については、別に説明する。
直交座標での直線の方程式から交点を求めてもいいが、別の考え方をする。以下、原点を O とし、 ベクトル OA を `bb a` などと表記する。 線分 AB 上の点 P はベクトルを使うと t をパラメータとして次のように書ける：
`bb p = t bb b + (1-t) bb a`
この点 P は線分 CD 上にある。したがって、△CPD の面積はゼロである。 これから t が求められ、その結果点 P の座標が求められる。
上級編の問題 17.3 を紹介する。
ランダムな集合：サイズ n の配列から m 個の整数の集合をランダムに生成するメソッドを書いてください。 各要素の選ばれる確率はすべて等確率になるようにしてください。
本書の解答で採用しているアルゴリズムはシンプルである。このアルゴリズムが優れている点は、 無作為抽出に適用したときに母集団の名簿の人数が不明である場合にも適用できることにある。 このアルゴリズムは、 改訂新版 C 言語による標準アルゴリズム事典で、 無作為抽出の項のrndsamp2.c で紹介されているアルゴリズムでもある。 しかし、乱数発生ルーチンは n - m 回呼び出される。 もし、n が事前にわかっていて、かつ n が m に比べて非常に大きいとしたら、 乱数発生ルーチンを m 回で済ませる方法もある。これについては、JavaScript のプログラム例を ランダム集合とランダム順列に掲げた。
さらに考えると、乱数発生ルーチンを１回だけで済ませる方法もある。
計算量の観点からこれが最適とは言い難いが、頭の体操としてこういうこともできるということを示す。
まず、n 個のものから m 個のものを選ぶ組み合わせの数は `((n),(m))` であることを認識する。
この数を C とする。
次に、0 以上 C 未満の整数を一様乱数で選ぶ。選んだ数を c とする。
この c から組み合わせが復元できればよい。それは可能である。
http://www.nct9.ne.jp/m_hiroi/gbook4.html
の「120.完全ハッシュ関数の逆関数」にある、高橋謙一郎氏のコードのうち、
/* 組合せ型の完全ハッシュ逆関数(鎌田さんのコードより) */
というコメントがある void ncr2inv() 関数を使って組み合わせの実体 p を見ればよい。
具体的には、C のコードで
char p[r];
ncr2inv(n, m, c, p);
として、p に入っている組み合わせの実体を見ればよい。
なお、上記コードについては、
http://www.nct9.ne.jp/m_hiroi/gbook5.html
で M.Hiroi 氏による改良案も提示されている。これらが正しければ、
１度の乱数呼び出しでランダムな集合を求めることができる。
しかし、 私にはこれらのコードが正しいかどうかはわからない。無責任と言われるだろうが、 批判は甘んじて受ける。
| 書 名 | 世界で闘うプログラミング力を鍛える本 ~コーディング面接189問とその解法 |
| 著 者 | Gayle Laakmann McDowell |
| 発行日 | 2017 年 2 月 24 日 初版 第 1 刷 |
| 発行元 | マイナビ |
| 定 価 | 円（本体） |
| サイズ | ページ |
| ISBN | 978-4-8399-6010-0 |
| その他 | 越谷市立図書館南部図書室で借りて読む |
まりんきょ学問所 ＞ コンピュータの部屋 ＞ コンピュータの本 ＞ プログラミング ＞ Gayle Laakmann McDowell：世界で闘うプログラミング力を鍛える本 ~コーディング面接189問とその解法
