Wawancara Coding: Swap bersebelahan minimum untuk membuat palindrom

Petunjuk dan konteks

Setiap swap bersebelahan bernilai satu. Karakter dapat berulang, dan input bisa tidak memungkinkan jika lebih dari satu karakter memiliki frekuensi ganjil. Tujuannya adalah jumlah swap minimum, bukan sembarang palindrom.

Apa yang diuji oleh pewawancara

• Menurunkan syarat kelayakan frekuensi ganjil.
• Mencocokkan karakter kiri dengan pasangan valid terdekat dari kanan.
• Membuktikan mengapa pilihan greedy optimal dan memperhitungkan pergeseran (shift).

Pertanyaan klarifikasi sebelum menjawab

• Apakah swap hanya dilakukan antar elemen bersebelahan, dan apakah setiap swap berbiaya satu?
• Apakah alfabetnya bebas, dan apakah code point Unicode diperlakukan sebagai karakter?
• Apakah fungsi harus memutasi array atau hanya mengembalikan jumlahnya?
• Berapa ukuran input yang menentukan apakah pendekatan O(n²) dapat diterima?

Kerangka jawaban 30 detik

Hitung frekuensi ganjil terlebih dahulu; lebih dari satu jumlah ganjil membuat pembentukan palindrom menjadi tidak mungkin. Gunakan pointer di kedua ujung. Jika kedua ujung cocok, bergerak ke dalam. Jika tidak, cari karakter yang cocok untuk ujung kiri dengan memindai dari batas kanan ke dalam, geser (bubble) ke arah kanan dengan swap bersebelahan, dan hitung setiap langkah. Jika tidak ada kecocokan, karakter yang tidak cocok tersebut pastilah elemen tengah tunggal; pindahkan ke arah tengah dan lanjutkan.

Pembahasan mendalam langkah demi langkah

1. Buktikan kelayakan

Sebuah palindrom memiliki paling banyak satu frekuensi ganjil, karena pasangan-pasangan menempati posisi simetris dan hanya elemen tengah pada panjang ganjil yang boleh tidak memiliki pasangan. Pemeriksaan ini mencegah eksekusi loop greedy pada input yang tidak memungkinkan.

2. Cocokkan batas-batas

Untuk pointer i dan j, jika s[i] sama dengan s[j], kedua posisi sudah tetap. Jika tidak, cari k dari j turun ke i + 1 untuk s[k] == s[i]. Memindahkan karakter tersebut ke kanan membutuhkan j - k swap dan mempertahankan prefiks yang sudah ditetapkan.

3. Tangani karakter tengah

Jika tidak ditemukan kecocokan, s[i] adalah karakter berfrekuensi ganjil yang berada di posisi tengah. Pindahkan satu langkah ke kanan dalam satu waktu hingga mencapai tengah, sambil menghitung swap. Jangan membuangnya atau mengasumsikan elemen tengah harus ditemukan pada putaran pertama.

4. Terapkan simulasi

count odd frequencies
if odd_count > 1: return impossible
left = 0, right = n - 1, swaps = 0
while left < right:
    if s[left] == s[right]: left++, right--; continue
    k = right
    while k > left and s[k] != s[left]: k--
    if k == left:
        swap s[k] with s[k + 1]
        swaps++
    else:
        while k < right:
            swap s[k] with s[k + 1]
            k++, swaps++
        left++, right--
return swaps

5. Analisis kompleksitas dan ide pembuktian

Setiap proses pencarian dan bubbling dapat memindai O(n), diulang sebanyak O(n) kali, sehingga waktunya adalah O(n²) dan array yang dapat dimutasi menggunakan ruang ekstra O(1). Pasangan greedy adalah yang terdekat dengan batas; memindahkan karakter sama yang lebih jauh akan membutuhkan setidaknya jumlah swap yang sama sebelum batas dapat ditetapkan. Kasus elemen tengah dipaksakan oleh paritas.

Contoh jawaban berkualitas tinggi

“Saya pertama-tama menghitung frekuensi ganjil; lebih dari satu berarti tidak memungkinkan. Kemudian saya membandingkan kedua ujung. Jika tidak cocok, saya mencari karakter sama yang paling dekat dengan batas kanan dan melakukan bubbling ke posisinya, menambahkan jaraknya; jika tidak ada yang sama, karakter tersebut adalah elemen tengah ganjil yang unik, jadi saya memindahkannya ke arah tengah. Ujung yang cocok akan memperkecil jendela. Simulasinya membutuhkan waktu O(n²) dan ruang ekstra O(1), dan pilihan greedy bersifat optimal karena pasangan mana pun yang lebih jauh memerlukan setidaknya jumlah swap bersebelahan yang sama.”

Kesalahan umum

• Hanya memeriksa apakah jumlahnya genap → string dengan panjang ganjil dapat memiliki satu jumlah ganjil → izinkan paling banyak satu frekuensi ganjil.
• Melakukan swap dengan karakter cocok yang sembarang → pergerakan ekstra bisa menjadi tidak minimal → pilih pasangan terdekat dengan batas.
• Mengabaikan karakter yang tidak cocok → pergerakan ke tengah menjadi kurang terhitung → lakukan bubbling ke arah tengah.
• Menggunakan swap two-pointer tanpa pergeseran → biaya swap bersebelahan hilang → simulasikan setiap gerakan bersebelahan atau gunakan struktur data yang setara.

Pertanyaan lanjutan dan tanggapan

Bisakah algoritma juga mengembalikan palindromnya?

Ya. Pertahankan array yang dapat dimutasi dan kembalikan konten akhirnya beserta jumlah swap. Simulasi yang sama mencatat setiap swap bersebelahan jika pemanggil memerlukan urutannya.

Bagaimana Anda meningkatkannya untuk input besar?

Lacak posisi asli dengan Fenwick tree atau struktur order-statistics sehingga pemindahan karakter dapat memperbarui posisi dalam waktu logaritmik. Pemasangan greedy tetap dipertahankan, sementara perhitungan biaya menghindari pergeseran setiap elemen.

Bagaimana jika swap dilakukan secara bebas bukan bersebelahan?

Itu adalah model biaya yang berbeda. Pembuktian jarak pasangan terdekat tidak lagi berlaku; definisikan operasi yang diizinkan sebelum menggunakan kembali algoritma ini.