Wawancara Coding: Bagaimana Cara Mengimplementasikan Skip List dengan Search, Insert, dan Delete?

Petunjuk dan cakupan

Implementasikan himpunan berurutan (ordered set) dari kunci integer dengan search, insert, dan delete. Struktur ini harus menggunakan operasi dengan expected O(log n) dan menghindari rotasi yang diperlukan oleh balanced tree. Nyatakan apakah duplikat ditolak atau dihitung; artikel ini memilih sebuah set, sehingga memasukkan kunci yang sudah ada adalah operasi no-op.

Pertanyaan ini muncul dalam laporan wawancara publik dan diskusi implementasi, termasuk soal wawancara Google dan postingan wawancara LeetCode. Sinyal pengkodean yang dinilai adalah pemeliharaan beberapa level forward-pointer dan pembuktian invariannya, bukan menghafal kelas pustaka.

Hal yang dievaluasi pewawancara

• Apakah Anda mempertahankan level nol sebagai daftar terurut lengkap dan setiap level yang lebih tinggi sebagai subsekuensi darinya.
• Apakah penyisipan dan penghapusan memperbarui setiap level pendahulu (predecessor) tanpa memutus tautan pada daftar dasar.
• Apakah Anda membedakan expected O(log n) dari operasi O(n) yang tidak beruntung dan menguji batas level acak.

Redis menggunakan representasi skip-list untuk salah satu pengodean sorted-set, sementara catatan algoritma MIT menjelaskan analisis probabilistiknya. Itu adalah bukti implementasi dan teori; hal tersebut tidak menyiratkan bahwa setiap beban kerja harus mengganti tree dengan skip list.

Klarifikasi sebelum menjawab

1. Set atau multiset? Set menolak kunci duplikat; multiset memerlukan penghitung (count) atau identitas simpul unik.
2. Apakah pemanggil membutuhkan kueri rank atau rentang? Rank memerlukan metadata rentang (span) atau lebar; pertanyaan dasar hanya membutuhkan pemeriksaan keanggotaan.
3. Apakah diperlukan pemutaran ulang yang deterministik? Suntikkan sumber acak ber-seed untuk pengujian, sementara produksi menggunakan generator yang tidak bias.
4. Berapa batas memorinya? Setiap simpul memiliki jumlah forward pointer yang bervariasi, sehingga batas level dan probabilitas memengaruhi memori.

Jawaban 30 detik

“Saya mempertahankan sentinel dengan forward pointer untuk setiap level dan daftar level-nol yang terurut. Pencarian dimulai dari level tertinggi dan bergerak maju selama kunci berikutnya lebih kecil; pencarian mencatat pendahulu terakhir di setiap level. Insert memilih tinggi acak, menyambungkan simpul baru setelah pendahulu tersebut, dan tidak melakukan apa pun untuk kunci yang sudah ada. Delete menggunakan array pendahulu yang sama dan memutus tautan target di setiap level tempat ia muncul, lalu menurunkan tinggi aktif saat daftar teratas menjadi kosong. Dengan probabilitas tinggi geometrik, search, insert, dan delete memiliki expected O(log n) dan ruang expected O(n); urutan acak yang patologis masih dapat memakan waktu O(n).”

Jawaban mendalam langkah demi langkah

Langkah 1: Tentukan invarian.

Level nol berisi setiap kunci dalam urutan strictly increasing. Level i + 1 adalah subsekuensi dari level i, dan forward pointer setiap simpul diurutkan berdasarkan kunci. Sentinel memiliki MAX_LEVEL pointer dan tidak memiliki kunci pengguna. Level aktif adalah daftar tertinggi yang tidak kosong.

Langkah 2: Cari sambil mengumpulkan pendahulu.

Mulai dari level aktif tertinggi milik sentinel. Bergerak maju selama simpul berikutnya ada dan kuncinya lebih kecil dari target. Turun satu level dan lanjutkan. Simpan simpul terakhir yang dikunjungi di update[i]; setelah level nol, update[0].next[0] adalah target atau posisi penyisipannya.

Langkah 3: Sisipkan dengan tinggi acak.

Ambil tinggi geometrik, misalnya dengan mempromosikan berulang kali dengan probabilitas p = 1/2, dibatasi pada MAX_LEVEL. Jika kandidat pada level nol memiliki kunci tersebut, kembalikan false. Untuk setiap level di bawah tinggi baru, atur pointer simpul baru ke pointer berikutnya milik pendahulu, lalu arahkan pendahulu ke simpul baru. Perluas level aktif jika diperlukan.

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: Hapus setiap kemunculan simpul target.

Array pendahulu mengidentifikasi pendahulu target di setiap level. Putuskan tautan hanya pada level di mana update[i].next[i] adalah target tersebut; level yang lebih tinggi mungkin tidak memuatnya. Setelah itu, kurangi level aktif selama pointer teratas milik sentinel kosong.

Langkah 5: Analisis kompleksitas dan memori.

Dengan probabilitas promosi p secara ketat antara nol dan satu, tinggi yang diharapkan bernilai konstan dan panjang jalur pencarian yang diharapkan bernilai logaritmik. Search, insert, dan delete memiliki expected O(log n); urutan acak yang buruk memiliki worst case O(n). Jumlah pointer yang diharapkan adalah n/(1-p) hingga batas konstanta, sehingga p = 1/2 menukar sekitar dua pointer per simpul untuk jalur yang lebih pendek.

Langkah 6: Uji struktur, keacakan, dan nilai batas.

Gunakan generator ber-seed dalam pengujian. Periksa search/delete pada struktur kosong, kunci pertama dan terakhir, duplikat, menghapus satu-satunya simpul yang ada, menghapus di lintas level, nilai negatif, dan siklus insert/delete berulang. Setelah setiap operasi, telusuri level nol dan bandingkan dengan referensi Set; verifikasi bahwa setiap level yang lebih tinggi terurut dan setiap simpul juga muncul di level nol. Jalankan banyak seed untuk mendeteksi kerusakan tinggi dan pointer.

Contoh jawaban berkualitas tinggi

“Saya memodelkan set dengan sentinel dan rantai level-nol yang terurut. Setiap level yang lebih tinggi adalah subsekuensi dari level nol. Search turun dari level aktif tertinggi dan mencatat pendahulu di setiap level. Insert menolak kunci yang sudah ada, memilih tinggi acak geometris, dan menyambungkan simpul setelah pendahulu tersebut. Delete menemukan array pendahulu yang sama, memutus tautan target dari setiap level tempat ia muncul, dan memangkas level teratas yang kosong.

Operasi-operasi tersebut memiliki expected O(log n) dengan expected space O(n), tetapi waktu worst-case O(n) tetap dimungkinkan saat tinggi acak tidak menguntungkan. Saya akan menggunakan sumber acak ber-seed untuk pengujian deterministik, membandingkan level nol dengan reference set setelah setiap operasi, dan menegaskan keterurutan serta invarian subsekuensi untuk semua level atas.”

Kesalahan umum

• Hanya memperbarui level nol → pencarian level atas dapat melewatkan atau mempertahankan kunci → sambungkan atau putuskan tautan di setiap level yang memuat simpul tersebut.
• Memperlakukan tinggi acak sebagai jaminan pasti → urutan patologis dapat menghasilkan jalur linier → nyatakan batas expected dan worst-case.
• Mengizinkan simpul duplikat secara tidak sengaja → semantik pencarian dan penghapusan menjadi ambigu → pilih perilaku set atau multiset sebelum membuat kode.
• Gagal memangkas level teratas yang kosong → pencarian memeriksa level yang basi dan pembukuan menyimpang → turunkan level aktif setelah penghapusan.
• Hanya menguji keanggotaan akhir → pointer atas yang rusak dapat tetap tersembunyi → periksa invarian keterurutan dan subsekuensi setelah setiap operasi.

Pertanyaan lanjutan dan tanggapan

Pertanyaan lanjutan 1: Bagaimana Anda mendukung kunci duplikat?

Pilih sebuah kontrak. Multiset dapat menyimpan hitungan (count) di setiap simpul kunci, membuat insert dan delete berulang memperbarui hitungan tersebut, atau menyimpan nomor urut unik di kunci pembanding. Simpan hitungan pada simpul jika memori memungkinkan; identitas unik berguna saat menghapus satu kemunculan tertentu.

Pertanyaan lanjutan 2: Bagaimana cara menambahkan kueri rank?

Simpan rentang (span) atau lebar di samping setiap forward pointer. Selama pencarian, akumulasikan rentang saat Anda bergerak ke kanan; penyisipan dan penghapusan memperbarui rentang yang terpengaruh di setiap level. Implementasi set sederhana tidak memiliki cukup metadata untuk menjawab kueri rank dalam waktu logaritmik.

Pertanyaan lanjutan 3: Kapan Anda lebih memilih balanced tree?

Gunakan balanced tree ketika batas worst-case, bentuk iterasi deterministik, atau operasi berurutan yang kaya lebih penting daripada kesederhanaan implementasi. Skip list cocok ketika performa logaritmik expected, varian konkuren yang mudah, atau indeks terurut berbasis pointer dapat diterima. Ukur overhead memori dan beban kerja alih-alih mengklaim satu struktur secara universal lebih cepat.