Bagaimana cara mengimplementasikan skip list dan menjelaskan perilaku O(log N) yang diharapkan?

1. Pertanyaan

Anda memerlukan kamus terurut yang mendukung pencarian kunci, penyisipan, penghapusan, dan pemindaian rentang. Kumpulan data bertambah secara dinamis, dan pewawancara menginginkan operasi rata-rata mendekati O(log N) tanpa memerlukan AVL tree atau red-black tree. Rancang sebuah skip list dan analisis keacakan, batas-batas, serta tata letak memori.

2. Batasan dan klarifikasi

• Tentukan apakah kunci bersifat unik; jika tidak, definisikan kebijakan penimpaan (overwrite), penghitungan, atau pengurutan yang stabil.
• Pilih level maksimum dan probabilitas promosi p; bangun indeks ke atas dari linked list terbawah.
• Pencarian, penyisipan, dan penghapusan mempertahankan pendahulu (predecessor) untuk setiap level; iterasi rentang mengikuti linked list terbawah.
• Bahas struktur single-threaded terlebih dahulu. Konkurensi memerlukan penguncian tambahan, pembuatan versi (versioning), atau pembuktian untuk algoritma lock-free.

3. Ide utama

Setiap node memiliki array pointer maju dengan ukuran acak. Pencarian dimulai dari head level tertinggi: maju selama kunci berikutnya berada di bawah target, jika tidak, turun satu level. Penyisipan mencatat pendahulu, memilih tinggi acak, dan menyambungkan node ke setiap level. Penghapusan menggunakan array pendahulu yang sama untuk melepaskannya. Level atas yang renggang menghasilkan ekspektasi pointer O(N) dan ekspektasi pencarian, penyisipan, serta penghapusan O(log N).

4. Implementasi referensi

randomLevel(rng, p, maxLevel):
  level = 1
  while level < maxLevel and rng.uniform01() < p:
    level += 1
  return level

findPredecessors(key):
  update = array(maxLevel)
  node = head
  for level from maxLevel - 1 down to 0:
    while node.forward[level] != nil and node.forward[level].key < key:
      node = node.forward[level]
    update[level] = node
  return update

insert(key, value):
  update = findPredecessors(key)
  if update[0].forward[0].key == key:
    update[0].forward[0].value = value
    return
  node = Node(key, value, randomLevel(rng, p, maxLevel))
  for level in 0 .. node.height - 1:
    node.forward[level] = update[level].forward[level]
    update[level].forward[level] = node

Periksa nil sebelum membaca kunci dan pastikan tinggi baru tidak pernah melebihi maxLevel. Penghapusan menghubungkan kembali setiap level yang menunjuk ke target dengan penerusnya. Jika level tertinggi menjadi kosong, kurangi jumlah level aktif tanpa memindahkan node.

5. Kompleksitas dan kasus terburuk

Dengan probabilitas promosi yang tetap dan sumber acak independen, level dan panjang jalur bersifat logaritmik dalam ekspektasi dan ruang yang diharapkan adalah O(N). Jika keacakan gagal atau pihak lawan dapat memprediksi level, struktur dapat terdegenerasi menjadi linked list dan operasi menjadi O(N). Gunakan sumber acak berkualitas tinggi, batasi tinggi maksimum, bangun ulang secara berkala, atau pilih balanced tree deterministik untuk beban kerja adversarial.

6. Verifikasi dan trade-off konkurensi

• Uji kunci terurut, duplikat, kosong, dan ekstrem untuk pencarian, pembaruan, penghapusan, dan iterasi rentang.
• Ukur distribusi tinggi, panjang jalur rata-rata, dan jumlah pointer di beberapa nilai N.
• Putar ulang urutan operasi acak terhadap ordered map referensi dan bandingkan konten serta urutannya.
• Untuk konkurensi, jelaskan granularitas kunci, penghapusan logis, reklamasi memori, dan risiko ABA; membungkus penulisan pointer dalam satu lock bukanlah desain lock-free.

7. Kesalahan umum

• Mengimplementasikan pencarian tanpa array pendahulu, sehingga memaksa penyisipan atau penghapusan memindai ulang list.
• Mengabaikan kebijakan kunci duplikat dan menghasilkan urutan rentang yang tidak stabil.
• Memperlakukan ekspektasi O(log N) sebagai jaminan kasus terburuk tanpa membahas keacakan dan input adversarial.
• Menggunakan array dengan tinggi tetap yang membuang-buang memori atau mengizinkan tinggi tak terbatas yang meluapkan (overflow) array.

8. Poin penilaian wawancara

Mencari dari level tinggi ke bawah

Kandidat menjelaskan kondisi maju pada setiap level, kapan harus turun, dan mengapa list terbawah berisi setiap elemen.

Mempertahankan pendahulu dengan benar

Kandidat menyimpan array pembaruan (update array) untuk setiap level dan menangani penimpaan, pointer nil, serta penyusutan level aktif tertinggi.

Menjelaskan kompleksitas probabilistik

Kandidat menyatakan waktu yang diharapkan O(log N), ruang yang diharapkan O(N), dan kondisi yang menyebabkan degenerasi ke O(N).

Mengidentifikasi batasan konkurensi

Kandidat membahas lock, versi, penghapusan logis, reklamasi memori, dan ABA alih-alih memperlakukan kode single-threaded sebagai kode konkuren.