Javaの就職面接。 コレクション

最近、私は専門能力の開発が非常に遅くなったと固く思っていました。 はい、本を読んで、コースを聴きますが、同時に、転職の時が来ているかもしれないという理解があります。ここですべてが研究されたようで、徐々にルーチンに移行しています。 このアイデアは、履歴書をいくつかの企業、つまり市場リーダーに送ることを私に促しました。 そのうち3人でインタビューを完了した後、5つのコペックをインタビューの広範なトピック、つまり私が対処しなければならないJavaコレクションの技術的な問題を取り上げる方法を決めました。 はい、私は知っています、読者は「コレクションは可能な限りハックされたトピックです」と言うでしょうが、モスクワから遠くない遠隔地の基準で開発者の位置を正確に占める開発者である私の知り合いに以下の質問の一部を尋ねました（「強い中間農民」）彼らは実際に自分の仕事に対処していますが、理論的にはギャップがあります。仕事にはいくつかの重要なタスクを解決する必要がないため、そして誰もがデータ構造がどのように機能するかを研究することに興味がないため、混乱が生じました。 議論された資料は、ジュニアレベル以上の開発者にとってあまり興味深いものではないと思います（ここで紹介した資料にコメント、補足、批判するようお願いします）が、Juniorはこの記事で自分自身にとって興味深いものになると確信しています。



率直に言って、インタビューの間、私は以下の質問のいくつかの答えを知りませんでしたが、ジュニアステージはすでに過ぎたようです。 これは、人事とのコミュニケーションから将来の活動の可能性に至るまですべてに共感が生じた企業のポジションがオファーを得ることができず、処理できないコレクションに関する質問があったという事実を考えると、二重に不快です彼らは否定的な貢献をした）。 しかし、インタビューの観点からすべてが非常にうまくいったところで、提案された活動分野と将来の同僚とのコミュニケーションは全体として否定的であり、「平凡」の法則はすべて栄光にあります。 その結果、このトピックでは、頭の中にあるギャップを埋めて、この知識を紙の上で体系化したいと思います。



この記事では、前回のインタビューで問題を引き起こした質問だけでなく、インタビューのすべての実践で求められた質問も検討します。 さて、質問に移る時が来たと思います。



1. ArrayListとLinkedListの違いは何ですか？



私のランキングでは、これはコレクションに関する2つの最も一般的な質問の1つであり、ケースの90％で尋ねています。 Junior Developerでの最初のインタビューで問題が発生しました。 つまり、この質問に対する答えは次のように要約されます。ArrayListは配列ベースのリストであり、LinkedListはそれらの間にリンクがあるオブジェクトに基づく古典的なリンクリストです。



ArrayListの利点：一定の時間（配列であるため）インデックスによって任意の要素にアクセスできる機能では、そのようなリストを保存するときのオーバーヘッドが最小限に抑えられ、リストの最後への挿入も一定の時間平均で実行されます。 平均して 、配列には特定の初期サイズn（コードではこれが容量パラメーター）があるため、デフォルトではn = 10で、n + 1要素を書き込むと、サイズ（n * 3）/ 2 + 1の新しい配列が作成され、古い配列のすべての要素が配置され、新しい要素が追加されます。 結果として、配列を拡張する必要がある場合に要素を追加すると、完成した空のセルに要素を書き込む場合よりも追加時間が長くなります。 ただし、平均して、リストの最後にあるアイテムの挿入時間は一定です。 最後のアイテムの削除は一定の時間で行われます。 リストの中央に要素を挿入/削除すると、ArrayListの欠点が現れます。これにより、リストの「右側」に配置されたすべての要素が左に1ポジション上書きされます。さらに、要素を削除すると、trimToSize（）メソッドが明示的に呼び出されるまで、配列のサイズは減少しません。



反対に、LinkedListは一定の時間リスト内の要素を挿入/削除できます（挿入と削除です。挿入と削除の位置の検索はここには含まれません）。 任意の要素へのアクセスは線形時間で実行されます（ただし、リストの最初と最後の要素へのアクセスは常に一定の時間で実行されます-リンクは常に最初と最後に保存されるため、リストの最後に要素を追加しても、最後を検索してリスト全体を反復する必要はありませんアイテム）。 一般に、LinkedListは絶対的な意味で、メモリ消費と操作速度の両方でArrayListを失います。 LinkedListは、リストの中央でアクティブな作業（挿入/削除）がある場合、またはリストにアイテムを追加するために保証時間が必要な場合に使用することが好ましい。



詳細なトレーニングと同時にエクスプレストレーニングについては、 ArrayListとArrayListに関する素晴らしい記事を読むことを強くお勧めします。 コレクションによるメモリ消費に関するlanyの記事もお勧めします- 非常に有益です。



2.通常は何を使用しますか（ArrayListまたはLinkedList）？ なんで？



この質問への回答は、前の質問への回答の段階的な提示につながるため、この質問は、前の質問の少し変装したバージョンです。 90％の場合、ArrayListはLinkedListよりも高速で経済的であるため、通常はArrayListを使用しますが、LinkedListの場合は常に10％の場合があります。 前の質問のテストと最後の段落を参照して、通常ArrayListを使用すると言いますが、LinkedListを忘れないでください（どのような場合ですか？また、前の質問の最後の段落が役立ちます）。



3. ArrayListまたはLinkedListよりも高速なものは何ですか？



最初の質問の別の変装バージョン。 上記のオプションよりも難しいのは、質問することは提案されたオプションのいずれかを選択する単音節の答えを意味することであり、私は理解しているように、コレクションの浅い知識を持つ人をすぐに特定する必要があります。 正しいアクションは、構造上で実行されるアクションの反対の質問になります。 その結果、ダイアログはスムーズに進み、最初の質問に答えます。



4. 100万を追加する必要があります。 要素、どの構造を使用していますか？



また、最初の質問の非常に人気のある隠されたバージョン。 また、ステートメントには提案されたオプションの1つを選択することが含まれますが、実際には明確な選択に関する情報はありません。 追加の質問をする必要があります：リストのどの部分にアイテムが追加されますか？ リスト項目の横に何が起こるかについての情報はありますか？ メモリまたは実行速度に制限はありますか？ 一般に、これは最初の質問と同じですが、少し異なる側面があります。追加の質問を通して、配列とリンクリストの作業の理解の深さを示します。

私がこのフックを「つついて」、リストの最後に「挿入」してArrayListを集中的に推進することを自分に考えてみましたが、このリストでのさらなるアクションと可能な制限については知りませんでした（見つけようとしませんでした）。



5. ArrayListから要素はどのように削除されますか？ この場合、ArrayListのサイズはどのように変わりますか？



繰り返しますが、質問1の答えには、この質問の答えが含まれています。 リストから任意の要素を削除すると、「右」にあるすべての要素が1セル左にシフトされ、配列の実際のサイズ（容量、容量）はまったく変化しません。 配列の自動「拡張」のメカニズムがありますが、自動「圧縮」はありません。trimToSize（）コマンドで明示的に「圧縮」を実行することしかできません。



6. ArrayListによって実装されたリストの中央からいくつかの隣接する要素を削除するための効果的なアルゴリズムを提案します。



私の標準では、ArrayListから要素を削除するメカニズムがわからなかったときに一度だけ会った、途切れのない質問です。 その結果、それは私に深刻な困難を引き起こしました。 実際、1つの要素がどのように削除されるかを知っていれば、すべてが非常に単純で明白です。 リストの位置mからn個の要素を削除するとします。 1つの要素をn回削除する代わりに（リストの「右」にある要素を1つずつシフトするたびに）、n + m位置の「右」にあるすべての要素をリストの左にn要素だけ左にシフトする必要があります。 したがって、リスト項目の移動をn回繰り返す代わりに、すべてが1パスで行われます。



7. HashMapはどのように配置されますか？



これは、最も人気のあるコレクションの質問のリストの2番目です。 この質問が私に聞かれない場合があったかどうかさえ覚えていません。



要するに、HashMapは「バスケット」で構成されています。 技術的な観点から見ると、「バスケット」は要素のリストへのリンクを格納する配列要素です。 新しいキーと値のペアを追加すると、キーのハッシュコードが計算され、それに基づいて、新しい要素が取得されるバスケット番号（配列のセル番号）が計算されます。 バスケットが空の場合、新しく追加された要素へのリンクがその中に保存され、既に要素が存在する場合、リンクは、新しく追加された要素へのリンクが配置される最後の要素を探して、チェーン内の要素間を順番にたどります リスト内で同じキーを持つアイテムが見つかった場合、それは置き換えられます。 要素の追加、検索、削除は一定の時間で実行されます。 すべてがうまくいくように思えますが、1つの注意点があります。ハッシュ関数は、バスケット全体に要素を均等に分散する必要があります。この場合、これらの3つの操作の時間の複雑さはlog Nより低くなく、平均的な場合は一定の時間です。



一般に、この答えは提起された質問には十分であり、プロセスと繊細さを深く理解した上で、HashMapダイアログが開始される可能性が高いです。



繰り返しますが、 tarzan82のHashMapの記事を読むことをお勧めします。



8. HashMap内のバスケットの初期数はいくつですか？



予想外の質問ですが、彼はかつて、デフォルトコンストラクターを使用するときにバスケットの数を推測させました。



ここでの答えは16です。答えとして、パラメーターを持つコンストラクターを使用することは可能です。容量パラメーターを使用して、バスケットの初期数を設定します。



9. HashMapからアイテムを選択する時間の複雑さの推定値はどのくらいですか？ HashMapは、指定された要素の取得の複雑さを保証しますか？



質問の最初の部分の答えは質問7の答えにあります。要素を選択するには一定の時間が必要です。 ここで質問の2番目の部分で、私は最近混乱しました。 そして、HashMapデバイスはハッシュ関数についても知っていましたが、そのような質問に対応する準備はできていませんでした。一般に他の方向に急ぎ、HashMapの構造に集中し、ハッシュコードの問題を捨てました。配布。 実際、答えは非常に単純であり、質問7の回答から続きます。



常に同じ値を返すハッシュ関数を使用すると、HashMapは不快なパフォーマンスでリンクリストになります。 一様分布のハッシュ関数を使用した場合でも、極端な場合、log Nの時間の複雑さのみが保証されるため、質問の2番目の部分に対する答えはnoであり、保証されません。



10. HashMapでのequalsとhashCodeの役割は？



この質問への回答は質問7への回答から得られますが、明確に記述されていません。 hashCodeを使用すると、バスケットを定義して要素を検索でき、equalsを使用して、バスケット内のリスト内の要素のキーと検索するキーを比較します。



11. hashCode（）値の最大数は？



ここでは、すべてが非常に単純で、メソッドのシグネチャを思い出してください：int hashCode（）。 つまり、値の数はint型の範囲-2 ^ 32に等しくなります（正確な範囲は尋ねられず、そのような答えで十分でした）。



12. HashMapのバスケットの数はいつ、どのように増加しますか？



これは非常に微妙な質問です。 私のミニ調査が示したように、HashMapデバイスの本質が多かれ少なかれ明確に理解されている場合、この質問は対話者をしばしば混乱させました。



容量に加えて、HashMapにはloadFactorパラメーターもあり、これに基づいてビジーバスケットの最大数が計算されます（capacity * loadFactor）。 デフォルトでは、loadFactor = 0.75です。 制限値に達すると、バスケットの数が2倍に増えます。 保管されているすべてのアイテムについて、新しい「場所」は、バスケットの新しい数を考慮して計算されます。



13.どのような場合、HashMapで要素が失われますか？



この興味深い質問は、 LeoCcoderから送られてきました。彼らはそのようなことを聞​​かなかったので、すぐに読んだ後、要素を失うためのスクリプトを思い付かなかったことを正直に認めます。 それほど明確ではありませんが、すべてが再び非常に単純であることが判明しました。たとえば、キーがプリミティブではなく、いくつかのフィールドを持つオブジェクトであるとしましょう。 HashMapに要素を追加すると、キーとして機能するオブジェクトは、ハッシュコードの計算に関係する1つのフィールドを変更します。 その結果、ソースキーでこの要素を見つけようとすると、正しいバスケットにアクセスしますが、等しい（結局、等しい、hashCodeは同じフィールドセットで動作する必要があります）要素のリストで指定されたキーを見つけられません。 それでも、オブジェクトの指定されたフィールドを変更しても結果に影響しないようにequalsが実装されている場合でも、バスケットのサイズを増やして要素のハッシュコードを再計算した後、変更されたフィールド値を持つ指定された要素は完全に異なるバスケットになりますそして彼は完全に失われます。



14.バイト[]をHashMapのキーとして使用できないのはなぜですか？



LeoCcoderからの別の質問。 いつものように、すべてが非常にシンプルであることが判明しました-配列のハッシュコードは、格納されている要素に依存しませんが、配列の作成時に割り当てられます（配列のハッシュコードの計算方法はオーバーライドされず、配列のアドレスに基づいて標準のObject.hashCode（）を使用して計算されます） また、配列は等号をオーバーライドせず、ポインター比較を実行します。 これは、同じサイズおよび同じ要素の別の配列を使用する場合、配列キーで保存された要素にアクセスできないという事実につながります。アクセスは1つの場合にのみ実行できます-保存に使用した同じ配列参照を使用する場合アイテム。 この質問に対する回答については、ユーザー@dark_dimiusに特別な感謝をします。



15. TreeSetとHashSetの違いは何ですか？



まず、Setはセットです（「セット」とも呼ばれます）。 セットでは、2つの同一の要素を保存できません。 正式に言えば、用語「multitude」は異なる要素の集合を意味するため、異なる要素であることは非常に重要です。これはSetの主要なプロパティだからです。 この定義を考えると、同一の要素の保存に関する説明は必要ありませんが、日常生活では、「セット」の概念はそれに含まれる要素の一意性に関する厳密な意味を失いました。それにもかかわらず、セットのこのプロパティを個別に指定します。



TreeSetは、赤黒木の形で要素の規則正しいストレージを提供します。 TreeSet lg Nで基本操作を実行する複雑さ。HashSetはHashMapと同じ方法を使用して要素を格納しますが、HashSetでキーとして機能する点が異なります。さらに、HashSet（HashMapなど）はHashMapのような操作の一時的な複雑さを提供します。



16. TreeSetデバイス？



この質問は質問14の代わりに尋ねられ、ここではTreeSetが赤黒木に基づいているというかなり短い回答を示します。 原則として、これで十分であり、対話者はすぐに次の質問に進みます;ツリーまたはその実装の他の詳細のバランスをとるメカニズムを尋ねられたことはありません。



赤と黒の木の知識を深めるために、 この記事をお勧めします 。



17. TreeSetにアイテムを昇順で追加するとどうなりますか？



通常、対話者はこの質問の前に、TreeSetがバイナリツリーに基づいているというフレーズを使用し、昇順で要素を追加する場合、ツリー全体にどのように要素を分散するかを指定します。



TreeSetデバイスについて正確な考えがないが、これがバイナリツリーであるという一般的な理解がある場合（対話者はさらに保証します）、この質問は興味深い結果につながる可能性があります：通常のバイナリツリーに追加した後、すべての要素は同じブランチになりますN要素の長さ。これは、ツリーなどの構造のすべての利点を無効にします（実際には、リストが取得されます）。 実際、上で述べたように、TreeSetの基礎はそれ自体のバランスを取ることができる赤黒木です。 その結果、TreeSetは要素を追加する順序を気にしません。このデータ構造の利点は保持されます。



おわりに



議論された質問がhabrayuzerに役立つことを願っています。 また、上記の質問にはこのような詳細な検討が必要であるという素朴さを許してください。しかし、やがて同様の記事が真剣に役立つでしょう。 記事には間違いがあると確信しています-コメントをお願いします。さらに、コメントの経験豊富な仲間が実践からの質問を積極的に共有し、記事がhabrasocietyに好意的に受け取られれば、Javaインタビューの技術的な問題のレビューを続けることができることを願っています。



PSちょっとした商業的関心：新しい仕事の検索は継続されます。もしhabrayuzersの1人が、開発や興味深いタスクに最新のアプローチをしている会社でJava開発者を検索している場合、または適切な空席を詳しく調べることをお勧めするかもしれません-感謝しますPM。