Wawancara Koding: Membalik Node dalam k-Group (Reverse Nodes in k-Group)

Pertanyaan dan Konteks yang Berlaku

Diberikan head head dari sebuah singly linked list dan sebuah integer positif k, balikkan setiap grup lengkap dari k node berurutan secara in-place. Jika tersisa kurang dari k node di akhir, pertahankan urutan aslinya. Sambungkan kembali pointer node alih-alih menukar field value.

Sebagai contoh, 1 → 2 → 3 → 4 → 5 menjadi 2 → 1 → 4 → 3 → 5 saat k = 2, dan menjadi 3 → 2 → 1 → 4 → 5 saat k = 3. Asumsikan 1 ≤ k ≤ n ≤ 5000, input bersifat asiklik, dan targetnya adalah waktu O(n) dengan ruang ekstra O(1).

Masalah ini cocok untuk wawancara koding di berbagai peran algoritma, backend, infrastruktur, dan rekayasa perangkat lunak umum. Bagian yang sulit bukanlah pembalikan list dasar. Tantangannya adalah membuktikan bahwa grup yang lengkap ada sebelum mutasi dilakukan, mempertahankan titik masuk ke grup berikutnya, menyambungkan kembali kedua batas, dan menunjukkan bahwa tidak ada node yang hilang atau terjebak dalam siklus.

Hal yang Dievaluasi Pewawancara

Sinyal pertama adalah apakah kandidat memisahkan penemuan batas, pembalikan segmen, dan penyambungan kembali. Mulai membalik sebelum mengetahui bahwa k node tersisa membuat tail yang tidak lengkap sulit dipulihkan tanpa penyimpanan ekstra. Solusi yang kuat melakukan lookahead read-only sebelum mengubah pointer apa pun.

Sinyal kedua adalah kepemilikan pointer yang jelas. groupPrev berada sebelum grup saat ini, kth adalah node terakhir dari grup yang lengkap, groupNext adalah titik masuk ke segmen berikutnya, dan head grup yang lama menjadi tail yang baru. Di akhir setiap iterasi, prefix yang telah selesai harus tetap dapat dijangkau dan groupPrev.next harus menjadi node pertama yang belum diproses.

Sinyal ketiga adalah invarian alih-alih kode yang dihafal. Menginisialisasi prev ke groupNext membuat head grup lama menunjuk ke suffix ketika ia menjadi tail. Setelah pembalikan selesai, hanya prefix sebelumnya yang perlu dihubungkan ke kth; koneksi grup-ke-suffix sudah benar.

Sinyal keempat adalah kedisiplinan kompleksitas. Setiap node dikunjungi paling banyak sekali saat complete-group lookahead dan sekali saat pembalikan, sehingga totalnya adalah O(n), sementara jumlah referensi yang tetap memberikan ruang ekstra O(1). Versi rekursif memiliki batas waktu yang sama tetapi menghabiskan ruang stack yang sebanding dengan jumlah grup.

Pertanyaan untuk Diklarifikasi Sebelum Menjawab

• Apa yang terjadi pada grup terakhir yang lebih kecil dari k? Grup tersebut tetap tidak berubah di sini. Beberapa varian membalikkannya,

yang menghasilkan hasil berbeda.

• Bolehkah nilai node ditukar? Tidak. Node mungkin memiliki identitas, referensi eksternal, atau field selain nilai,

sehingga penukaran nilai bukanlah pembalikan node.

• Nilai k apa saja yang valid? Deskripsi menjamin 1 ≤ k ≤ n. Fungsi yang dapat digunakan kembali tetap dapat menolak

non-integer atau nilai di bawah satu.

• Bisakah input mengandung siklus? Deskripsi ini menyatakan tidak. Jika siklus dimungkinkan, kontrak harus menentukan apakah akan

menolak atau mengubahnya; jika tidak, lookahead mungkin tidak akan pernah selesai.

• Haruskah algoritma bersifat in-place? Ya. Penggunaan stack lebih sederhana jika ruang O(k) diizinkan, tetapi tidak memenuhi target ini.
• Haruskah objek node digunakan kembali? Ya. Membangun list baru yang hanya menyalin nilai melanggar kontrak.

Kerangka Jawaban 30 Detik

"Saya akan menambahkan dummy node sebelum head dan mempertahankan groupPrev tepat sebelum grup saat ini. Setiap iterasi melangkah k langkah dari groupPrev untuk menemukan kth. Jika gagal, saya langsung mengembalikan hasil karena tail belum dimodifikasi. Setelah menyimpan groupNext = kth.next, saya menginisialisasi prev ke groupNext dan membalik grup saat ini pointer demi pointer. Hal ini membuat head grup lama menjadi tail baru yang sudah menunjuk ke groupNext. Saya menghubungkan groupPrev.next ke kth, lalu memindahkan groupPrev ke head grup yang lama. Setiap node dikunjungi sekali untuk lookahead dan sekali untuk pembalikan, menghasilkan waktu O(n) dan ruang ekstra O(1)."

Pembahasan Mendalam Langkah demi Langkah

Mulailah dengan dummy node. Head list berubah ketika grup pertama dibalik. Dummy node membuat proses penyambungan prefix ke head grup yang baru menjadi identik untuk grup pertama maupun setiap grup berikutnya, menghindari penanganan kasus khusus untuk head.

Setiap iterasi pertama-tama melakukan complete-group lookahead. Bergerak tepat k kali dari groupPrev untuk mendapatkan kth. Jika langkah mencapai null, tersisa kurang dari k node, jadi kembalikan dummy.next. Lookahead tidak menulis pointer apa pun, itulah sebabnya tail yang tidak lengkap secara otomatis tetap tidak berubah.

Implementasinya adalah:

class ListNode {
  constructor(value, next = null) {
    this.value = value
    this.next = next
  }
}

function reverseKGroup(head, k) {
  if (!Number.isInteger(k) || k < 1) {
    throw new RangeError('k must be a positive integer')
  }

  const dummy = new ListNode(0, head)
  let groupPrev = dummy

  while (true) {
    let kth = groupPrev

    for (let step = 0; step < k; step += 1) {
      kth = kth.next
      if (kth === null) {
        return dummy.next
      }
    }

    const groupNext = kth.next
    let prev = groupNext
    let current = groupPrev.next

    while (current !== groupNext) {
      const nextNode = current.next
      current.next = prev
      prev = current
      current = nextNode
    }

    const oldGroupHead = groupPrev.next
    groupPrev.next = kth
    groupPrev = oldGroupHead
  }
}

Penelusuran 1 → 2 → 3 → 4 → 5 dengan k = 3. Lookahead menemukan kth = 3, dan groupNext = 4 disimpan. Atur prev = 4, lalu tulis 1.next = 4, 2.next = 1, dan 3.next = 2. Node 3 sekarang menjadi head grup, sementara node 1 menjadi tail dan sudah terhubung ke node 4. Hubungkan dummy node ke 3 dan pindahkan groupPrev ke node 1. Lookahead berikutnya tidak dapat menemukan tiga node, sehingga kembali tanpa menyentuh 4 → 5.

Invarian loop memiliki tiga bagian. Pada awal loop, prefix hingga groupPrev telah ditransformasi dengan benar dalam grup-grup lengkap; groupPrev.next adalah node pertama yang belum diproses; dan semua node yang belum diproses tetap dapat dijangkau sesuai urutan input. Lookahead yang gagal tidak melakukan penulisan, sehingga invarian langsung membuktikan bahwa tail yang tidak lengkap tetap terjaga. Lookahead yang berhasil membatasi pembalikan tepat ke k node, sementara groupNext mempertahankan titik masuk suffix. Setelah penyambungan kembali, prefix yang selesai bertambah satu grup dan invarian dipulihkan. Setiap iterasi yang berhasil memproses k node baru, sehingga algoritma pasti berakhir (terminates).

Lookahead dan pembalikan masing-masing menyentuh sebuah node paling banyak satu kali di semua iterasi. Oleh karena itu, total pekerjaan paling banyak sekitar 2n kunjungan node: O(n), bukan O(nk). Dummy node dan jumlah pointer tidak bertambah seiring ukuran input, sehingga ruang tambahannya adalah O(1).

Jika ruang ekstra diperbolehkan, memasukkan satu grup ke dalam stack lalu mengeluarkannya (pop) lebih mudah ditulis tetapi menggunakan ruang O(k). Solusi rekursif dapat mengonfirmasi satu grup lengkap, membalikkannya, dan melakukan rekursi pada suffix, menggunakan ruang stack O(n / k). Versi iteratif adalah rekomendasi yang tepat untuk target ruang konstan. Untuk input kecil di mana prioritasnya adalah versi pertama yang cepat ditinjau, pendekatan stack bisa menjadi trade-off yang masuk akal dan dinyatakan secara eksplisit.

Pengujian harus melakukan lebih dari sekadar membandingkan array nilai. Simpan set referensi node asli, telusuri hasilnya, dan pastikan list bersifat asiklik, memiliki jumlah node yang sama, dan berisi referensi yang persis sama sebelum memeriksa urutan. Cakup input kosong defensif, satu node, k = 1, n = k, panjang yang habis dibagi k, tail yang tidak lengkap, nilai duplikat, dan ukuran maksimum. Nilai duplikat sangat berguna karena pengujian berbasis nilai saja tidak dapat membuktikan bahwa objek node benar-benar digunakan kembali.

Contoh Jawaban Berkualitas Tinggi

"Pertama-tama saya akan mengonfirmasi bahwa node sisa yang kurang dari k tetap dalam urutan aslinya dan nilainya tidak boleh ditukar. State iteratif saya adalah sebuah dummy node ditambah sejumlah referensi tetap. groupPrev selalu berada tepat sebelum grup saat ini. Saya melangkah k langkah darinya, dan jika kth tidak ada, fungsi akan kembali sebelum mengubah pointer tail apa pun.

Untuk grup yang lengkap, saya menyimpan groupNext. Saya menginisialisasi prev ke groupNext, lalu menerapkan pembalikan standar tiga pointer dari head grup lama hingga mencapai groupNext. Inisialisasi itu penting: ketika head lama menjadi tail, next-nya sudah mencapai segmen berikutnya. Setelah pembalikan, kth menjadi head yang baru. Saya menyambungkan groupPrev.next ke node tersebut dan memindahkan groupPrev ke head yang lama.

Invariannya adalah bahwa prefix yang diproses sudah benar dan terhubung, groupPrev.next adalah node pertama yang belum diproses, dan suffix tetap dalam urutan input. Pembalikan lengkap memperluas prefix; grup yang tidak lengkap tidak memicu penulisan apa pun, sehingga menjaga tail. Setiap node dikunjungi paling banyak sekali untuk lookahead dan sekali untuk pembalikan, sehingga waktunya adalah O(n) dan ruang ekstranya adalah O(1). Saya juga akan memverifikasi identitas node dan sifat asikliknya, bukan hanya urutan nilainya."

Kesalahan Umum

• Membalik sebelum mengonfirmasi grup lengkap → tail yang tidak lengkap termutasi dan sulit dipulihkan →

lakukan lookahead read-only terlebih dahulu.

• Memulai pembalikan dengan prev = null → grup terlepas sementara dari suffix dan mudah tertinggal dalam kondisi

terputus → mulai dengan prev = groupNext.

• Hanya menyambungkan head grup baru → tail baru mungkin tidak terhubung ke suffix → **pertahankan groupNext dan

verifikasi bahwa tail baru menunjuk ke sana.**

• Mempertahankan kth sebagai predecessor berikutnya → batas grup berikutnya menjadi salah → **pindahkan groupPrev ke head

grup yang lama.**

• Menukar nilai node → identitas node dan semantik field yang terkait menjadi rusak → ubah hanya next.
• Mengklaim ruang tambahan rekursif adalah O(1) → call stack bertambah seiring jumlah grup → **gunakan iterasi untuk

ruang ekstra konstan.**

• Hanya menguji urutan nilai → node yang hilang, disalin, atau bersiklus mungkin luput dari deteksi → **verifikasi juga identitas

referensi, jumlah node, dan sifat asiklik.**

• Mengalikan lookahead dengan pembalikan menjadi O(nk) → grup-grup bersifat disjoint antar iterasi → **jumlahkan total kunjungan

per node.**

Pertanyaan Lanjutan dan Tanggapan

Lanjutan 1: Bagaimana jika grup terakhir yang lebih kecil dari k juga harus dibalik?

Lookahead yang gagal tidak bisa lagi langsung mengembalikan hasil. Fungsi dapat menghitung jumlah node yang tersisa dan membalik segmen yang lebih pendek tersebut, atau algoritma dapat menghitung panjang list terlebih dahulu dan menggunakan min(k, remaining) sebagai ukuran grup. Bagian terminasi dari invarian berubah, dan kasus uji dengan n < k menjadi wajib.

Lanjutan 2: Bagaimana cara membalik grup secara selang-seling (alternating groups)?

Lanjutkan lookahead untuk setiap grup k node yang lengkap dan simpan flag boolean. Grup yang dibalik menggunakan logika asli; grup yang dilewati membiarkan pointer tidak tersentuh dan memajukan groupPrev sebanyak k node. Klarifikasi kembali aturan tail yang tidak lengkap, karena apakah tail dihitung sebagai grup yang dilewati atau dibalik akan mengubah hasilnya.

Lanjutan 3: Bagaimana Anda membuktikan algoritma tidak menciptakan siklus?

Pembuktian lokal menggunakan dua batas: simpan groupNext, yang berada di luar grup saat ini, dan lakukan pembalikan mulai dari prev = groupNext hingga current === groupNext. Setiap pointer yang ditulis ulang menunjuk dari node saat ini ke predecessor yang sudah diproses atau ke titik masuk suffix, tidak pernah kembali ke bagian grup saat ini yang belum diproses. Pengujian juga harus menjalankan pemeriksaan siklus pointer fast-slow dan memastikan jumlah node yang dilintasi sama dengan jumlah input.

Lanjutan 4: Apa yang berubah untuk list dengan seratus juta node?

Batas asimtotik tetap sama, tetapi rekursi harus dihindari, node tidak boleh disalin, serta perilaku timeout dan pembatalan (cancellation) menjadi penting untuk satu operasi yang panjang. Jika list berada di penyimpanan eksternal atau tersebar di beberapa mesin, penyambungan pointer acak dan visibilitas atomik mendominasi masalah. Algoritma in-memory tidak dapat ditransfer secara langsung; tata letak data, batas transaksi, dan checkpoint yang dapat dipulihkan harus didefinisikan terlebih dahulu.