Wawancara coding: Bagaimana cara mengimplementasikan iterator yang dapat dilanjutkan (resumable) dan dapat diserialisasi (serializable)?

Pertanyaan dan konteks

Implementasikan iterator dengan get_state() dan set_state(): mulai dengan satu list, lalu kembangkan ke iterasi konkuren di beberapa sumber dan pembacaan asinkron. Bagaimana Anda mendefinisikan state, menjamin tidak ada duplikasi atau data yang terlewat setelah pemulihan, serta menangani penyelesaian, kegagalan, dan snapshot yang tidak valid?

Ini sesuai dengan catatan wawancara coding OpenAI publik yang perkembangannya mencakup iterator list, composite iterator multi-berkas, dan versi berbasis coroutine. Topik ini cocok untuk peran rekayasa coding umum, infrastruktur, pemrosesan data, dan machine learning. Tantangannya bukan menjeda sebuah generator; melainkan mengodekan "apa yang harus dikembalikan oleh pemanggilan berikutnya" sebagai state yang dapat diverifikasi dan diserialisasi.

Hal yang dievaluasi pewawancara

• Apakah Anda mendefinisikan semantik input, output, penyelesaian, dan error dari next() alih-alih mengandalkan hasNext()?
• Apakah Anda memisahkan objek runtime dari state yang dapat dipersistensikan?
• Dapatkah Anda membuktikan bahwa pemulihan tidak mengulang maupun melewatkan elemen yang telah dikirimkan?
• Apakah Anda melacak progres setiap sumber dan urutan penjadwalan global?
• Apakah Anda menangani pembacaan asinkron, pembatalan, percobaan ulang (retry), dan pembersihan sumber daya?
• Apakah Anda menguji sumber kosong, snapshot tidak valid, perubahan sumber, dan pemulihan idempoten?

Pertanyaan klarifikasi sebelum menulis kode

• Apakah sumber berupa list yang tidak dapat diubah (immutable), berkas append-only, atau stream eksternal yang dapat berubah? Jika dapat berubah, snapshot memerlukan versi atau fingerprint konten.
• Apakah pemulihan mengulang nilai terakhir yang dikembalikan atau dimulai pada nilai berikutnya yang belum dikembalikan? Jawaban ini menggunakan opsi kedua dan hanya memajukan kursor setelah pengiriman berhasil.
• Apakah urutan multi-sumber berupa round-robin, urutan waktu global, atau sumber-siap-pertama (any-ready-source-first)? Pilihan ini mengubah field state dan pembuktian keadilan (fairness).
• Haruskah get_state() bertahan dari perubahan proses atau versi skema? Jika ya, simpan hanya skalar berversi dan ID sumber, jangan pernah menyimpan file handle, promise, atau objek generator.

Jawaban 30 detik

"Pertama-tama, saya mendefinisikan checkpoint sebagai elemen yang akan dikembalikan oleh pemanggilan next() berikutnya. Satu list menyimpan indeks dan versi sumber; beberapa sumber menyimpan setiap kursor ditambah state penjadwal. next() memajukan kursor hanya setelah pengiriman berhasil, sehingga memulihkan state yang sama akan mengembalikan elemen yang sama dan tidak mengulangi elemen yang telah dikonfirmasi. Snapshot berupa JSON berversi, yang divalidasi terhadap fingerprint dan batas sumber sebelum dipulihkan. Versi asinkron memisahkan I/O yang sedang berjalan dari state yang dapat dipulihkan, mendukung pembatalan, pembersihan, dan percobaan ulang per sumber, serta tidak pernah menserialisasi handle runtime."

Jawaban mendalam langkah demi langkah

Langkah 1: Tentukan antarmuka minimal dan checkpoint

Gunakan next(), get_state(), dan set_state(state) tanpa menambahkan hasNext(). Iterator terbatas (finite) mengembalikan satu hasil selesai yang konsisten atau memunculkan exception penyelesaian yang disepakati; pemanggil tidak boleh memeriksa ke depan dan menebak state.

Tempatkan checkpoint pada "item berikutnya", bukan "item terakhir". Sumber list dapat menyimpan {sourceId, version, index, done}. next() membaca items[index] dan menambah indeks hanya setelah nilai berhasil dikirimkan; kegagalan membaca membiarkan state tidak berubah untuk percobaan ulang.

class ListIterator:
    def __init__(self, items, source_id, version):
        self.items = items
        self.source_id = source_id
        self.version = version
        self.index = 0

    def next(self):
        if self.index == len(self.items):
            return {"done": True}
        value = self.items[self.index]
        self.index += 1
        return {"done": False, "value": value}

    def get_state(self):
        return {
            "schema": 1,
            "sourceId": self.source_id,
            "version": self.version,
            "index": self.index,
        }

    def set_state(self, state):
        if state["schema"] != 1 or state["sourceId"] != self.source_id:
            raise ValueError("incompatible state")
        if state["version"] != self.version or not 0 <= state["index"] <= len(self.items):
            raise ValueError("stale or invalid state")
        self.index = state["index"]

Langkah 2: Nyatakan invarian dan buktikan pemulihan

Invarian utamanya adalah bahwa index sama dengan jumlah elemen yang berhasil dikirimkan; indeks snapshot sama dengan kursor dalam memori; dan versi sumber tidak berubah. next() hanya maju setelah mengembalikan nilai, sedangkan set_state() hanya menerima versi yang cocok dan batas yang valid, sehingga checkpoint yang sama menghasilkan sufiks yang sama.

Jika kontrak bisnisnya adalah at-least-once dan bukan exactly-once, mengulangi item terakhir antara pengiriman dan checkpoint dapat diterima, tetapi state harus menyertakan penanda konfirmasi (acknowledgement) atau kunci idempoten. Jangan mencampur kedua semantik dalam satu kontrak set_state().

Langkah 3: Kembangkan ke beberapa sumber

Composite iterator menyimpan state children[sourceId] independen dan state penjadwal seperti antrean round-robin, set sumber yang telah selesai, dan nomor urut. Round-robin memilih sumber berikutnya yang belum selesai; pengurutan global mengharuskan penyimpanan elemen terdepan yang telah diambil sebelumnya (prefetched head) dari setiap sumber agar perbandingan dapat direproduksi setelah pemulihan.

Snapshot multi-sumber dapat berupa {schema, children: [{id, state}], scheduler: {kind, cursor}, emitted}. Validasi keanggotaan dan urutan sumber terlebih dahulu, pulihkan child berikutnya, dan pulihkan penjadwal terakhir. Jumlah total tunggal tidak cukup karena progres masing-masing sumber berbeda.

Langkah 4: Jadikan state dapat diserialisasi dan dapat berevolusi

Persistensikan hanya skalar, array, dan objek berformat JSON dengan versi skema. File handle, koneksi jaringan, lock, promise, call stack generator, dan closure adalah sumber daya runtime; buka kembali atau bangun ulang saat pemulihan alih-alih menuliskannya ke dalam snapshot.

Ketika versi baru membaca snapshot lama, jalankan migrasi eksplisit. Jika kompatibilitas tidak pasti, tolak pemulihan dan mulai ulang dari batas yang aman. Jika konten sumber dapat berubah, simpan ETag, panjang, checksum chunk, atau versi logis sehingga indeks yang sama tidak merujuk ke data yang berbeda secara diam-diam.

Langkah 5: Tambahkan pembacaan asinkron, pembatalan, dan percobaan ulang

next() asinkron mengembalikan promise dan dapat menunggu beberapa sumber secara konkuren, tetapi commit state tetap mengikuti prinsip "commit setelah pengiriman berhasil". Pembatalan menghentikan pembacaan baru, menutup berkas atau sumber daya jaringan, dan membiarkan kursor yang belum di-commit tidak berubah.

Klasifikasikan kegagalan sebagai I/O yang dapat dicoba ulang, error format permanen, atau perubahan versi sumber. Lakukan backoff dan pertahankan checkpoint untuk error yang dapat dicoba ulang; catat ID sumber dan offset sebelum mengakhiri sumber yang rusak permanen; wajibkan validasi ulang atau snapshot baru setelah perubahan sumber alih-alih beralih konten secara diam-diam.

Langkah 6: Rancang pengujian dan kompleksitas

Untuk satu sumber, verifikasi bahwa next(), penyimpanan, kelanjutan, dan pemulihan menghasilkan urutan yang persis sama. Uji list kosong, indeks batas, pemanggilan next setelah item terakhir, set_state berulang, dan versi tidak valid. Pengujian multi-sumber mencakup satu sumber yang berakhir lebih awal, urutan penyelesaian yang berbeda dari urutan penjadwalan, pembatalan, dan kegagalan satu sumber.

Operasi next dan pembacaan/penulisan snapshot sumber tunggal adalah O(1), dengan ukuran state O(1). Dengan m sumber, snapshot setidaknya berukuran O(m). Heap atau prefetched head dapat membuat next menjadi O(log m); round-robin dapat bernilai amortized O(1). Kompleksitas harus sesuai dengan penjadwal yang dipilih.

Contoh jawaban berkualitas tinggi

"Pertama-tama saya akan menyatakan kontrak pemulihan: snapshot menentukan elemen yang harus dikembalikan oleh pemanggilan next() berikutnya, dan kursor hanya maju setelah pengiriman berhasil. Iterator list menyimpan ID sumber, versi, dan indeks, lalu memvalidasi indeks; kegagalan membaca tidak melakukan commit pada kursor, sehingga percobaan ulang aman dilakukan.

Untuk beberapa sumber, setiap child menyimpan statenya sendiri, sedangkan composite menyimpan kursor round-robin, sumber yang telah selesai, dan urutan output. Jika urutan global diperlukan, ia juga menyimpan prefetched head setiap sumber. Snapshot berupa JSON berversi; file handle, promise, dan stack generator dibangun ulang setelah pemulihan.

Next asinkron dapat menunggu I/O secara konkuren, tetapi commit state tetap terjadi setelah pengiriman. Pembatalan menutup sumber daya dan mempertahankan state yang belum di-commit. Error diklasifikasikan sebagai dapat dicoba ulang, permanen, atau perubahan versi sumber. Pengujian membuktikan bahwa satu snapshot menghasilkan sufiks yang sama tanpa duplikasi atau data terlewat, dan bahwa perubahan urutan penyelesaian tetap memenuhi kontrak penjadwalan. Operasi sumber tunggal bernilai O(1), sedangkan snapshot m-sumber bernilai O(m), dengan kompleksitas next ditentukan oleh penjadwalan round-robin atau heap."

Kesalahan umum

• Menyimpan indeks yang dikembalikan sebagai indeks berikutnya → pemulihan mengulang atau melewatkan elemen → tentukan semantik checkpoint dan majukan kursor setelah pengiriman.
• Menserialisasi file handle atau objek generator → objek tidak bertahan setelah proses dimulai ulang → simpan skalar berversi dan bangun ulang sumber daya.
• Melakukan probing dengan hasNext() → sumber asinkron dapat berubah antara probing dan konsumsi → biarkan next() mengembalikan nilai atau hasil penyelesaian secara atomik.
• Hanya menyimpan hitungan total untuk beberapa sumber → progres per sumber dan posisi penjadwal hilang → simpan setiap state child dan state penjadwal.
• Memajukan kursor setelah kegagalan membaca → percobaan ulang kehilangan data → lakukan commit hanya setelah pengiriman berhasil.
• Memulihkan tanpa memeriksa versi sumber → offset yang sama dapat mengidentifikasi konten yang berbeda → validasi fingerprint, panjang, atau versi logis dan tolak state yang basi (stale).

Pertanyaan lanjutan dan jawabannya

Bagaimana jika snapshot ditulis setelah pembacaan berhasil tetapi sebelum pengiriman dikonfirmasi (acknowledged)?

Tentukan batas konfirmasi. Jika snapshot dapat tersimpan lebih dulu, sistem bersifat at-least-once dan setiap item memerlukan kunci idempoten atau penanda konfirmasi. Untuk perilaku exactly-once, tempatkan konfirmasi pengiriman dan commit kursor dalam satu transaksi yang dapat dipulihkan atau log commit eksternal.

Bagaimana cara menjaga keadilan di antara beberapa sumber asinkron yang siap?

Persistensikan kursor yang terakhir dipilih dalam penjadwal round-robin dan majukan setelah setiap pengiriman berhasil; sumber tercepat tidak boleh memonopoli output. Untuk urutan waktu global, gunakan min-heap dari head sumber dan sertakan heap head serta aturan perbandingan dalam snapshot.

Bisakah berkas yang ditambahkan datanya (appended) saat dijeda dilanjutkan dengan aman?

Hanya jika perilaku append-only merupakan bagian dari kontrak. Simpan versi, panjang yang telah dikonsumsi, dan checksum chunk, lalu lanjutkan dari panjang sebelumnya. Jika berkas dapat ditulis ulang atau diubah urutannya, tolak ketidakcocokan versi dan buat snapshot baru.

Bagaimana cara membatalkan next() saat sedang menunggu beberapa operasi I/O?

Kirimkan sinyal pembatalan, hentikan pembacaan yang belum dimulai, dan tutup sumber daya yang terbuka. Tidak boleh ada promise yang belum terselesaikan yang memajukan kursor. Pemanggilan next() berikutnya dapat mencoba lagi dari checkpoint awal atau mengembalikan state pembatalan eksplisit.