Wawancara Koding: Bagaimana Cara Menghitung Edit Distance dengan Pemrograman Dinamis?

Masalah dan skenario yang berlaku

Diberikan dua string source dan target, kembalikan jumlah minimum pengeditan yang diperlukan untuk mengubah source menjadi target. Satu pengeditan dapat berupa menyisipkan satu karakter, menghapus satu karakter, atau mengganti satu karakter. Setiap operasi berbiaya satu. Salah satu string boleh kosong, dan keduanya hanya berisi huruf kecil bahasa Inggris.

source = "horse"
target = "ros"

horse -> rorse   replace h with r
rorse -> rose    delete r
rose  -> ros     delete e

answer = 3

Misalkan m = source.length dan n = target.length, dengan panjang kedua string paling banyak 2.000. Tugas ini hanya menanyakan biaya minimum, bukan skrip pengeditan (edit script). Makalah Wagner–Fischer mendefinisikan koreksi string sebagai urutan berbiaya minimum dari penyisipan, penghapusan, dan substitusi, serta memberikan algoritma yang waktunya sebanding dengan hasil kali kedua panjang string tersebut. Panduan wawancara tahun 2026 saat ini masih menggunakan edit distance sebagai latihan pemrograman dinamis kanonikal untuk dua string. Ini mendukung nilai persiapan dari topik tersebut; hal ini tidak membuktikan frekuensi atau atribusi perusahaan tertentu.

Masalah ini muncul dalam pemeriksaan ejaan (spell checking), pencocokan fuzzy (fuzzy matching), penautan rekaman (record linkage), dan perbandingan sekuens, tetapi definisi pada sistem produksi mungkin menggunakan operasi berbobot, transposisi, normalisasi, atau token khusus domain. Versi wawancara secara sengaja menetapkan biaya satu unit untuk pengeditan karakter agar status (state) dan pembuktiannya tidak ambigu.

Apa yang dievaluasi pewawancara

Sinyal pertama adalah definisi status (state definition) dengan batasan yang tepat. Definisikan dp[i][j] sebagai edit minimum yang diperlukan untuk mengubah i karakter pertama dari source menjadi j karakter pertama dari target. “Jawaban hingga i dan j” terlalu samar untuk menjustifikasi suatu transisi atau menginisialisasi prefiks kosong.

Sinyal kedua adalah menurunkan ketiga transisi karakter yang tidak cocok (mismatch). Operasi terakhir dari solusi optimal haruslah salah satu dari hapus (delete), sisipkan (insert), atau ganti (replace). Menghapus operasi terakhir tersebut akan menyisakan submasalah prefiks yang lebih kecil. Kandidat harus memetakan setiap operasi ke sel tetangga yang benar, alih-alih sekadar menghafal tiga koordinat.

Sinyal ketiga adalah menangani karakter akhir yang cocok tanpa menciptakan pekerjaan tambahan. Jika source[i - 1] sama dengan target[j - 1], solusi optimal dapat membiarkan karakter tersebut tidak berubah, sehingga nilainya berasal dari dp[i - 1][j - 1]. Pembuktian juga harus menunjukkan bahwa tidak ada solusi yang lebih murah yang tersembunyi di balik pilihan ini.

Sinyal keempat adalah mengenali bentuk ketergantungan (dependency shape). Sebuah baris hanya menggunakan baris sebelumnya dan sel kirinya sendiri, sehingga matriks O(mn) penuh tidak diperlukan jika hanya jarak (distance) yang dikembalikan. Menempatkan string yang lebih pendek pada dimensi kolom akan menghasilkan ruang bantu O(min(m, n)).

Sinyal terakhir adalah menjaga kontrak masalah. Menukar string baris dan kolom valid di sini karena biaya satuan penyisipan dan penghapusan membuat jaraknya simetris. Hal ini tidak otomatis valid jika penyisipan dan penghapusan memiliki bobot yang berbeda. Teks Unicode juga memerlukan pilihan eksplisit antara UTF-16 code units, Unicode code points, dan grapheme clusters yang dirasakan pengguna.

Pertanyaan untuk diklarifikasi sebelum menjawab

• Operasi apa saja yang diizinkan? Masalah ini mengizinkan penyisipan, penghapusan, dan penggantian. Transposisi

karakter yang bersebelahan bukan satu operasi tunggal.

• Berapa biaya satu pengeditan? Setiap operasi yang diizinkan berbiaya satu. Biaya berbobot akan mengubah rekurensi dan dapat

menghilangkan simetri.

• Apa unit perbandingannya? Soal menggunakan huruf kecil bahasa Inggris, jadi pengindeksan JavaScript aman untuk

implementasi ini. Teks Unicode umum memerlukan kontrak terpisah.

• Apakah kita hanya mengembalikan jaraknya atau skrip pengeditannya? Hanya jaraknya. Rekonstruksi operasi biasanya

memerlukan penyimpanan tabel penuh atau informasi pendahulu (predecessor) yang eksplisit.

• Apakah salah satu input boleh kosong? Ya. Mengubah string kosong menjadi prefiks dengan panjang j memerlukan tepat j

penyisipan; sebaliknya memerlukan i penghapusan.

• Berapa batas ukurannya? Panjang hingga 2.000 membuat waktu O(mn) dapat diterima, tetapi membuat rekursi eksponensial

dan memori tabel penuh yang tidak perlu menjadi tidak diinginkan.

• Bisakah input ditukar untuk menghemat memori? Ya di bawah kontrak biaya satuan ini karena jaraknya

simetris. Nyatakan asumsi tersebut sebelum menggunakannya.

Kerangka jawaban 30 detik

“Saya mendefinisikan dp[i][j] sebagai edit minimum dari i karakter source pertama ke j karakter target pertama. Biaya prefiks kosong menginisialisasi baris dan kolom pertama. Karakter akhir yang sama menggunakan nilai diagonal tanpa perubahan. Jika tidak, edit terakhir adalah hapus, sisipkan, atau ganti, jadi saya mengambil satu ditambah nilai minimum dari sel di atas, di kiri, dan diagonal. Setiap sel hanya bergantung pada baris sebelumnya dan nilai kiri baris saat ini, jadi saya menempatkan string yang lebih pendek pada kolom dan mempertahankan dua baris. Itu memberikan waktu O(mn) dan ruang O(min(m, n)). Saya memverifikasi string kosong, string yang sama, panjang asimetris, dan hasilnya terhadap referensi tabel penuh pada input kecil.”

Solusi mendalam langkah demi langkah

Mulai dari prefiks. Misalkan dp[i][j] adalah jumlah minimum edit yang diizinkan untuk mengubah source[0..i - 1] menjadi target[0..j - 1].

Batasan prefiks kosong mengikuti langsung dari kontrak:

dp[0][j] = j   // insert all j target characters
dp[i][0] = i   // delete all i source characters

Untuk prefiks yang tidak kosong, periksa karakter akhirnya. Jika cocok, mempertahankan karakter akhir yang sama tersebut akan mereduksi masalah menjadi dua prefiks yang lebih pendek:

if source[i - 1] == target[j - 1]:
  dp[i][j] = dp[i - 1][j - 1]

Jika berbeda, klasifikasikan edit terakhir dari urutan optimal apa pun:

delete source[i - 1]:       dp[i - 1][j]     + 1
insert target[j - 1]:       dp[i][j - 1]     + 1
replace the final character: dp[i - 1][j - 1] + 1

dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])

Kasus-kasus ini bersifat menyeluruh (exhaustive) karena operasi terakhir harus berupa salah satu dari tiga edit yang diizinkan. Kasus-kasus ini bersifat konstruktif: tambahkan edit yang disebutkan ke solusi optimal untuk prefiks lebih kecil yang dipilih, dan itu menghasilkan solusi yang valid untuk (i, j). Sebaliknya, hapus edit terakhir dari solusi optimal mana pun; sisanya menyelesaikan prefiks lebih kecil yang bersesuaian, sehingga biayanya tidak boleh lebih murah daripada sel tersebut. Ini membuktikan rekurensi untuk ketidakcocokan.

Untuk karakter akhir yang cocok, ada solusi optimal yang membiarkannya tetap cocok. Jika suatu urutan optimal mengedit karakter akhir source atau target, hapus efek akhir tersebut dan sejajarkan karakter yang sama sebagai gantinya; hal ini tidak menambah biaya. Sisa pekerjaannya tepat merupakan submasalah prefiks diagonal. Induksi pada i + j, yang berpijak pada batasan prefiks kosong, membuktikan setiap sel dan oleh karena itu membuktikan dp[m][n].

Hanya tiga nilai sebelumnya yang diperlukan saat mengisi baris: previous[j] untuk penghapusan, current[j - 1] untuk penyisipan, dan previous[j - 1] untuk penggantian atau kecocokan. Kode menjadikan string yang lebih pendek sebagai kolom. Pertukaran tersebut merupakan optimasi memori di bawah definisi biaya satuan yang simetris ini; itu tidak mengubah jawabannya.

export function editDistance(source: string, target: string): number {
  const rows = source.length >= target.length ? source : target
  const columns = source.length >= target.length ? target : source

  let previous = Array.from(
    { length: columns.length + 1 },
    (_, index) => index,
  )

  for (let row = 1; row <= rows.length; row += 1) {
    const current = new Array<number>(columns.length + 1)
    current[0] = row

    for (let column = 1; column <= columns.length; column += 1) {
      if (rows[row - 1] === columns[column - 1]) {
        current[column] = previous[column - 1]
        continue
      }

      const deleteCost = previous[column] + 1
      const insertCost = current[column - 1] + 1
      const replaceCost = previous[column - 1] + 1
      current[column] = Math.min(deleteCost, insertCost, replaceCost)
    }

    previous = current
  }

  return previous[columns.length]
}

Untuk source = "horse" dan target = "ros", dimensi kolom yang lebih pendek memiliki panjang tiga. Baris terakhir berakhir pada angka tiga, cocok dengan urutan satu-penggantian-plus-dua-penghapusan. Algoritma mengembalikan biaya; algoritma tidak mengklaim bahwa urutan edit tertentu ini bersifat unik.

Kompleksitas, batasan, dan pilihan rekayasa

Algoritma mengisi (m + 1)(n + 1) status konseptual, sehingga waktu yang dibutuhkan adalah O(mn). Setiap baris memiliki min(m, n) + 1 entri, dan hanya ada dua baris yang ada secara bersamaan, sehingga ruang bantu adalah O(min(m, n)). Mengalokasikan ulang satu baris per iterasi tidak mengubah batas asimtotik; dua array yang dapat digunakan kembali dapat mengurangi beban alokasi tanpa mengubah algoritma.

Jawaban maksimum di bawah operasi satuan penyisipan, penghapusan, dan penggantian adalah max(m, n): ganti min(m, n) karakter pertama, lalu sisipkan atau hapus selisih panjangnya. Nilai minimumnya setidaknya |m - n|, karena setiap edit mengubah panjang paling banyak satu. Batas-batas ini adalah asersi yang berguna dalam pengujian.

Untuk string JavaScript umum, pengindeksan beroperasi pada UTF-16 code units. Iterasi string mempertahankan surrogate pairs dengan menghasilkan Unicode code points, tetapi masih dapat memecah satu grapheme cluster seperti emoji ditambah warna kulit atau urutan zero-width-joiner. Fitur similaritas produksi harus memutuskan apakah pengeditan berlaku untuk code units, code points, grapheme clusters yang dinormalisasi, kata, atau token domain sebelum memilih tokenizer. Normalisasi diam-diam juga dapat mengubah semantik produk, sehingga hal ini termasuk dalam kontrak, bukan di dalam loop DP ini.

Jika pemanggil hanya menanyakan apakah jaraknya paling banyak k, tolak terlebih dahulu jika |m - n| > k, lalu evaluasi hanya pita diagonal (diagonal band) dan berhenti saat tidak ada status di pita aktif yang dapat tetap berada dalam batas k. Itu adalah kontrak output yang berbeda; implementasi jarak penuh sebaiknya tidak menambahkan kompleksitas tersebut secara spekulatif.

Contoh jawaban berkualitas tinggi

“Saya akan memodelkan masalah ini pada prefiks. Misalkan dp[i][j] adalah biaya minimum untuk mengubah i karakter source pertama menjadi j karakter target pertama. Batasan prefiks kosong adalah panjangnya masing-masing. Untuk karakter akhir yang sama, saya mempertahankan nilai diagonal. Untuk karakter akhir yang berbeda, saya mengklasifikasikan urutan optimal berdasarkan edit terakhirnya: menghapus menggunakan sel di atas, menyisipkan menggunakan sel di kiri, dan mengganti menggunakan diagonal, dengan menambahkan satu ke nilai minimumnya. Kasus-kasus tersebut bersifat menyeluruh, dan menghapus edit terakhir membuktikan rekurensi dari arah sebaliknya.

“Karena sebuah sel hanya menggunakan baris sebelumnya dan sel kiri pada baris saat ini, saya menyimpan dua baris. Biaya satuan penyisipan dan penghapusan membuat jarak ini simetris, sehingga string yang lebih pendek dapat menjadi kolom dan memori menjadi O(min(m, n)); waktu tetap O(mn). Saya tidak akan menggunakan pertukaran itu untuk bobot asimetris. Saya akan menguji kedua arah string kosong, string yang sama, contoh horse ke ros, dan string pendek yang dihasilkan terhadap versi tabel penuh. Jika pewawancara memerlukan skrip pengeditan, saya akan menyimpan informasi pendahulu alih-alih berjanji untuk memulihkannya dari baris yang ditimpa.”

Kesalahan umum

• Menggunakan pencocokan karakter secara greedy → karakter yang berulang dan pergeseran berikutnya membuat edit yang tampak menguntungkan secara lokal kehilangan

minimum global → definisikan status prefiks optimal dan bandingkan semua operasi akhir yang valid.

• Menginisialisasi baris dan kolom pertama ke nol → kasus string kosong menjadi gratis → **atur biaya batas

ke panjang prefiksnya masing-masing.**

• Tertukar antara tetangga insert dan delete → kode mungkin lolos contoh simetris tetapi gagal pada

prefiks asimetris → jelaskan string apa yang tersisa setelah menghapus operasi terakhir.

• Menambahkan satu saat karakter akhir cocok → karakter sama yang tidak berubah dikenai biaya sebagai penggantian → **salin

nilai diagonal persis apa adanya saat cocok.**

• Mengembalikan jawaban rolling-row sambil menjanjikan skrip pengeditan → pendahulu yang tertimpa tidak dapat merekonstruksi

jalur → simpan matriks atau backpointers jika operasi diperlukan.

• Menukar string di bawah bobot asimetris → penyisipan dalam satu arah menjadi penghapusan di arah lain →

pertahankan orientasi asli kecuali model biaya bersifat simetris.

• Menyebut indeks JavaScript sebagai “karakter” untuk sembarang Unicode → surrogate pairs atau grapheme clusters akan

terhitung secara tidak terduga → definisikan dan lakukan tokenisasi pada unit perbandingan secara eksplisit.

Kumpulan pengujian yang terfokus mencakup ("", "") = 0, ("", "abc") = 3, ("abc", "") = 3, ("same", "same") = 0, ("aaaa", "aa") = 2, ("horse", "ros") = 3, dan ("intention", "execution") = 5. Bandingkan implementasi rolling dengan referensi tabel penuh di seluruh string pendek dari alfabet kecil. Periksa juga identitas, simetri di bawah model biaya ini, |m - n| ≤ d ≤ max(m, n), dan pertidaksamaan segitiga pada pasangan tiga string (triples) yang dihasilkan. Terakhir, jalankan input dengan panjang 2.000 yang sama dan yang berbeda sepenuhnya untuk memastikan jalur ukuran ekstrem tetap berada dalam perkiraan waktu kuadratik dan ruang linear.

Pertanyaan lanjutan dalam wawancara

Lanjutan 1: Bagaimana Anda mengembalikan operasi pengeditan sebenarnya?

Pertahankan tabel penuh dan lakukan backtracking dari (m, n). Kecocokan akan bergerak secara diagonal tanpa menghasilkan operasi; jika tidak, pilih sel tetangga yang nilainya ditambah biaya edit yang sesuai sama dengan nilai saat ini. Tentukan aturan pemutus seri (tie-break) yang stabil karena mungkin ada beberapa skrip minimum. Metode langsung ini menggunakan ruang O(mn). Rekonstruksi ruang linear dimungkinkan dengan teknik divide-and-conquer, tetapi itu adalah algoritma terpisah dan hanya boleh diperkenalkan jika persyaratan memori menuntutnya.

Lanjutan 2: Apa yang berubah jika operasi memiliki bobot yang berbeda?

Tambahkan bobot yang relevan ke setiap transisi, bukan nilai satu. Pembuktian optimal-substructure yang sama tetap berlaku jika biaya bernilai non-negatif dan didefinisikan oleh kontrak. Jika biaya penyisipan dan penghapusan berbeda, jarak mungkin bersifat berarah (directional), sehingga menukar string untuk memperpendek baris tidak lagi otomatis benar. Biaya edit negatif merusak interpretasi umum dan mengharuskan peninjauan ulang model.

Lanjutan 3: Bagaimana Anda mendukung transposisi yang bersebelahan?

Pertama, perjelas apakah transposisi hanya menukar karakter yang bersebelahan dan apakah transposisi yang tumpang tindih (overlapping) diizinkan. Rekurensi restricted optimal-string-alignment dapat memeriksa dua karakter sebelumnya tambahan dan sebuah sel dua baris dan kolom ke belakang. Jarak Damerau–Levenshtein penuh memiliki persyaratan status yang berbeda. Hanya menambahkan satu pemeriksaan diagonal informal dapat mengimplementasikan varian yang salah.

Lanjutan 4: Apa hubungannya dengan longest common subsequence (LCS)?

Jika penggantian dilarang atau berbiaya sama dengan satu penghapusan ditambah satu penyisipan, jarak penyisipan-dan-penghapusan dapat diturunkan dari LCS sebagai m + n - 2 * LCS(source, target). Dengan biaya penggantian satu unit, rumus tersebut secara umum bukanlah edit distance: mengganti satu karakter yang tidak cocok berbiaya satu, sedangkan hapus-plus-sisip berbiaya dua. Nyatakan biaya operasi sebelum menggunakan relasi tersebut.

Lanjutan 5: Bagaimana Anda menjawab “apakah jaraknya paling banyak k?” secara lebih cepat?

Kembalikan false segera jika selisih panjangnya melebihi k. Jika tidak, hitung hanya status dalam batas k dari diagonal utama, anggap sel di luar pita tidak dapat dijangkau, dan berhenti jika frontier aktif tidak dapat kembali ke dalam anggaran biaya. Ini dapat mengurangi pekerjaan secara signifikan ketika k bernilai kecil, sedangkan kasus terburuk untuk jarak tanpa batasan tetap kuadratik.

Lanjutan 6: Bagaimana Anda menangani teks Unicode nyata yang terlihat oleh pengguna?

Pilih unit bersama product owner. Iterasi code-point mencegah pemisahan surrogate pairs, tetapi masih dapat memisahkan beberapa karakter yang dirasakan pengguna. Segmentasi grapheme lebih cocok dengan karakter yang terlihat, dan normalisasi Unicode dapat membuat urutan yang setara secara kanonikal dibandingkan secara konsisten. Locale, case folding, aksen, dan aturan tingkat token adalah keputusan produk. Terapkan prapemrosesan tersebut sebelum DP dan uji contoh dari bahasa-bahasa yang didukung.

Lanjutan 7: Bisakah satu baris menggantikan dua baris?

Ya. Sebelum menimpa dp[j], simpan nilai lamanya sebagai diagonal berikutnya; dp[j] masih mewakili sel di atas, dan dp[j - 1] sudah mewakili sel kiri dari baris saat ini. Ini mengurangi faktor konstan, bukan ruang asimtotik. Dalam wawancara, dua baris sering kali lebih mudah dibuktikan dan lebih minim kesalahan kecuali jika pewawancara secara khusus meminta varian in-place.