スキップリスト: エクスプレスレーンとコイントス (AI エンジニアのコーディングインタビュー)

第一原則からのスキップリスト。各駅に停車する電車に乗っていると、停車駅はずっと先になります。単純に言えば、数値を並べ替えておいて、どれか 1 つをすばやく見つけて追加または削除します。ソートされたリンク リストは簡単に挿入しますが、一度に 1 つのノードを検索します。ソートされた配列は高速に検索しますが、挿入するたびにシフトします。スキップ リストは、ソートされたリンク リスト上にまばらなエクスプレス レーンを積み重ねます。検索は左上から開始され、次のキーが大きすぎない間に右に移動し、オーバーシュートする可能性があるときにレーンをドロップします。また、コイン投げによって新しいキーに高さが与えられるため、リバランスは発生しません。 9 に対して 5 ステップで 52 の検索、10 に対して 6 ステップでの不在検索、およびタワーを 2 つのレーンに接続するコイントスによる 35 の挿入を追跡します。約 2 log n ステップが必要な理由がわかり、不運なコイン、重複キー、レーンや無制限の高さを逃した削除による破壊が発生し、正直なコストがわかります。予想される log n 検索、挿入と削除、キーごとに約 2 つのポインタ、およびシード実行による 100 万個のキーの場合、約 20 レーン、平均約 38 ステップ、最悪の場合は 70 ステップで、プレーン リストの平均 50 万ステップです。バランスのとれたツリー、ソートされた配列とハッシュ テーブル、Redis ソート セットでの使用、RocksDB と LevelDB の memtable、キューとレート リミッター、順序付けされたスキャン、ランダム性、キャッシュの動作、練習ページに対するトレードオフ。構造の 3 番目の段にはデータベースがはしごを出荷します。 AI エンジニアのコーディング ラウンド向けに構築されました。サイトで自分で練習してください (無料、ブラウザで実行できます): https://vibeengines.com/algorithm/skip-list このページには、シミュレーター、非表示のテストを含むコーディング タスク、ヒント、完全な説明が含まれています。各章 0:00 質問: ソートされ、検索、追加、削除が高速 0:50 ブルート フォース: リンクされたリストとソートされた配列 1:19 アイデア: レーンの高速化、右からドロップ、コイン投げ 1:59 トレース検索と 10 キーによる挿入 3:02 log n ステップと回転なしの理由 3:34 打破: アンラッキー コイン、削除、高さ制限 4:21 ライブ状態のコード4:48 100万個のキーを使用した時間と空間の詳細 5:53 トレードオフ: バランスのとれたツリー、ソートされた配列、ハッシュ テーブル 6:35 AI システムのどこに存在するか 7:06 エッジ ケース: スキャン、ランダム性、キャッシュ、空のリスト 7:45 Vibe エンジンで実践する データベースがサイトに出荷する構造の 3 段目: B ツリー、LSM ツリー、スキップ リスト、ピース テーブル、および一貫性のあるハッシュ。 #skiplist #データ構造 #アルゴリズム #redis #aiエンジニア #システム設計インタビュー #コーディングインタビュー