目次[隠す][見せる]
- 1. 配列はどのように定義しますか?
- 2. 動的配列: それは何ですか? 基本配列と何が違うのでしょうか?
- 3. 配列と辞書はどのように異なりますか?
- 4. 配列の長所と短所をいくつか挙げます。
- 5. 「疎配列」とは何を指しますか?
- 6. 配列ではなくリンク リストを選択するのはどのような場合ですか?
- 7. インデックス付き配列と連想配列の違いは何ですか?
- 8. ソートされた配列に比べて、ヒープにはどのような利点がありますか?
- 9. 配列のサイズを負になるように定義できますか?
- 10. 1 ~ 100 要素の配列で欠落している整数を見つけるにはどうすればよいですか?
- 11. 配列内の要素のインデックスはどのように見つけますか?
- 12. 配列から特定の要素を削除するにはどうすればよいですか?
- 13. XNUMX つの配列が等しいことはどのように検証できますか?
- 14. 配列について説明するとき、「次元」と「添字」というフレーズは何を意味しますか?
- コーディング面接の質問
- 15. 指定された合計を持つ配列内のペアを探します
- 16. 線形時間によるバイナリ配列のソート
- 17. 配列内の最大の XNUMX つの int 積を見つけます。
- 18. 配列のすべてのゼロを末尾にシフトする方法
- 19. XNUMX 回の操作で切り替えられる XNUMX つのエントリを持つ配列をソートする方法。
- 20. ソートされた XNUMX つの配列を適切な位置で結合する方法。
- 21. 項目の配列を高い位置と低い位置に交互に並べ替えるにはどうすればよいですか?
- 22. 除算演算子を使用せずに配列の各要素を配列の各要素の積に置き換えるにはどうすればよいですか?
- 23. 対数時間で配列内の最も奇数の要素を見つけます
- 24. 円形配列の各要素に対して後続のより大きな要素を取得するにはどうすればよいですか?
- 25. 配列の反転数を調べますか?
- 26. 雨水の滞留問題とは何ですか?
- まとめ
コーディング面接には一連の DSA 質問が含まれます。 FAANG または別の Tier-1 技術企業との今後の技術面接の準備をしているのであれば、アレイの熟練が必要です。
ほとんどのコーディング面接では、文字列に次いで XNUMX 位にランクされます。 配列は、メモリ内で互いに近接して保持される、関連するデータ要素のグループです。
これらは C、C++、Java、Python、Perl、Ruby などのすべてのプログラミング言語に接続されているため、どこにでもあります。 コーディングの練習問題と、配列に基づく面接の質問と回答については、引き続きお読みください。
Python は使いやすく、理解しやすく、ほとんどの人にとって馴染みのあるものであるため、この投稿ではコーディングの問題に取り組むために Python を使用します。
さぁ、始めよう。
1. 配列はどのように定義しますか?
- 関連するデータ型のグループが配列です。
- 配列は常に固定です。
- 同じ種類の変数が配列オブジェクトによって複数の場所に格納されます。
- プリミティブ型とオブジェクト参照の両方に互換性があります。
2. 動的配列: それは何ですか? 基本配列と何が違うのでしょうか?
動的配列 (Java では拡張可能な配列、サイズ変更可能な配列、変更可能な配列、または ArrayList とも呼ばれます) が提供する自動スケーリングは、大きな利点です。
配列のサイズは固定されているため、配列に格納する要素の数を事前に常に知っておく必要があります。 一方、動的配列はメンバーを追加すると増大するため、事前に正確なサイズを知っておく必要はありません。
3. 配列と辞書はどのように異なりますか?
これは、定期的に尋ねられる面接の質問の基本に基づいたものです。 配列と辞書の主な違いは次のとおりです。
- 配列は、類似した項目の順序付きリストです。 一方、辞書にはキーと値のペアがあります。
- 配列のサイズは動的に変更できます。 このようなダイナミックな考え方は辞書には存在しません。
- 配列を利用する前に、そのサイズを指定する必要があります。 辞書のサイズをカスタマイズする必要はありません。
- 配列のサイズを拡張したい場合は、Redim ステートメントを使用します。 ディクショナリでは、宣言なしで要素を追加できます。
4. 配列の長所と短所をいくつか挙げます。
Advantages:
- 配列では、多数の要素を同時に並べ替えることができます。
- その他 データ構造、スタック、キュー、リンクされたリスト、ツリー、グラフなどのように、配列で実装できます。
- インデックスを使用して、配列の要素にアクセスできます。
短所:
- 配列のサイズは事前に宣言する必要があります。 ただし、配列宣言の時点では、必要なサイズが認識されていない可能性があります。
- 配列の構造は静的です。 これは、配列サイズが常に固定されており、メモリ割り当てを増減できないことを意味します。
5. 「疎配列」とは何を指しますか?
スパース配列は、値がゼロのエントリが多数あるデータ配列です。 対照的に、密な配列には、ゼロ以外の値を持つ項目の大部分が含まれます。 数値をオブジェクトに変換する疎配列のインデックスにはギャップが含まれる場合があります。 HashMap と比較すると、メモリ効率が高くなります。
6. 配列ではなくリンク リストを選択するのはどのような場合ですか?
配列の代わりにリンク リストを使用する場合は、次の点を考慮してください。
- ランダムアクセスするには要素は必要ありません。
- 時間的な予測可能性が不可欠な場合は、リストへの一定時間の挿入とリストからの削除が必要です。
- 優先キューを作成するには、項目をリストの中央に配置する必要がある場合があります。
- リストがどれくらい長くなるかわかりません。 配列のサイズが大きくなった場合は、単純な配列の場合と同様に、メモリを再宣言して複製する必要があります。
7. インデックス付き配列と連想配列の違いは何ですか?
連想配列とインデックス付き配列の主な違いを次の表に示します。
- テキストまたは数値形式のキーと値のペアは、連想配列を並べ替えるために使用されます。 インデックス付き配列のキーはすべて数値であり、各キーは個別の値に関連付けられています。
- 連想配列では、キーは文字列である場合があります。 0 から始まる整数キーを持つインデックス付き配列。
- XNUMX 列のテーブルは、連想配列の動作を模倣します。 単一列のテーブルと似ているのは、インデックス付き配列です。
- マップは連想配列タイプです。 インデックス配列はマップではありません。
8. ソートされた配列に比べて、ヒープにはどのような利点がありますか?
ソートされた配列よりもヒープを利用することの時間効率が主な利点です。 ヒープ操作は高速ですが、配列のソートには多くの時間がかかります。 ヒープは、配列をソートするよりもはるかに速く最小の要素を検出できます。
特定の数値のコレクションは、ソート配列を使用して XNUMX つの方法のいずれかで配置できます。 一方、特定の数値のコレクションに対して、複数の潜在的なヒープが存在する可能性があります。
9. 配列のサイズを負になるように定義できますか?
いいえ、負の整数を配列のサイズとして定義することはできません。 宣言してもコンパイル時エラーは発生しません。 ただし、実行時には NegativeArraySizeException が発生します。
10. 1 ~ 100 要素の配列で欠落している整数を見つけるにはどうすればよいですか?
系列の合計は、次の関数を適用して計算できます: n (n + 1) / 2
配列に重複がない場合、または複数の整数が欠落している場合にのみ、この関数は動作します。 配列に重複した要素があるかどうかに関係なく、配列を並べ替えて同等の要素があるかどうかを確認できます。
11. 配列内の要素のインデックスはどのように見つけますか?
要素のインデックスは、線形検索または二分検索によって検出できます。 必要な要素の一致が見つかるまで、線形検索関数は配列内のすべての要素をループします。 一致する要素を見つけるとインデックスを返します。 したがって、線形探索の時間的複雑さは O.(n) です。 ソートされた配列とソートされていない配列の両方で線形検索を使用できます。
二分検索を使用すると、間隔の中央値が必要な要素と一致してインデックスが提供されるまで配列を継続的に半分に分割し、配列がソートされている場合は要素のインデックスを取得できます。 したがって、二分探索の時間的複雑さは O. (log n) です。
12. 配列から特定の要素を削除するにはどうすればよいですか?
要素はサイズが定義された固定セットであるため、元の配列から要素を単純に削除することはできません。面接官は、別のアプローチを提案して、質問が引き起こす問題に対処することを求めています。 最善の対処法は、要素を削除するために新しい配列を作成することです。 この配列の最初の配列から要素を複製し、削除する要素のみを含めることができます。
別の戦略には、配列内のターゲット要素を見つけて、ターゲット要素の右側にあるすべての項目の順序を逆にすることが含まれます。
13. XNUMX つの配列が等しいことはどのように検証できますか?
まず、提供された XNUMX つの配列の長さを確認する必要があります。 両方の配列の一致する項目は、長さが等しい場合に比較されます。 XNUMX つの配列は等しいとみなされます。 すべての対応におけるコンポーネントの各ペアが等しい場合。 XNUMX つの配列のサイズが大きい場合、この方法で XNUMX つの配列の等価性をチェックすることは時間がかかるため、お勧めできません。 Arrays クラスに含まれる equals() メソッドを使用することもできますが、面接官が組み込みメソッドを使用せずに XNUMX つの配列を比較するように求めた場合は、この方法が便利です。
14. 配列について説明するとき、「次元」と「添字」というフレーズは何を意味しますか?
配列の「次元」は、個々のメンバーを識別するために必要なインデックスまたは添字の数です。 下付き文字と寸法が不明瞭な場合があります。 ディメンションは許可されるキーの範囲の説明ですが、添え字は数値です。 配列の各次元に必要な添字は XNUMX つだけです。
たとえば、配列 arr[10][5] には 10 次元があります。 サイズは一方が5、もう一方が0です。 そのコンポーネントを指定するには、4 つの添え字が必要です。 どちらも 0 から 9 の間です。 XNUMX から XNUMX までの値。
コーディング面接の質問
15. 指定された合計を持つ配列内のペアを探します
たとえば、
入力:
- nums = [8、7、2、5、3、1]
- ターゲット= 10
出力:
- ペアが見つかりました (8, 2)
- Or
- ペアが見つかりました (7, 3)
入力:
- nums = [5、2、6、8、1、9]
- ターゲット= 12
出力:
- ペアが見つかりません
16. 線形時間によるバイナリ配列のソート
バイナリ配列を線形時間および固定領域でソートします。 出力では、最初にすべて XNUMX が表示され、次にすべて XNUMX が表示されます。
たとえば、
- 入力: { 1, 0, 1, 0, 1, 0, 0, 1 }
- 出力: { 0, 0, 0, 0, 1, 1, 1, 1 }
簡単なアプローチは、配列の 0 の合計数 (k とする) を計算し、配列内の最初の k 個のインデックスを 0 で埋め、残りのインデックスを 1 で埋めることです。別の方法として、配列 k 内の 1 の合計数を計算し、配列の最後の k 個のインデックスを 1 で埋め、残りのインデックスを 0 で埋めることもできます。
指定されたアプローチの時間計算量は O(n) で、追加のストレージは使用しません (n は入力のサイズです)。
17. 配列内の最大の XNUMX つの int 積を見つけます。
整数配列内の XNUMX つの数値の最大の積を見つけます。
例として配列 10 3 5 6 2 について考えてみましょう。 (-10, -3) または (5, 6) のペアが最高の積です。
あらゆる要素の組み合わせを考えて、その結果を導き出すのは愚かなアプローチです。 現在のペアの積がこれまでに取得した最大積よりも大きい場合は、最大積を更新します。 最終製品のコンポーネントを最後に印刷します。
上記の解決策 (n は入力量) の時間計算量は O(n2) で、それ以上のスペースは必要ありません。
18. 配列のすべてのゼロを末尾にシフトする方法
整数配列内のすべてのゼロを最後に移動します。 答えは、定数スペースの使用を避け、配列のコンポーネントの相対的な順序を保持する必要があります。
入力:{1,2,3,0,8,0,4,7,XNUMX}
出力は {1,2,3,8,4,7,0,0} になります。
現在の要素がゼロでない場合は、配列内の次の利用可能な位置に要素を配置します。 配列の項目がすべて処理されたら、残りのインデックスをすべて 0 で埋めます。
前述の解決策の時間計算量は O(n) です。ここで、n は入力のサイズです。
19. XNUMX 回の操作で切り替えられる XNUMX つのエントリを持つ配列をソートする方法。
交換された XNUMX つの項目と、すべての要素が昇順に配置された配列を指定して、配列を線形時間でソートします。 配列に重複が含まれていないとみなします。
入力:= [1,9,3,4,7,2] または [9,3,7,2,1,4] または [2,4,1,7,3,9]
出力: = [1,2,3,4,7,9]
配列の XNUMX 番目の要素から始めて、各要素をその前の要素と比較することが目的です。 論争の位置は、XNUMX つのポインタ x と y を取得することによって保存されます。
前者が後者より大きい場合は、x を前の要素のインデックスに更新し、y を現在の要素のインデックスに更新します。 前の要素が現在の要素よりも大きいことが判明した場合は、 y を現在の要素のインデックスに更新します。
最後に、隣接する要素の各ペアの処理が完了したら、インデックス x と y の要素を切り替えます。
前述の方法はサイズ n の入力配列の XNUMX 回のスキャンのみを実行するため、その時間計算量は O(n) です。 ソリューションのために追加のスペースは必要ありません。
20. ソートされた XNUMX つの配列を適切な位置で結合する方法。
配列 X[] と Y[] の項目 (それぞれサイズが m と n の XNUMX つの並べ替えられた配列) を、並べ替え順序を維持することによってマージします。つまり、X[] に最初の m 個の最小要素を埋め込み、Y[] に残りの要素を埋め込みます。
配列 X[] 内の要素がすでに正しい位置 (つまり、残りの要素の中で最も小さい要素) にある場合は、それを無視します。 それ以外の場合は、Y[] の最初のメンバーでもある最小の要素に置き換えます。 交換後にソートされた順序を保持するには、要素 (現在 Y[0] にあります) を Y[] 内の適切な場所に転送します。
最初の配列のサイズは m、XNUMX 番目の配列のサイズは n、時間計算量は O(mn) です。
21. 項目の配列を高い位置と低い位置に交互に並べ替えるにはどうすればよいですか?
後続の各メンバーが前後の要素より大きくなるように、整数配列を再配置します。 配列には重複する要素が含まれていないと仮定します。
効果的なアプローチには、配列をソートしたり、追加のスペースを利用したりする必要はありません。 この計画は、まず配列の XNUMX 番目のメンバーであり、ループ反復ごとに XNUMX つずつ増えていきます。
最後の要素が最初の要素を超える場合は、コンポーネントを交換します。 同様に、次の要素が現在の要素よりも大きい場合は、両方の項目を切り替えます。 ループの終了時に、指定された制限に準拠する目的の配列を取得します。
22. 除算演算子を使用せずに配列の各要素を配列の各要素の積に置き換えるにはどうすればよいですか?
除算演算子を使用せずに、整数配列内の各要素を他のすべての要素の積に置き換えます。
線形時間と一定空間では、再帰を利用してこの問題に対処できます。 右部分配列の各要素の積を再帰的に計算し、左部分配列の積を関数パラメーターとして渡すという概念です。
時間計算量は O(n) です。
23. 対数時間で配列内の最も奇数の要素を見つけます
XNUMX つを除くすべてのメンバーが偶数回出現する整数配列が与えられた場合、問題は、この XNUMX つの要素が何回出現するかを判断することです。 配列内で同じ要素がペアで出現し、行内に指定された要素のインスタンスが XNUMX つ以上存在できない場合、対数時間と定空間で奇数に出現する要素を見つけます。
XOR 演算を使用すると、この問題を線形時間で解決できます。 目標は、配列内のすべての要素を XOR することです。 偶数で発生する要素が互いに打ち消し合った後、奇数で発生する要素だけが残ります。
この問題は O(log(n)) 時間で解決することもできます。
24. 円形配列の各要素に対して後続のより大きな要素を取得するにはどうすればよいですか?
循環整数配列内の各要素の次に大きい要素を見つける必要があります。 配列内の要素 x の後の最初の大きい整数が、その要素の後続の大きい要素になります。
右から左に配列項目を操作できます。 目標は、スタックが空になるか、その上に上位の要素ができるまで、要素 x ごとにループすることです。 x の次に大きな要素がスタックの一番上に表示されるように設定します。
25. 配列の反転数を調べますか?
配列の反転の総数を求めます。 ペア I j) は、I j) かつ (A[i] > A[j]) の場合、配列 A の反転と呼ばれます。 配列内のこれらのすべてのペアを数えなければなりません。
その右側にある配列メンバーよりも小さい配列メンバーをすべて数えて、その結果を出力に追加するのが簡単な方法です。
このソリューションの複雑さは O(n2) です (n は入力のサイズです)。
26. 雨水の滞留問題とは何ですか?
それぞれ XNUMX 単位の幅を持つ特定のバーのセットに閉じ込めることができる最も多くの水を見つけることは、「トラップ降雨」問題として知られています。
目標は、各バーの左右に配置できる最も高いバーを決定することです。 左右の先頭のバーの最小値から現在のバーの高さを引いたものが、各バーの上に蓄えられている水の量となります。
まとめ
他のデータ構造トピックと比較して、配列は単純です。 配列面接の質問に答えるには、配列の基本を理解する必要があります。
配列の面接の質問にうまく答えるためには、配列操作 (配列の宣言/作成から配列項目へのアクセス/変更まで) や、ループ、再帰、基本的な演算子などのプログラミング概念を含む配列の基礎を徹底的に復習する必要があります。 問題を完全に認識します。
質問がある場合は、説明を求める必要があります。 問題をより管理しやすい部分に分割することを考えてください。 プログラミングを始める前に、必ずアルゴリズムを念頭に置いてください。 書き留めるか、フローチャートで視覚化します。 それからコードを書き始めます。
コメントを残す