Wawancara Koding: Menyalin Linked List dengan Pointer Acak

Konteks dan Deskripsi Soal

Diberikan head dari acyclic singly linked list, setiap simpul berisi val, next, dan random. Pointer random bernilai null atau merujuk ke simpul mana pun yang dapat dijangkau melalui rantai next pada list tersebut, termasuk simpul itu sendiri. Kembalikan deep copy dengan tepat satu simpul baru untuk setiap simpul asli. Jika simpul asli x menunjuk ke simpul asli y melalui salah satu field, salinan dari x harus menunjuk melalui field tersebut ke salinan dari y.

Nilai simpul tidak unik, sehingga nilai tidak dapat mengidentifikasi simpul. Rantai next bersifat terbatas (finite), meskipun tepi random dapat menunjuk ke belakang, ke depan, atau membentuk siklus. List yang dikembalikan tidak boleh berbagi simpul dengan input, dan input harus memiliki struktur aslinya saat fungsi kembali.

Ini adalah masalah struktur data dan identitas objek. Jawaban dasar menggunakan map dari setiap objek asli ke salinannya. Pertanyaan lanjutan dapat meminta ruang tambahan konstan (constant auxiliary space); versi tersebut menyisipkan salinan di antara simpul asli untuk sementara waktu dan kemudian memulihkan input. Simpul keluaran tidak dihitung sebagai ruang tambahan, tetapi tetap mengonsumsi total memori O(n).

Apa yang Dinilai oleh Pewawancara

Sinyal pertama adalah apakah kandidat mendefinisikan deep copy secara struktural. Nilai yang sama saja tidak cukup. Jawabannya memerlukan pemetaan satu-ke-satu f dari simpul asli ke simpul baru sedemikian rupa sehingga kedua relasi dipertahankan: salinan dari x.next adalah f(x).next, dan salinan dari x.random adalah f(x).random.

Sinyal kedua adalah penanganan referensi sebelum targetnya disalin. Salinan nilai satu lintasan (one-pass) tidak dapat menghubungkan tepi maju random dengan aman. Solusi langsung memisahkan alokasi dari penghubungan: buat setiap simpul tujuan terlebih dahulu, lalu hubungkan pointer melalui identity map.

Sinyal ketiga adalah menurunkan optimasi ruang alih-alih sekadar menghafalnya. Setelah menempatkan setiap salinan tepat setelah simpul aslinya, salinan dari setiap simpul asli r tepat berada di r.next. Invarian lokal tersebut menggantikan map selama penugasan pointer acak.

Terakhir, pewawancara mencari kedisiplinan mutasi. Metode penyisipan (interleaving) belum lengkap sampai metode tersebut memulihkan setiap pointer next asli, mengekstrak rantai salinan yang valid, dan menjelaskan kapan memutasi input untuk sementara waktu tidak dapat diterima.

Pertanyaan untuk Diklarifikasi Sebelum Menjawab

• Bisakah random menunjuk ke luar list? Deskripsi soal ini menyatakan tidak. Jika simpul eksternal termasuk dalam klona, cakupannya menjadi penyalinan graf terjangkau umum; jika tidak, kontrak keluaran harus menyatakan apakah akan mempertahankan, mengosongkan, atau menolak referensi tersebut.
• Bisakah rantai next mengandung siklus? Tidak. Jika bisa, perulangan yang hanya mengikuti next tidak akan pernah berhenti tanpa himpunan yang telah dikunjungi (visited set), dan masalah ini lebih tepat diperlakukan sebagai kloning graf.
• Bolehkah algoritma memutasi input untuk sementara? Solusi map tidak memutasi. Solusi penyisipan memutasi dan hanya sesuai jika fungsi memiliki akses mutasi eksklusif dan memulihkan list sebelum kembali.
• Apa yang dihitung sebagai ruang tambahan? Simpul yang disalin adalah output yang diperlukan. Map membutuhkan ruang tambahan O(n); penyisipan menggunakan pointer tambahan O(1) selain output O(n).
• Apakah nilainya unik? Tidak. Map yang menggunakan nilai sebagai kunci akan menggabungkan simpul yang berbeda dan merusak referensi; kunci harus berupa identitas simpul.
• Apa yang harus dikembalikan jika input kosong? Kembalikan null.

Kerangka Jawaban 30 Detik

“Pertama-tama saya akan menyelesaikannya dengan identity map dari asli ke salinan. Lintasan pertama mengalokasikan setiap simpul salinan, dan lintasan kedua menetapkan pointer next dan random salinan dengan mencari target asli yang sesuai. Itu membutuhkan waktu O(n) dan ruang tambahan O(n). Jika pewawancara memerlukan ruang tambahan konstan dan mutasi sementara diizinkan, saya dapat menyisipkan setiap salinan tepat setelah aslinya. Kemudian salinan dari target acak asli adalah simpul berikutnya. Lintasan ketiga memisahkan kedua rantai sambil memulihkan input. Kedua metode beroperasi secara linear; versi penyisipan menggunakan ruang tambahan O(1), di luar output yang diperlukan.”

Jawaban Mendalam Langkah demi Langkah

Shallow copy gagal karena menggunakan kembali referensi asli. Menyalin nilainya saja juga gagal: dua simpul yang berbeda dapat memiliki nilai yang sama, dan random dapat menunjuk ke simpul yang belum muncul dalam penelusuran. Mengikuti random secara rekursif bukanlah jalan pintas karena tepi acak dapat membentuk siklus.

Dasar yang paling aman adalah membuat bijeksi secara eksplisit. Lintasan pertama mengalokasikan satu objek baru per simpul asli. Lintasan kedua menerjemahkan kedua tepi keluar melalui map tersebut. Menyertakan null -> null dalam pencarian bersifat opsional; pemeriksaan null eksplisit biasanya lebih jelas dalam wawancara.

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 setelah lintasan pertama sederhana: setiap simpul asli yang dikunjungi melalui next memiliki tepat satu entri berbeda dalam map, dan tidak ada pointer salinan yang harus menargetkan simpul yang belum dialokasikan. Selama lintasan kedua, menerjemahkan tepi dari x ke y menjadi tepi dari f(x) ke f(y) mempertahankan graf. Metode ini membutuhkan dua lintasan linear, sehingga waktu adalah O(n) dan ruang tambahan adalah O(n).

Untuk menghilangkan map, simpan korespondensi yang sama untuk sementara di topologi list. Ubah rantai ini:

A -> B -> C -> null

menjadi rantai yang disisipkan ini:

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

Sekarang A' adalah A.next, dan jika A.random menunjuk ke C, maka target yang benar untuk A'.random adalah A.random.next, yaitu C'. Ini berfungsi untuk tepi maju, tepi mundur, referensi diri sendiri (self-references), dan target yang berulang karena bergantung pada posisi 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
}

Kebenaran algoritma mengikuti tiga invarian lintasan. Setelah lintasan pertama, setiap simpul asli langsung diikuti oleh salinan uniknya. Selama lintasan kedua, setiap tepi acak salinan mengarah ke salinan tepat setelah target aslinya. Selama lintasan ketiga, setiap iterasi memulihkan satu tepi asli dan menghubungkan satu tepi salinan ke simpul salinan berikutnya. Saat perulangan berakhir, rantai asli dipulihkan dan setiap pointer yang dapat dijangkau dari head salinan hanya menargetkan simpul salinan.

Metode penyisipan melakukan tiga lintasan linear, sehingga waktu tetap O(n). Metode ini hanya menyimpan sejumlah pointer kerja yang tetap, sehingga ruang tambahan adalah O(1), tidak termasuk n simpul baru yang diperlukan. Ini tidak serta merta menjadi pilihan produksi yang lebih baik: selama dua lintasan pertama, pembaca (reader) lain akan melihat input yang tampak rusak, dan pengecualian (exception) sebelum pemisahan dapat membuat list tetap dalam keadaan tersisip. Solusi map lebih mudah diaudit dan mendukung input yang tidak dapat diubah (immutable) atau digunakan bersama (shared).

Uji struktur, identitas, dan pemulihan secara terpisah. Cakup list kosong; satu simpul dengan random = null; satu simpul yang pointer random-nya menunjuk ke dirinya sendiri; nilai duplikat; dua simpul yang pointer random-nya bersilangan; tepi random maju dan mundur; serta banyak simpul yang menunjuk ke target yang sama. Setelah kloning, mutasi nilai salinan dan pastikan nilai asli tidak berubah. Telusuri kembali list asli untuk memverifikasi rantai next telah dipulihkan, dan pastikan tidak ada pointer next atau random salinan yang menjadi bagian dari himpunan simpul asli.

Contoh Jawaban Berkualitas Tinggi

“Bagian terpenting adalah mempertahankan identitas simpul, bukan hanya nilainya. Nilai dapat berulang, dan tepi acak dapat menunjuk ke depan atau membentuk siklus, jadi saya tidak akan menggunakan nilai sebagai kunci apa pun atau mengikuti pointer acak secara rekursif tanpa status kunjungan.

Dasar saya adalah dua lintasan dengan identity map. Lintasan pertama menelusuri rantai next yang asiklik dan mengalokasikan satu salinan per simpul asli. Lintasan kedua menerjemahkan kedua pointer melalui map. Itu secara langsung membangun korespondensi satu-ke-satu, membutuhkan waktu linear, dan menggunakan ruang tambahan linear. Ini adalah versi yang akan saya pilih ketika input bersifat immutable, shared, atau ketika implementasi yang paling sederhana dan mudah diaudit menjadi prioritas.

Jika ruang tambahan konstan adalah persyaratan mutlak dan saya boleh memutasi untuk sementara, saya akan menyisipkan setiap salinan setelah aslinya. Itu membuat pemetaan menjadi implisit: salinan dari target asli mana pun adalah target.next. Saya kemudian menetapkan setiap pointer acak salinan dan memisahkan (unzip) rantai yang berselang-seling tersebut. Lintasan pemisahan harus memperbarui kedua rantai, sehingga yang asli dipulihkan secara tepat dan salinannya tidak berisi referensi yang kembali ke list asli.

Saya akan membuktikan tiga invarian setelah penggabungan, penugasan acak, dan pemisahan, lalu menguji self-random, nilai duplikat, tepi acak yang bersilangan, input kosong, dan independensi pasca-penyalinan. Kedua versi memiliki waktu O(n); versi kedua membutuhkan ruang tambahan O(1) tetapi tetap mengalokasikan output O(n) dan tidak aman untuk pembaca bersamaan (concurrent readers).”

Kesalahan Umum

• Menggunakan nilai simpul sebagai kunci map -> nilai duplikat meleburkan identitas yang berbeda -> gunakan objek simpul asli sebagai kunci.
• Menyalin random secara langsung -> output masih menunjuk ke dalam input -> terjemahkan setiap target non-null ke simpul salinannya.
• Mengalokasikan dan menghubungkan dalam satu lintasan maju naif -> target acak maju mungkin belum ada -> alokasikan semua simpul terlebih dahulu atau buat salinan yang hilang melalui identity map lengkap.
• Mengikuti pointer acak secara rekursif tanpa status kunjungan -> siklus acak menyebabkan rekursi tak terbatas atau simpul duplikat -> gunakan rantai next yang terbatas untuk kontrak ini atau map yang telah dikunjungi untuk graf umum.
• Menyebut metode penyisipan memiliki ruang O(1) tanpa kualifikasi -> list yang dikembalikan masih berisi n simpul baru -> sebutkan ruang tambahan O(1) tidak termasuk output yang diperlukan.
• Menetapkan copy.random = current.random.next tanpa pemeriksaan null -> pointer random null menyebabkan crash -> pertahankan null secara eksplisit.
• Hanya melepaskan rantai salinan -> simpul asli tetap terhubung melalui salinan -> pulihkan rantai asli dan bangun rantai salinan dalam lintasan pemisahan yang sama.
• Menggunakan penyisipan pada input bersama (shared input) -> pembaca bersamaan akan melihat salinan yang disisipkan -> gunakan solusi map kecuali jika mutasi sementara yang eksklusif dijamin.
• Hanya menguji nilai -> shallow copy dapat lolos perbandingan nilai -> pastikan identitas berbeda, tepi diterjemahkan, pemulihan asli, dan independensi mutasi.

Pertanyaan Lanjutan dan Tanggapan

Pertanyaan lanjutan 1: Bagaimana jika input tidak boleh dimodifikasi sama sekali, bahkan untuk sementara?

Gunakan solusi identity map. Pendekatan ini memberikan waktu O(n) dan ruang tambahan O(n) sambil membiarkan sumber tidak tersentuh selama eksekusi. Menyalin ke dalam array berdasarkan indeks penelusuran juga mengonsumsi ruang O(n) dan masih memerlukan pemetaan identitas-ke-indeks kecuali jika input sudah menyediakan indeks yang stabil. Optimasi penyisipan melanggar kontrak immutabilitas yang lebih ketat ini meskipun nantinya list dipulihkan.

Pertanyaan lanjutan 2: Bagaimana jika random dapat menunjuk ke simpul di luar rantai next?

Pertama tentukan kepemilikan klona. Jika simpul eksternal juga harus disalin, input tersebut merupakan graf dengan tepi keluar next dan random; gunakan DFS atau BFS dengan identity map dan klona setiap simpul yang dapat dijangkau satu kali. Jika simpul eksternal memang sengaja dibagikan, kontrak harus mengizinkan referensi eksternal yang dipertahankan. Penyisipan tidak dapat menemukan atau memposisikan salinan untuk target eksternal sembarang.

Pertanyaan lanjutan 3: Bagaimana jika pointer next dapat membentuk siklus?

Penelusuran while current !== null biasa tidak akan pernah berhenti. Perlakukan kedua field sebagai tepi graf dan simpan identity map dari simpul yang telah dikunjungi. Buat salinan simpul saat pertama kali ditemukan, lalu masukkan tetangga yang belum terlihat ke dalam antrean. Waktu dan ruang menjadi O(V + E) untuk graf yang dapat dijangkau, dengan paling banyak dua tepi keluar per simpul pada model ini.

Pertanyaan lanjutan 4: Bagaimana Anda memverifikasi bahwa salinannya benar-benar deep copy?

Bangun map hanya dalam pengujian dari identitas asli ke identitas salinan sambil menelusuri kedua rantai next. Pastikan panjang dan nilai sama, identitas simpul berbeda, dan untuk setiap tepi, target salinan sama dengan target asli yang dipetakan. Pastikan juga tidak ada pointer output yang berada dalam himpunan simpul asli. Terakhir, mutasi nilai dan pointer pada salinan dan konfirmasi bahwa sumber tidak berubah; untuk penyisipan, bandingkan identitas pointer sumber sebelum dan sesudah pemanggilan.

Pertanyaan lanjutan 5: Solusi mana yang akan Anda terapkan ke lingkungan produksi?

Gunakan versi map dua lintasan sebagai default karena invarian-nya eksplisit dan tidak pernah mengekspos input yang dimodifikasi sementara. Pilih penyisipan hanya jika memori tambahan adalah kendala terukur, list dimiliki secara eksklusif selama seluruh pemanggilan, dan penanganan kegagalan dapat menjamin pemulihan. Peningkatan ruang asimtotik tidak menghapus biaya konkurensi, exception-safety, dan maintainability.