特定の挿入と削除を伴うユーザー定義コレクションの正しいアルゴリズムとデータ構造

Question

この質問は投資銀行のインタビューの1つで尋ねられます。 私はstudentRecordsオブジェクトのキャッシュを保持するmyCacheを設計しなければならず、studentRecordsコレクションのmyCacheの1つのオブジェクトを持つことができます。ユーザーがstudentRecordsにレコードを挿入したい場合、コレクションに20レコード未満であればレコードを挿入します。 studentRecordsから最も使用されていないレコードを削除し、レコードを挿入します。レコードはソートされた順序でstudentRecordsの順位に基づいて挿入されます。ユーザーがレコードを読みたい場合は、studentRecordsがmyCacheに存在するかどうかをチェックし、 studentRecordsコレクションから。

二重リンクリストを作成し、ランキングに基づいてレコードを挿入しました。また、シングルトンであるmycacheクラスを作成し、キャッシュからレコードを読み込むこともできます。

レコードを削除する配列リストを作成することはできますが、配列の中で最も使用頻度の低いレコードですが、ランクの順序に基づいて要素を保持することはできません。ランキングに基づいてレコードを読み込むことは高価です。

面接官に感銘を受けた他の解決策はありますか？ 80 90 160 80
sohan StudentRecords

SrNoランク名数学科学総パーセンテージ
1ロアン90 90 180 90
2 2の

 public void removeRecordFromStudentRecords(String rank); 
     public void addRecordToStudentRecords(StudentRecords st); 
     public Student readRecordFromStudentRecords(String rank); 

表：

MyCacheというクラスのような機能を有します 3 3 abhi 70 70 140 70

Answer 1

最も使用されていないレコードを記録するには、各レコードが持つヒット数を保存する（「ヒット」が何であるか分からない場合は、「ヒットとキャッシュのミス」を参照することをお勧めします）。したがって、各studentRecordは次のようにクラスのオブジェクトになります。

class StudentRecord{ 
    int unique_id; 
    int ranking; 
    int hits 
} 
StudentRecord studentRecord = new StudentRecord(); 

studentRecord.rankingに基づいてキャッシュをソートし、削除するstudentRecordを決定する必要がある場合は、ヒットに基づいてキャッシュをトラバースし、最小ヒットの要素を削除するだけです。

あなたは、あなたがこのように1によって、そのヒットをインクリメントそのUNIQUE_IDに基づいてstudentRecordのクエリを取得するたびに、ヒットを維持するために、あなたにstudentRecordが最も使用されているのメトリックを与えるヒット/最低使用

編集：あなたの質問ははるかに明確になりました。並べ替えの場合、簡単な挿入並べ替えを使用できます。これは、1）キャッシュに最大20個の要素があり、2）新しい要素を挿入して挿入しようとすると、要素を配置できるインデックスを完全に見つけることができます。実際、技術的に言えば、ソートは1回だけ必要です。次に、将来の要素をどこに挿入するかを判断するだけです。

私は、java.util.ArrayListのような任意のアクセス権を持つ簡単なリンクリストで十分です。それは配列のようなランダムアクセスと、20個未満の要素を収容するための規定を与えるでしょう。ここで要素の左と右の隣人にアクセスする必要がないので、二重にリンクされたリストを作る理由はありません。

Answer 2

ここでは最近使用されたスケジューリング手法を適用することができます。あなたのリストに。

オブジェクトのエントリが使用されるたびに、1をバイト（b >> 1）にプッシュできます。

したがって、頻繁に使用されているエントリの場合、バイトのバイナリ表現では1が大きくなります。

データの場合、まったく使用されず、すべて0になります。

毎回、キャッシュからエントリを削除する必要があります.0またはこのバイトフィールドの最小値を持つエントリを削除するだけです。

さらに、8よりも長い期間の参照を覚えておくと、より大きなデータ型を使用できます。

Answer 3

キャッシュについては、時間の複雑さを最優先に最適化し、後でメモリを最適化する必要があります。

• 使用Map（すなわち、ハッシュマップ）を格納するレコード（key: recordId, value: Record）用：

  したがって、この場合には、私は次の解決策を提供することができます。

• 最後に使用したアイテム（value: recordId）にはStackを使用してください。
• ランク（key: rankValue, value: recordId）を保持するのにTree（すなわちBST）を使用します。

このツリーデータ構造を組み合わせることで、最も速い解決策（私が推測する）を提供することができます。

• は、ID操作で読む：O（1） - 地図から単純なGET
• レコード操作追加：O（LN N）を - 私たちは（ツリーにキーを挿入する必要があるため、我々はに均衡含まれていません。
• ）complaxityをカウントすると、ランク操作によって削除：O（LN N） - 単にツリーにランクレコードIDを見つける（スタックから地図とレコードIDからレコードを削除することを忘れないでください）

をこれはちょうど簡単な概要です問題。推測すると、主なアイデアを理解するのに十分な情報です。