データ構造
データ構造は、データを保持するための構造です。最適化する目的に応じて、データを保持、整理するための多くのアプローチがあります。
面接官が重視すると思われる順番で、一般的なデータ構造を紹介します。
配列
配列はデータを保持する最もシンプルな方法です。配列ではオブジェクトの簡単なリストが用意され、そこにデータが格納されます。インデックスがあれば素早く検索することができますが、そうでなければ遅くなります。たとえば「リストの中で12番目の人物のデータを読み出す」といった場合には高速で処理できるのですが、「"アレックス"という名前の人物をすべて見つける」といった場合には時間がかかるのです(データセッ ト内の全員を調べなければならないため)。 ほとんどの言語では、配列を作成した後で長さを「延ばす」ことはできません。前もって配列の長さを指定する必要があり、後から変更することはできません。
問題例
最後尾に空のスポット (ゼロ) をもつ正の整数のソート済みの配列があります。ある要素をソート順に従うように挿入しなさい。
詳細：
ハッシュテーブル
ハッシュデーブル(「辞書」や「ハッシュマップ」とも呼ばれます)を使うと、「値」に対して「キー」を割り当てることができます。このキーは多くの場合、数字または文字列です。値はどんなタイプのオブジェクトでもかまいません。 これはとても便利なデータ構造です。きわめて高速に探索できるからです。面接では通常、100%真でないとしても、ハシシュテーブルに要素を挿入して探索する実行時間は、O(1)(データ数を問わず、一定時間)と仮定します。ハッシュテーブルの実装がお粗末だと、探索にO(N)時間かかります。 ハシシュテーブルを使って、個人のID番号からほかの情報を持つ何らかのオブジェクトにマップしたりします。
問題例
ユニークな文字列のリストが2つ(AとB)があります。AがBのサブセットであるかどうかを決定するプログラムを書きなさい。つまり、Aのすべての要素がBに含まれているかどうかを確認しなさい。
詳細：
【コーディング面接】ハッシュテーブルに関する問題と解説 - 情報工学科の大学生が学ぶこと
木とグラフ
グラフとは、エッジ(枝)で結ばれたノード(節点)の集まりです。すべてのノートが接続されている必要はありません。独立したサブグラフが複数存在していてもかまいません。またエッジには「有向」と「無向」の2種類があります。有向のエッジ(有向辺)は一方通行の道のようなもので、無向のエッジ(無向辺)は双方向の道だと考えてください。有向グラフの場合、vからWへと向かうエッジは、WからVへと向かうエッジとは異なります。したがって、ノードnからノードmへと「ドライブ」できたとしても、逆に向かうことができない場合もあります。
木とはグラフの一種で、この中にあるあらゆる2つのノードは、たった1つのパス(経路)を通じて結びついています。2つのノードの間には1つのパスしかないので、木の中でループは発生しません。
木はさまざまな形をとることができますが、二分木が最も一般的です。二分木は、各ノートに子ノートが2つだけある木です。2つの子ノードを、左ノード、右ノードと呼びます。どんな木でも、「ループ」にはなりません(あるノードからそれ自体へ戻るバスはありません)。このような制限があるため、二分木で次のように厳密に階層化された形式を表現できます。
一般的には、二分探索木が使われます。二分探索木は、左のサブ木のノードはすべてのノードの値より小さく、 右のサブ木のすべてのノードの値より小さい木です。先ほどの木は二分探索木です。 二分探索木が平衡である場合(通常、平衡の二分探索木を扱います)、要素の挿入や要素の検索の実行時間 はO(logn)です。nはノートの数です。
