Wawancara coding: Memvalidasi urutan byte UTF-8

Petunjuk dan ruang lingkup

Ini adalah masalah manipulasi bit dan encoding karakter. Inputnya adalah sebuah byte array, bukan string Unicode yang sudah didekodekan. Tentukan apakah setiap skalar menggunakan 1 hingga 4 byte dan tolak urutan yang terpotong atau salah format (malformed). LeetCode 393 menggunakan batasan yang sama: panjang paling banyak 2 * 10^4, dengan setiap integer menyumbangkan 8 bit terendahnya. RFC 3629 mendefinisikan bentuk-bentuk UTF-8 1–4 byte dan rentang nilai skalar yang valid.

Apa yang diuji oleh pewawancara

• Menurunkan jumlah lanjutan dari pola leading byte (byte awal).
• Memeriksa awalan lanjutan 10xxxxxx secara ketat.
• Menolak byte lanjutan ekstra, pemotongan, dan pola leading byte lima byte.
• Menghasilkan solusi satu lintasan dengan waktu O(n) dan ruang ekstra O(1).

Klarifikasi yang perlu ditanyakan terlebih dahulu

Konfirmasikan apakah setiap elemen dijamin berada dalam 0..255; jika tidak, tolak nilai di luar rentang terlebih dahulu. Perjelas juga apakah tugas ini hanya memeriksa bentuk byte atau harus menolak overlong encoding, titik kode surrogate, dan nilai di atas U+10FFFF. Versi LeetCode berfokus pada bentuk byte; parser tingkat produksi harus menerapkan aturan nilai skalar RFC 3629 yang lebih ketat.

Jawaban 30 detik

Pertahankan remaining, yaitu jumlah byte lanjutan yang masih diperlukan untuk karakter saat ini. Untuk byte awal, gunakan pola bit tingginya untuk menetapkan 0, 1, 2, atau 3; untuk byte lanjutan, wajibkan (byte & 0b11000000) === 0b10000000 dan kurangi penghitung. Tolak byte awal yang tidak valid, lanjutan yang tidak terduga, atau akhir input dengan remaining !== 0. Pemindaian hanya menyimpan penghitung ini.

Solusi langkah demi langkah

1. Mengenali pola leading byte

0xxxxxxx adalah karakter satu byte; 110xxxxx, 1110xxxx, dan 11110xxx membutuhkan 1, 2, dan 3 byte lanjutan. Uji awalan dengan mask: periksa 0x80, lalu 0xE0, 0xF0, dan terakhir 0xF8. Jika pengujian 0xF8 masih bernilai bukan nol, byte tersebut memulai bentuk lima byte atau lebih panjang dan harus ditolak.

2. Memvalidasi byte lanjutan secara online

Ketika remaining > 0, byte saat ini harus cocok dengan 10xxxxxx. Kurangi penghitung setelah pemeriksaan berhasil. Byte awal ASCII atau byte awal multi-byte lainnya dalam status ini langsung tidak valid. Tidak diperlukan backtracking atau pemotongan (slicing), dan pemotongan terdeteksi saat input berakhir.

3. Implementasi rujukan

isValidUtf8(bytes):
  remaining = 0
  for byte in bytes:
    if byte < 0 or byte > 255: return false
    if remaining > 0:
      if (byte & 0b11000000) != 0b10000000: return false
      remaining -= 1
      continue
    if (byte & 0b10000000) == 0:
      remaining = 0
    else if (byte & 0b11100000) == 0b11000000:
      remaining = 1
    else if (byte & 0b11110000) == 0b11100000:
      remaining = 2
    else if (byte & 0b11111000) == 0b11110000:
      remaining = 3
    else:
      return false
  return remaining == 0

4. Ketatnya standar tingkat produksi

Penghitungan awalan saja masih menerima beberapa overlong encoding, seperti merepresentasikan nilai dengan tiga byte padahal satu byte sudah cukup, dan mungkin menerima nilai surrogate. Parser produksi harus mengakumulasikan nilai skalar dan memeriksa nilai minimum untuk panjangnya, rentang surrogate, serta batas atas U+10FFFF; putuskan secara eksplisit apakah BOM diizinkan. Nyatakan batasan latihan terlebih dahulu, lalu jelaskan ekstensi ini alih-alih mencampuradukkan aturan secara diam-diam.

5. Pengujian dan kompleksitas

Cakup [197,130,1] sebagai true, [235,140,4] sebagai false, byte lanjutan yang terisolasi [128], [226,130] yang terpotong, byte awal lima byte [248,128,128,128,128], dan array kosong. Setiap byte dipindai sekali: waktu O(n) dan ruang ekstra O(1), di mana n adalah panjang array.

Jawaban model

Saya memisahkan pengenalan leading byte dari validasi byte lanjutan. Byte awal yang cocok dengan 0xxxxxxx, 110xxxxx, 1110xxxx, atau 11110xxx menetapkan remaining ke 0, 1, 2, atau 3; status lanjutan hanya menerima 10xxxxxx dan mengurangi penghitung. Byte awal lima byte, lanjutan yang tidak terduga, elemen di luar rentang, atau akhir input dengan karakter yang tidak lengkap akan mengembalikan false. Implementasinya adalah satu lintasan O(n) dengan ruang O(1). Untuk produksi, akumulasikan nilai skalar untuk menolak overlong encoding, surrogate, dan nilai di atas U+10FFFF.

Kesalahan umum

• Menghitung byte lanjutan tanpa memeriksa setiap awalan 10.
• Menganggap 111110xx sebagai bentuk lima byte yang valid.
• Melupakan pemeriksaan akhir remaining dan menerima urutan yang terpotong.
• Mendelegasikan ke decoder bahasa bawaan tanpa menunjukkan invarian tingkat bit atau indeks kesalahan.
• Mencampuradukkan pemeriksaan bentuk LeetCode dengan aturan nilai skalar RFC tanpa menyatakan ruang lingkupnya.
• Memperlakukan byte sebagai signed dan gagal menormalisasinya ke 0..255 sebelum operasi bit.

Pertanyaan lanjutan

Bagaimana Anda mengembalikan indeks kesalahan pertama?

Kembalikan {valid, errorIndex, reason}. Catat indeks saat ini ketika pemeriksaan byte awal, lanjutan, atau akhir input gagal. Status pemindaian tetap tidak berubah, sehingga pemanggil dapat menyorot byte asli.

Bagaimana Anda mendukung input streaming terpotong-potong (chunked streaming)?

Pertahankan remaining dan status skalar parsial dalam objek parser di antara potongan data (chunk). Karakter hanya selesai setelah chunk berikutnya menyediakan semua byte lanjutan; akhir aliran dengan remaining != 0 tetap merupakan kesalahan pemotongan (truncation error).

Mengapa tidak hanya menggunakan regular expression?

Regular expression dapat mengekspresikan beberapa aturan awalan, tetapi state machine lebih jelas untuk batas chunk, indeks kesalahan, dan batasan nilai skalar. Penghitung menggunakan ruang konstan untuk input dengan panjang berapa pun dan dapat diperluas secara alami ke validasi ketat.

Bagaimana cara Anda menolak overlong encoding?

Catat panjang urutan dan nilai akumulasi dari byte awal, lalu syaratkan nilai tersebut memenuhi rentang minimum panjang tersebut. Tolak juga 0xD800..0xDFFF dan nilai di atas 0x10FFFF.

Bagaimana Anda menangani input berukuran besar yang mencurigakan (hostile oversized input)?

Biarkan pemanggil menerapkan batas byte, batas waktu (timeout), dan kebijakan pengambilan sampel kesalahan. Parser itu sendiri mempertahankan status O(1) dan melakukan short-circuit pada kesalahan pasti pertama, sehingga input yang malformed tidak memerlukan buffer tambahan.