Temu Duga Pengekodan: Bagaimana Anda Melaksanakan Skip List dengan Search, Insert, dan Delete?

Gesaan dan skop

Laksanakan set tertib kunci integer dengan search, insert, dan delete. Struktur ini harus menggunakan operasi jangkaan O(log n) dan mengelakkan putaran yang diperlukan oleh balanced tree. Nyatakan sama ada pendua ditolak atau dikira; artikel ini memilih set, jadi memasukkan kunci sedia ada ialah no-op.

Soalan ini muncul dalam laporan temu duga awam dan perbincangan pelaksanaan, termasuk gesaan temu duga Google dan siaran temu duga LeetCode. Isyarat pengekodan adalah mengekalkan berbilang tahap forward-pointer dan membuktikan invariantnya, bukan menghafal kelas pustaka.

Perkara yang dinilai oleh penemu duga

• Sama ada anda mengekalkan tahap sifar sebagai senarai tersusun lengkap dan setiap tahap yang lebih tinggi sebagai suburutan daripadanya.
• Sama ada penyisipan dan pemadaman mengemas kini setiap tahap pendahulu (predecessor) tanpa kehilangan pautan senarai asas.
• Sama ada anda membezakan jangkaan O(log n) daripada operasi O(n) yang malang dan menguji sempadan tahap rawak.

Redis menggunakan perwakilan skip-list untuk satu pengekodan sorted-set, manakala nota algoritma MIT menerangkan analisis kebarangkaliannya. Itu adalah bukti pelaksanaan dan teori; ia tidak membayangkan bahawa setiap beban kerja perlu menggantikan tree dengan skip list.

Penjelasan sebelum menjawab

1. Set atau multiset? Set menolak kunci pendua; multiset memerlukan kiraan atau identiti nod yang unik.
2. Adakah pemanggil memerlukan pertanyaan pangkat (rank) atau julat? Pangkat memerlukan metadata rentang (span) atau lebar; soalan asas hanya memerlukan keahlian.
3. Adakah tayangan semula deterministik diperlukan? Suntik sumber rawak berbenih (seeded) untuk ujian, manakala pengeluaran menggunakan penjana tidak berat sebelah.
4. Apakah had memori? Setiap nod mempunyai bilangan forward pointer yang berubah-ubah, jadi had tahap dan kebarangkalian mempengaruhi memori.

Jawapan 30 saat

“Saya mengekalkan sentinel dengan forward pointer untuk setiap tahap dan senarai tahap sifar yang tersusun. Carian bermula pada tahap tertinggi dan bergerak ke hadapan selagi kunci seterusnya lebih kecil; ia merekodkan pendahulu terakhir pada setiap tahap. Insert memilih ketinggian rawak, menyambung nod baharu selepas pendahulu tersebut, dan tidak melakukan apa-apa untuk kunci sedia ada. Delete menggunakan tatasusunan pendahulu yang sama dan memutuskan pautan sasaran pada setiap tahap di mana ia muncul, kemudian menurunkan ketinggian aktif apabila senarai teratas menjadi kosong. Dengan kebarangkalian ketinggian geometri, carian, penyisipan, dan pemadaman adalah jangkaan O(log n) dan ruang adalah jangkaan O(n); jujukan rawak patologi masih boleh mengambil masa O(n).”

Jawapan mendalam langkah demi langkah

Langkah 1: Tentukan invariant.

Tahap sifar mengandungi setiap kunci dalam susunan strictly increasing. Tahap i + 1 ialah suburutan tahap i, dan forward pointer setiap nod disusun mengikut kunci. Sentinel mempunyai penunjuk MAX_LEVEL dan tiada kunci pengguna. Tahap aktif ialah senarai tertinggi yang tidak kosong.

Langkah 2: Cari sambil mengumpul pendahulu.

Mula pada tahap aktif tertinggi sentinel. Bergerak ke hadapan selagi nod seterusnya wujud dan kuncinya kurang daripada sasaran. Turun satu tahap dan teruskan. Simpan nod terakhir yang dilawati dalam update[i]; selepas tahap sifar, update[0].next[0] adalah sama ada sasaran atau kedudukan penyisipannya.

Langkah 3: Sisipkan dengan ketinggian rawak.

Dapatkan ketinggian geometri, contohnya dengan menaikkan tahap secara berulang dengan kebarangkalian p = 1/2, dihadkan pada MAX_LEVEL. Jika calon pada tahap sifar mempunyai kunci tersebut, kembalikan false. Untuk setiap tahap di bawah ketinggian baharu, tetapkan penunjuk nod baharu kepada penunjuk seterusnya pendahulu, kemudian halakan pendahulu pada nod baharu. Luaskan tahap aktif jika perlu.

type Node = { key: number; next: Array<Node | null> };

class SkipSet {
  private readonly maxLevel = 16;
  private readonly head: Node = { key: Number.NEGATIVE_INFINITY, next: [] };
  private level = 1;

  constructor() {
    this.head.next = Array(this.maxLevel).fill(null);
  }

  private randomLevel(): number {
    let h = 1;
    while (h < this.maxLevel && Math.random() < 0.5) h += 1;
    return h;
  }

  search(key: number): boolean {
    let node = this.head;
    for (let i = this.level - 1; i >= 0; i -= 1) {
      while (node.next[i] && node.next[i]!.key < key) node = node.next[i]!;
    }
    return node.next[0]?.key === key;
  }

  insert(key: number): boolean {
    const update = Array<Node>(this.maxLevel);
    let node = this.head;
    for (let i = this.level - 1; i >= 0; i -= 1) {
      while (node.next[i] && node.next[i]!.key < key) node = node.next[i]!;
      update[i] = node;
    }
    if (update[0].next[0]?.key === key) return false;
    const height = this.randomLevel();
    if (height > this.level) {
      for (let i = this.level; i < height; i += 1) update[i] = this.head;
      this.level = height;
    }
    const fresh: Node = { key, next: Array(height).fill(null) };
    for (let i = 0; i < height; i += 1) {
      fresh.next[i] = update[i].next[i];
      update[i].next[i] = fresh;
    }
    return true;
  }

  delete(key: number): boolean {
    const update = Array<Node>(this.maxLevel);
    let node = this.head;
    for (let i = this.level - 1; i >= 0; i -= 1) {
      while (node.next[i] && node.next[i]!.key < key) node = node.next[i]!;
      update[i] = node;
    }
    const target = update[0].next[0];
    if (!target || target.key !== key) return false;
    for (let i = 0; i < this.level; i += 1) {
      if (update[i].next[i] !== target) break;
      update[i].next[i] = target.next[i] ?? null;
    }
    while (this.level > 1 && !this.head.next[this.level - 1]) this.level -= 1;
    return true;
  }
}

Langkah 4: Padamkan setiap kemunculan nod sasaran.

Tatasusunan pendahulu mengenal pasti pendahulu sasaran pada setiap tahap. Putuskan pautan hanya pada tahap di mana update[i].next[i] ialah sasaran tersebut; tahap yang lebih tinggi mungkin tidak mengandunginya. Selepas itu, kurangkan tahap aktif selagi penunjuk teratas sentinel kosong.

Langkah 5: Analisis kekompleksan dan memori.

Dengan kebarangkalian kenaikan tahap p secara ketat antara sifar dan satu, ketinggian jangkaan adalah malar dan panjang laluan carian jangkaan adalah logaritma. Carian, penyisipan, dan pemadaman adalah jangkaan O(log n); jujukan rawak yang buruk mempunyai kes terburuk O(n). Bilangan penunjuk jangkaan ialah n/(1-p) sehingga pemalar, jadi p = 1/2 menukar kira-kira dua penunjuk bagi setiap nod untuk laluan yang lebih pendek.

Langkah 6: Uji struktur, kerawakan, dan sempadan.

Gunakan penjana berbenih dalam ujian. Periksa carian/padam kosong, kunci pertama dan terakhir, pendua, memadamkan satu-satunya nod, memadam merentasi tahap, nilai negatif, dan kitaran insert/delete berulang. Selepas setiap operasi, lintasi tahap sifar dan bandingkan dengan rujukan Set; sahkan setiap tahap yang lebih tinggi disusun dan setiap nod juga muncul pada tahap sifar. Jalankan banyak benih untuk mengesan kerosakan ketinggian dan penunjuk.

Contoh jawapan berkualiti tinggi

“Saya memodelkan set dengan sentinel dan rantai tahap sifar yang tersusun. Setiap tahap yang lebih tinggi ialah suburutan tahap sifar. Search turun dari tahap aktif tertinggi dan merekodkan pendahulu pada setiap tahap. Insert menolak kunci sedia ada, memilih ketinggian rawak geometri, dan menyambung nod selepas pendahulu tersebut. Delete mencari tatasusunan pendahulu yang sama, memutuskan pautan sasaran dari setiap tahap di mana ia muncul, dan memangkas tahap teratas yang kosong.

Operasi ini adalah jangkaan O(log n) dengan ruang jangkaan O(n), tetapi masa kes terburuk O(n) masih boleh berlaku apabila ketinggian rawak tidak bernasib baik. Saya akan menggunakan sumber rawak berbenih untuk ujian deterministik, membandingkan tahap sifar dengan set rujukan selepas setiap operasi, dan menegaskan keteraturan serta invariant suburutan untuk semua tahap atas.”

Kesilapan biasa

• Hanya mengemas kini tahap sifar → carian tahap atas boleh melangkau atau mengekalkan kunci → sambung atau putuskan pautan setiap tahap yang mengandungi nod.
• Menganggap ketinggian rawak sebagai jaminan → jujukan patologi boleh menghasilkan laluan linear → nyatakan batas jangkaan dan kes terburuk.
• Membenarkan nod pendua secara tidak sengaja → semantik carian dan pemadaman menjadi kabur → pilih kelakuan set atau multiset sebelum mengekod.
• Gagal memangkas tahap teratas yang kosong → carian memeriksa tahap lapuk dan simpan kira terpesong → turunkan tahap aktif selepas pemadaman.
• Hanya menguji keahlian akhir → penunjuk atas yang rosak boleh kekal tersembunyi → semak keteraturan dan invariant suburutan selepas setiap operasi.

Soalan susulan dan respons

Soalan susulan 1: Bagaimana anda akan menyokong kunci pendua?

Pilih kontrak. Multiset boleh menyimpan kiraan dalam setiap nod kunci, menjadikan insert dan delete berulang mengemas kini kiraan tersebut, atau menyimpan nombor jujukan unik dalam kunci perbandingan. Kira nod apabila memori mengizinkan; identiti unik berguna apabila memadamkan satu kemunculan tertentu.

Soalan susulan 2: Bagaimana anda menambah pertanyaan pangkat (rank)?

Simpan rentang (span) atau lebar di sebelah setiap forward pointer. Semasa carian, kumpulkan rentang semasa anda bergerak ke kanan; penyisipan dan pemadaman mengemas kini rentang yang terjejas pada setiap tahap. Pelaksanaan set mudah tidak mempunyai metadata yang mencukupi untuk menjawab pertanyaan pangkat dalam masa logaritma.

Soalan susulan 3: Bilakah anda akan memilih balanced tree sebagai ganti?

Gunakan balanced tree apabila batas kes terburuk, bentuk lelaran deterministik, atau operasi tertib yang kaya lebih penting daripada kesederhanaan pelaksanaan. Skip list sesuai apabila prestasi logaritma jangkaan, varian serentak yang mudah, atau indeks tertib berasaskan penunjuk boleh diterima. Ukur overhed memori dan beban kerja berbanding mendakwa satu struktur secara universal lebih pantas.