次のコーディングインタビューで知っておくべき上位のデータ構造

スイスのコンピューター科学者であるニクラウス・ヴィルトは、1976年に「アルゴリズム+データ構造=プログラム」というタイトルの本を書きました

40年以上経った今でも、その方程式は当てはまります。そのため、ソフトウェアエンジニアリングの候補者は、アプリケーションとともにデータ構造を理解していることを実証する必要があります。

ほとんどすべての問題は、候補者がデータ構造の深い理解を示すことを要求します。(大学またはコーディングブートキャンプを卒業したばかりか)、数十年の経験があるかどうかは関係ありません。

面接の質問で、たとえば「二分木が与えられた」などのデータ構造について明示的に言及されることがあります。また、「各著者に関連付けられている本の数を追跡したい」など、暗黙的な場合もあります。

現在の仕事を上達させようとしているだけでも、データ構造を学ぶことは不可欠です。基本を理解することから始めましょう。

データ構造とは何ですか?

簡単に言うと、データ構造は、特定のレイアウトでデータを格納するコンテナーです。この「レイアウト」により、データ構造を一部の操作で効率的にし、他の操作で非効率的にすることができます。目標は、データ構造を理解して、目前の問題に最適なデータ構造を選択できるようにすることです。

なぜデータ構造が必要なのですか?

データ構造は組織化された形式でデータを格納するために使用され、データはコンピュータサイエンスで最も重要なエンティティであるため、データ構造の真の価値は明らかです。

解決する問題が何であれ、何らかの方法でデータを処理する必要があります。データは、従業員の給与、株価、買い物リスト、または単純な電話帳ですらあります。

さまざまなシナリオに基づいて、データは特定の形式で保存する必要があります。さまざまな形式でデータを保存する必要性をカバーするデータ構造がいくつかあります。

一般的に使用されるデータ構造

最初に最も一般的に使用されるデータ構造をリストし、次にそれらを1つずつ説明します。

  1. 配列
  2. スタック
  3. キュー
  4. リンクリスト
  5. グラフ
  6. 試行します(これらは事実上ツリーですが、個別に呼び出すことをお勧めします)。
  7. ハッシュテーブル

配列

配列は、最も単純で最も広く使用されているデータ構造です。スタックやキューなどの他のデータ構造は、配列から派生しています。

これは、要素(1、2、3、および4)を含むサイズ4の単純な配列の画像です。

各データ要素と呼ばれる正の数値が割り当てられているインデックス配列内のその項目の位置に対応します。大多数の言語は、配列の開始インデックスを0として定義しています。

以下は、2つのタイプの配列です。

  • 1次元配列(上記のとおり)
  • 多次元配列(配列内の配列)

配列の基本操作

  • 挿入—指定されたインデックスに要素を挿入します
  • Get —指定されたインデックスの要素を返します
  • 削除—指定されたインデックスの要素を削除します
  • サイズ—配列内の要素の総数を取得します

アレイインタビューに関するよくある質問

  • 配列の2番目の最小要素を見つける
  • 配列内の最初の非反復整数
  • ソートされた2つの配列をマージする
  • 配列内の正の値と負の値を再配置します

スタック

私たちは皆、ほとんどすべてのアプリケーションに存在する有名な元に戻すオプションに精通しています。それがどのように機能するのか疑問に思ったことはありますか?アイデア:作業の以前の状態(特定の数に制限されている)を、最後の状態が最初に表示される順序でメモリに保存します。これは、配列を使用するだけでは実行できません。そこで、スタックが役に立ちます。

Stackの実際の例は、縦に並べられた本の山です。真ん中の本を手に入れるには、その上にある本をすべて削除する必要があります。これがLIFO(後入れ先出し)方式の仕組みです。

これは、3つのデータ要素(1、2、および3)を含むスタックの画像です。3が一番上にあり、最初に削除されます。

スタックの基本操作:

  • プッシュ—上部に要素を挿入します
  • Pop —スタックから削除した後に最上位の要素を返します
  • isEmpty —スタックが空の場合はtrueを返します
  • Top —スタックから削除せずにtop要素を返します

スタックインタビューのよくある質問

  • スタックを使用して後置式を評価する
  • スタック内の値を並べ替える
  • 式のバランスの取れた括弧を確認します

キュー

スタックと同様に、キューは要素を順次格納する別の線形データ構造です。スタックとキューの唯一の重要な違いは、LIFOメソッドを使用する代わりに、キューがFIFOを実装することです。メソッド。FirstinFirstOutの略です。

キューの完璧な実例:チケット売り場で待っている人々の列。新しい人が来た場合、彼らは最初からではなく最後から列に加わります—そして前に立っている人が最初にチケットを手に入れて列を去ります。

これは、4つのデータ要素(1、2、3、および4)を含むキューの画像です。1が一番上にあり、最初に削除されます。

キューの基本操作

  • Enqueue()—キューの最後に要素を挿入します
  • Dequeue()—キューの先頭から要素を削除します
  • isEmpty()—キューが空の場合はtrueを返します
  • Top()—キューの最初の要素を返します

よくあるキューインタビューの質問

  • キューを使用してスタックを実装する
  • キューの最初のk個の要素を逆にする
  • キューを使用して1からnまでの2進数を生成します

リンクリスト

リンクリストは、最初は配列に似ているかもしれませんが、メモリ割り当て、内部構造、および挿入と削除の基本操作の実行方法が異なる、もう1つの重要な線形データ構造です。

リンクリストはノードのチェーンのようなもので、各ノードにはデータやチェーン内の後続ノードへのポインタなどの情報が含まれています。リンクリストの最初の要素を指すヘッドポインタがあり、リストが空の場合は、単にnullまたは何も指していません。

リンクリストは、ファイルシステム、ハッシュテーブル、および隣接リストを実装するために使用されます。

リンクリストの内部構造を視覚的に表したものは次のとおりです。

リンクリストの種類は次のとおりです。

  • 単一リンクリスト(単方向)
  • 二重リンクリスト(双方向)

リンクリストの基本操作:

  • InsertAtEnd —リンクリストの最後に特定の要素を挿入します
  • InsertAtHead —リンクリストの先頭/先頭に特定の要素を挿入します
  • 削除—リンクリストから特定の要素を削除します
  • DeleteAtHead —リンクリストの最初の要素を削除します
  • 検索—リンクリストから指定された要素を返します
  • isEmpty —リンクリストが空の場合はtrueを返します

よくあるリンクリストの面接の質問

  • リンクリストを逆にする
  • リンクリスト内のループを検出する
  • リンクリストの最後からN番目のノードを返す
  • リンクリストから重複を削除する

グラフ

グラフは、ネットワークの形で相互に接続されているノードのセットです。ノードは頂点とも呼ばれます。対(x、y)が呼び出され、エッジ頂点ことを示すxは、頂点に接続されているY。エッジには重み/コストが含まれる場合があり、頂点xからyにトラバースするために必要なコストを示します

グラフの種類:

  • 無向グラフ
  • 有向グラフ

プログラミング言語では、グラフは次の2つの形式を使用して表すことができます。

  • 隣接行列
  • 隣接リスト

一般的なグラフトラバースアルゴリズム:

  • 幅優先探索
  • 深さ優先探索

よくあるグラフインタビューの質問

  • 幅と深さ優先探索を実装する
  • グラフがツリーかどうかを確認します
  • グラフのエッジの数を数える
  • 2つの頂点間の最短経路を見つける

ツリーは、頂点(ノード)とそれらを接続するエッジで構成される階層データ構造です。ツリーはグラフに似ていますが、ツリーとグラフを区別する重要な点は、ツリーにサイクルが存在できないことです。

ツリーは、問題解決のための効率的なストレージメカニズムを提供するために、人工知能や複雑なアルゴリズムで広く使用されています。

単純なツリーの画像と、ツリーデータ構造で使用される基本的な用語を次に示します。

木の種類は次のとおりです。

  • N-aryツリー
  • バランスツリー
  • 二分木
  • 二分探索木
  • AVLツリー
  • 赤黒木
  • 2–3ツリー

上記の中で、バイナリツリーとバイナリ検索ツリーが最も一般的に使用されるツリーです。

ツリーインタビューのよくある質問

  • 二分木の高さを見つける
  • 二分探索木でk番目の最大値を見つける
  • ルートから「k」の距離にあるノードを見つけます
  • バイナリツリーで特定のノードの祖先を検索します

トライ

「プレフィックスツリー」としても知られるTrieは、文字列に関連する問題を解決するのに非常に効率的であることが証明されているツリーのようなデータ構造です。高速検索を提供し、主に辞書内の単語の検索、検索エンジンでの自動提案の提供、さらにはIPルーティングにも使用されます。

これは、「top」、「thus」、「their」の3つの単語がTrieにどのように格納されているかを示しています。

単語は上から下に格納され、緑色のノード「p」、「s」、「r」はそれぞれ「top」、「thus」、「their」の終わりを示します。

よくあるトライインタビューの質問:

  • Trieの単語の総数を数える
  • Trieに保存されているすべての単語を印刷する
  • Trieを使用して配列の要素を並べ替える
  • Trieを使用して辞書から単語を形成する
  • T9辞書を作成する

ハッシュ表

ハッシュは、オブジェクトを一意に識別し、各オブジェクトを「キー」と呼ばれる事前に計算された一意のインデックスに格納するために使用されるプロセスです。そのため、オブジェクトは「キーと値」のペアの形式で格納され、そのようなアイテムのコレクションは「ディクショナリ」と呼ばれます。そのキーを使用して、各オブジェクトを検索できます。ハッシュに基づくさまざまなデータ構造がありますが、最も一般的に使用されるデータ構造はハッシュテーブルです。

ハッシュテーブルは通常、配列を使用して実装されます。

データ構造のハッシュのパフォーマンスは、次の3つの要因に依存します。

  • ハッシュ関数
  • ハッシュテーブルのサイズ
  • 衝突処理方法

これは、ハッシュが配列にどのようにマッピングされるかを示しています。この配列のインデックスは、ハッシュ関数を介して計算されます。

よくあるハッシュインタビューの質問

  • 配列内の対称ペアを見つける
  • 旅の完全な道をたどる
  • アレイが別のアレイのサブセットであるかどうかを確認します
  • 指定された配列が互いに素であるかどうかを確認します

上記は、コーディングインタビューに入る前に必ず知っておくべき上位8つのデータ構造です。

コーディングインタビューのデータ構造に関するリソースを探している場合は、インタラクティブでチャレンジベースのコースをご覧ください:コーディングインタビューのデータ構造(Python、Java、またはJavaScript)。

より高度な質問については、Coderust 3.0:インタラクティブなチャレンジと視覚化によるより高速なコーディングインタビューの準備をご覧ください。

ソフトウェアエンジニアリングのインタビューの準備をしている場合は、インタビューのコーディングの準備をするための包括的なロードマップを次に示します。

幸運と幸せな学習!:)