Temu Duga Pengekodan: Menyalin Pautan Senarai dengan Penunjuk Rawak

Kehendak Soalan dan Konteks Berkenaan

Diberikan nod kepala (head) bagi acyclic singly linked list, setiap nod mengandungi val, next, dan random. Penunjuk random sama ada bernilai null atau merujuk kepada mana-mana nod yang boleh dicapai melalui rantai next senarai tersebut, termasuk nod itu sendiri. Kembalikan deep copy dengan tepat satu nod baharu bagi setiap nod asal. Jika nod asal x menunjuk ke nod asal y melalui salah satu medan, salinan bagi x mesti menunjuk melalui medan tersebut ke salinan bagi y.

Nilai nod tidak unik, jadi nilai tidak boleh digunakan untuk mengenal pasti nod. Rantai next adalah terhingga, walaupun tepi random boleh menunjuk ke belakang, ke hadapan, atau membentuk kitaran. Senarai yang dikembalikan tidak boleh berkongsi sebarang nod dengan input, dan input mesti mengekalkan struktur asalnya apabila fungsi kembali.

Ini adalah masalah struktur data dan identiti objek. Jawapan asas menggunakan peta daripada setiap objek asal kepada salinannya. Soalan susulan boleh memerlukan ruang bantuan malar (constant auxiliary space); versi tersebut menyisipkan salinan di antara nod asal buat sementara waktu dan kemudian memulihkan input. Nod output tidak dikira sebagai ruang bantuan, tetapi ia masih menggunakan sejumlah O(n) memori keseluruhan.

Perkara yang Dinilai oleh Penemu Duga

Isyarat pertama ialah sama ada calon mentakrifkan deep copy secara struktur. Nilai yang sama tidak mencukupi. Jawapan tersebut memerlukan pemetaan satu-ke-satu f daripada nod asal kepada nod baharu supaya kedua-dua hubungan dikekalkan: salinan bagi x.next ialah f(x).next, dan salinan bagi x.random ialah f(x).random.

Isyarat kedua ialah mengendalikan rujukan sebelum sasarannya disalin. Salinan nilai satu laluan (one-pass) tidak dapat menyambungkan tepi ke hadapan random dengan selamat. Penyelesaian terus mengasingkan peruntukan daripada penyambungan: cipta setiap nod destinasi terlebih dahulu, kemudian sambungkan penunjuk melalui peta identiti.

Isyarat ketiga ialah menerbitkan pengoptimuman ruang dan bukannya sekadar menghafalnya. Selepas meletakkan setiap salinan tepat selepas nod asalnya, salinan bagi mana-mana nod asal r adalah tepat pada r.next. Invarian tempatan itu menggantikan peta semasa penetapan penunjuk rawak.

Akhir sekali, penemu duga mencari disiplin mutasi. Kaedah penyisipan (interleaving) tidak lengkap sehingga ia memulihkan setiap penunjuk next asal, mengekstrak rantai salinan yang sah, dan menerangkan bila tindakan memutasi input buat sementara waktu tidak boleh diterima.

Soalan untuk Dijelaskan Sebelum Menjawab

• Bolehkah random menunjuk ke luar senarai? Soalan ini menyatakan tidak. Jika nod luaran tergolong dalam klon, skopnya menjadi penyalinan graf boleh capai umum; jika tidak, kontrak output mesti menyatakan sama ada untuk mengekalkan, mengosongkan, atau menolak rujukan tersebut.
• Bolehkah rantai next mengandungi kitaran? Tidak. Jika boleh, gelung yang hanya mengikut next tidak akan pernah berhenti tanpa set dilawati (visited set), dan masalah ini lebih wajar dikendalikan sebagai pengklonan graf.
• Bolehkah algoritma memutasi input buat sementara waktu? Penyelesaian peta tidak memutasi. Penyelesaian penyisipan memutasi dan hanya sesuai apabila fungsi mempunyai akses mutasi eksklusif serta memulihkan senarai sebelum kembali.
• Apakah yang dikira sebagai ruang tambahan? Nod yang disalin adalah output yang diperlukan. Peta menggunakan ruang bantuan O(n); penyisipan menggunakan penunjuk bantuan O(1) sebagai tambahan kepada output O(n).
• Adakah nilai nod unik? Tidak. Peta yang menggunakan nilai sebagai kunci akan menggabungkan nod yang berbeza dan merosakkan rujukan; kunci mestilah identiti nod.
• Apakah yang patut dikembalikan untuk input kosong? Kembalikan null.

Rangka Jawapan 30 Saat

“Saya akan menyelesaikannya terlebih dahulu menggunakan peta identiti asal-ke-salinan. Laluan pertama memperuntukkan setiap nod yang disalin, dan laluan kedua menetapkan penunjuk next dan random salinan dengan mencari sasaran asal yang sepadan. Itu memerlukan masa O(n) dan ruang bantuan O(n). Jika penemu duga memerlukan ruang bantuan malar dan mutasi sementara dibenarkan, saya boleh memasukkan setiap salinan sejurus selepas asalnya. Kemudian salinan sasaran rawak asal ialah nod seterusnya. Laluan ketiga memisahkan kedua-dua rantai sambil memulihkan input. Kedua-dua kaedah adalah linear; versi penyisipan menggunakan ruang bantuan O(1), tidak termasuk output yang diperlukan.”

Jawapan Terperinci Langkah demi Langkah

Shallow copy akan gagal kerana ia menggunakan semula rujukan asal. Menyalin nilai sahaja juga gagal: dua nod berbeza mungkin mempunyai nilai yang sama, dan random boleh menunjuk kepada nod yang belum muncul dalam traversal. Mengikuti random secara rekursif bukanlah jalan pintas kerana tepi rawak boleh membentuk kitaran.

Pendekatan asas yang paling selamat adalah membina bijeksi secara eksplisit. Laluan pertama memperuntukkan satu objek baharu bagi setiap nod asal. Laluan kedua menterjemahkan kedua-dua tepi keluar melalui peta tersebut. Memasukkan null -> null dalam carian adalah pilihan; semakan null secara eksplisit biasanya lebih jelas dalam temu duga.

class RandomListNode {
  val: number
  next: RandomListNode | null
  random: RandomListNode | null

  constructor(
    val: number,
    next: RandomListNode | null = null,
    random: RandomListNode | null = null,
  ) {
    this.val = val
    this.next = next
    this.random = random
  }
}

function copyWithMap(head: RandomListNode | null): RandomListNode | null {
  if (head === null) return null

  const copies = new Map<RandomListNode, RandomListNode>()

  let current: RandomListNode | null = head
  while (current !== null) {
    copies.set(current, new RandomListNode(current.val))
    current = current.next
  }

  current = head
  while (current !== null) {
    const copy = copies.get(current)!
    copy.next = current.next === null ? null : copies.get(current.next)!
    copy.random = current.random === null ? null : copies.get(current.random)!
    current = current.next
  }

  return copies.get(head)!
}

Invarian selepas laluan pertama adalah mudah: setiap nod asal yang dilawati melalui next mempunyai tepat satu entri berbeza dalam peta, dan tiada penunjuk salinan yang perlu menyasar nod yang belum diperuntukkan. Semasa laluan kedua, menterjemahkan tepi dari x ke y menjadi tepi dari f(x) ke f(y) mengekalkan struktur graf. Kaedah ini memerlukan dua laluan linear, jadi masa ialah O(n) dan ruang bantuan ialah O(n).

Untuk menghapuskan peta, simpan korespondensi yang sama buat sementara waktu dalam topologi senarai. Ubah rantai ini:

A -> B -> C -> null

menjadi rantai yang disisipkan ini:

A -> A' -> B -> B' -> C -> C' -> null

Kini A' ialah A.next, dan jika A.random menunjuk ke C, maka sasaran yang betul untuk A'.random ialah A.random.next, iaitu C'. Ini berfungsi untuk tepi ke hadapan, tepi ke belakang, rujukan diri sendiri (self-references), dan sasaran berulang kerana ia bergantung pada kedudukan objek, bukan nilainya.

function copyByInterleaving(head: RandomListNode | null): RandomListNode | null {
  if (head === null) return null

  let current: RandomListNode | null = head
  while (current !== null) {
    const copy: RandomListNode = new RandomListNode(current.val, current.next)
    current.next = copy
    current = copy.next
  }

  current = head
  while (current !== null) {
    const copy: RandomListNode = current.next!
    copy.random = current.random === null ? null : current.random.next
    current = copy.next
  }

  const copiedHead = head.next
  current = head

  while (current !== null) {
    const copy: RandomListNode = current.next!
    const nextOriginal: RandomListNode | null = copy.next

    current.next = nextOriginal
    copy.next = nextOriginal === null ? null : nextOriginal.next
    current = nextOriginal
  }

  return copiedHead
}

Ketepatan algoritma terbukti melalui tiga invarian laluan. Selepas laluan satu, setiap nod asal diikuti serta-merta oleh salinan uniknya. Semasa laluan dua, setiap tepi rawak yang disalin menuju ke salinan tepat selepas sasaran asal. Semasa laluan tiga, setiap lelaran memulihkan satu tepi asal dan menyambungkan satu tepi salinan ke nod salinan seterusnya. Apabila gelung tamat, rantai asal dipulihkan dan setiap penunjuk yang boleh dicapai daripada kepala salinan hanya menyasarkan nod salinan.

Kaedah penyisipan melakukan tiga laluan linear, jadi masa kekal O(n). Ia hanya menyimpan bilangan penunjuk kerja yang tetap, jadi ruang bantuan ialah O(1), tidak termasuk n nod baharu yang diperlukan. Ia tidak semestinya pilihan pengeluaran yang lebih baik: semasa dua laluan pertama, pembaca (reader) lain melihat input yang kelihatan rosak, dan pengecualian (exception) sebelum pemisahan boleh meninggalkan senarai dalam keadaan bersisip. Penyelesaian peta lebih mudah diaudit dan menyokong input yang tidak boleh diubah (immutable) atau dikongsi (shared).

Uji struktur, identiti, dan pemulihan secara berasingan. Uji senarai kosong; satu nod dengan random = null; satu nod yang penunjuk rawaknya menunjuk ke dirinya sendiri; nilai pendua; dua nod yang penunjuk rawaknya bersilang; tepi rawak ke hadapan dan ke belakang; dan banyak nod yang menunjuk ke sasaran yang sama. Selepas pengklonan, mutasikan nilai salinan dan sahkan nilai asal tidak berubah. Lalui senarai asal sekali lagi untuk mengesahkan rantai next telah dipulihkan, dan pastikan tiada penunjuk next atau random salinan yang tergolong dalam set nod asal.

Contoh Jawapan Berkualiti Tinggi

“Perkara penting ialah mengekalkan identiti nod, bukan sekadar nilai. Nilai mungkin berulang, dan tepi rawak boleh menunjuk ke hadapan atau membentuk kitaran, jadi saya tidak akan menggunakan nilai sebagai kunci atau mengikut penunjuk rawak secara rekursif tanpa status dilawati.

Penyelesaian asas saya adalah dua laluan dengan peta identiti. Laluan pertama menelusuri rantai next yang asiklik dan memperuntukkan satu salinan bagi setiap nod asal. Laluan kedua menterjemahkan kedua-dua penunjuk melalui peta. Itu secara langsung membina korespondensi satu-ke-satu, mengambil masa linear, dan menggunakan ruang bantuan linear. Ini adalah versi yang akan saya pilih apabila input bersifat immutable, dikongsi, atau apabila pelaksanaan yang paling mudah diaudit diperlukan.

Jika ruang bantuan malar adalah keperluan wajib dan saya dibenarkan memutasi buat sementara waktu, saya akan menyisipkan setiap salinan selepas asalnya. Itu menjadikan pemetaan tersirat: salinan bagi mana-mana sasaran asal ialah target.next. Saya kemudian menetapkan setiap penunjuk rawak yang disalin dan memisahkan (unzip) rantai yang berselang-seli itu. Laluan pemisahan mesti mengemas kini kedua-dua rantai, supaya senarai asal dipulihkan dengan tepat dan salinan tidak mengandungi rujukan kembali ke dalamnya.

Saya akan membuktikan tiga invarian selepas penyisipan, penetapan rawak, dan pemisahan, kemudian menguji self-random, nilai pendua, tepi rawak bersilang, input kosong, dan kebebasan pasca-salinan. Kedua-dua versi mengambil masa O(n); versi kedua menggunakan ruang bantuan O(1) tetapi masih memperuntukkan output O(n) dan tidak selamat dengan pembaca serentak (concurrent readers).”

Kesilapan Biasa

• Menggunakan nilai nod sebagai kunci peta -> nilai pendua menggabungkan identiti yang berbeza -> gunakan objek nod asal sebagai kunci.
• Menyalin random secara terus -> output masih menunjuk ke dalam input -> terjemahkan setiap sasaran bukan-null kepada nod salinannya.
• Memperuntukkan dan menyambung dalam satu laluan ke hadapan yang naif -> sasaran rawak ke hadapan mungkin belum wujud -> peruntukkan semua nod terlebih dahulu atau cipta salinan yang hilang melalui peta identiti yang lengkap.
• Mengikuti penunjuk rawak secara rekursif tanpa status dilawati -> kitaran rawak menyebabkan rekursi tanpa henti atau nod pendua -> gunakan rantai next yang terhingga untuk kontrak ini atau peta dilawati untuk graf umum.
• Menyatakan kaedah penyisipan menggunakan ruang O(1) tanpa syarat -> senarai yang dikembalikan masih mengandungi n nod baharu -> nyatakan ruang bantuan O(1) tidak termasuk output yang diperlukan.
• Menetapkan copy.random = current.random.next tanpa semakan null -> penunjuk rawak null akan menyebabkan ranap -> kekalkan null secara eksplisit.
• Hanya mengasingkan rantai yang disalin -> nod asal kekal dipautkan melalui salinan -> pulihkan rantai asal dan bina rantai salinan dalam laluan pemisahan yang sama.
• Menggunakan penyisipan pada input yang dikongsi (shared input) -> pembaca serentak akan melihat salinan yang disisipkan -> gunakan penyelesaian peta melainkan mutasi sementara eksklusif dijamin.
• Menguji nilai sahaja -> shallow copy boleh melepasi perbandingan nilai -> sahkan identiti berbeza, tepi diterjemahkan, pemulihan asal, dan kebebasan mutasi.

Soalan Susulan dan Maklum Balas

Soalan susulan 1: Bagaimana jika input tidak boleh diubah langsung, walaupun buat sementara waktu?

Gunakan penyelesaian peta identiti. Ia memberikan masa O(n) dan ruang bantuan O(n) sambil mengekalkan sumber tanpa disentuh sepanjang pelaksanaan. Menyalin ke dalam tatasusunan mengikut indeks traversal juga menggunakan ruang O(n) dan masih memerlukan pemetaan identiti-ke-indeks melainkan input sudah mendedahkan indeks yang stabil. Pengoptimuman penyisipan melanggar kontrak immutabiliti yang lebih ketat ini walaupun ia kemudiannya memulihkan senarai.

Soalan susulan 2: Bagaimana jika random boleh menunjuk ke nod di luar rantai next?

Mula-mula takrifkan pemilikan klon. Jika nod luaran juga mesti disalin, input tersebut ialah graf yang tepi keluarnya ialah next dan random; gunakan DFS atau BFS dengan peta identiti dan klon setiap nod yang boleh dicapai sekali. Jika nod luaran sengaja dikongsi, kontrak mesti membenarkan pengekalan rujukan luaran tersebut. Penyisipan tidak dapat menemui atau meletakkan salinan bagi sasaran luaran rawak.

Soalan susulan 3: Bagaimana jika penunjuk next boleh membentuk kitaran?

Traversal while current !== null biasa tidak akan berhenti. Anggap kedua-dua medan sebagai tepi graf dan simpan peta identiti yang dilawati. Cipta salinan nod kali pertama ia ditemui, kemudian masukkan jiran yang belum dilihat ke dalam baris gilir (queue). Masa dan ruang menjadi O(V + E) untuk graf yang boleh dicapai, dengan paling banyak dua tepi keluar bagi setiap nod dalam model ini.

Soalan susulan 4: Bagaimanakah anda mengesahkan bahawa salinan itu benar-benar deep copy?

Bina peta hanya dalam ujian daripada identiti asal kepada identiti salinan semasa menelusuri kedua-dua rantai next. Sahkan panjang dan nilai yang sama, identiti nod yang berbeza, dan bagi setiap tepi, pastikan sasaran salinan bersamaan dengan sasaran asal yang dipetakan. Sahkan juga bahawa tiada penunjuk output berada dalam set nod asal. Akhir sekali, mutasikan nilai dan penunjuk dalam salinan dan sahkan bahawa sumber tidak berubah; untuk penyisipan, bandingkan identiti penunjuk sumber sebelum dan selepas panggilan fungsi.

Soalan susulan 5: Penyelesaian manakah yang akan anda gunakan untuk pengeluaran (production)?

Gunakan versi peta dua laluan sebagai lalai kerana invariannya adalah eksplisit dan ia tidak pernah mendedahkan input yang diubah suai buat sementara waktu. Pilih penyisipan hanya apabila memori bantuan ialah kekangan yang telah diukur, senarai dimiliki secara eksklusif sepanjang panggilan, dan pengendalian kegagalan dapat menjamin pemulihan. Penambahbaikan ruang asimptotik tidak memadamkan kos konkurensi, keselamatan pengecualian (exception-safety), dan kebolehselenggaraan.