Temu duga pengekodan: Bagaimanakah anda melaksanakan lelaran (iterator) yang boleh disambung semula dan boleh disirikan?

Soalan dan konteks

Laksanakan lelaran dengan get_state() dan set_state(): mulakan dengan satu senarai, kemudian lanjutkan kepada lelaran serentak merentasi pelbagai sumber dan bacaan tak segerak. Bagaimanakah anda mentakrifkan keadaan, menjamin tiada duplikasi atau langkauan selepas pemulihan, dan mengendalikan penyiapan, kegagalan, serta snapshot yang tidak sah?

Ini sepadan dengan rekod temu duga pengekodan OpenAI awam yang perkembangannya merangkumi lelaran senarai, lelaran komposit pelbagai fail, dan versi berasaskan coroutine. Ia sesuai untuk peranan pengekodan am, infrastruktur, pemprosesan data, dan kejuruteraan pembelajaran mesin. Cabarannya bukanlah menjeda penjana (generator); ia adalah mengekod "apa yang mesti dikembalikan oleh panggilan seterusnya" sebagai keadaan yang boleh disahkan dan disirikan.

Perkara yang dinilai oleh penemu duga

• Adakah anda mentakrifkan semantik input, output, penyiapan, dan ralat next() dan bukannya bergantung pada hasNext()?
• Adakah anda memisahkan objek masa larian (runtime) daripada keadaan yang boleh dikekalkan (persistable state)?
• Bolehkah anda membuktikan bahawa pemulihan tidak mengulangi atau melangkau elemen yang telah dihantar?
• Adakah anda menjejaki kemajuan setiap sumber dan susunan penjadualan global?
• Adakah anda mengendalikan bacaan tak segerak, pembatalan, percubaan semula (retry), dan pembersihan sumber?
• Adakah anda menguji sumber kosong, snapshot tidak sah, perubahan sumber, dan pemulihan idempoten?

Soalan penjelasan sebelum mengekod

• Adakah sumber merupakan senarai tidak boleh ubah (immutable list), fail tambah sahaja (append-only file), atau strim luaran yang boleh diubah? Jika ia boleh berubah, snapshot memerlukan versi atau cap jari kandungan (content fingerprint).
• Adakah pemulihan mengulangi nilai terakhir yang dikembalikan atau bermula pada nilai seterusnya yang belum dikembalikan? Jawapan ini menggunakan yang kedua dan memajukan kursor hanya selepas penghantaran berjaya.
• Adakah susunan pelbagai sumber secara round-robin, susunan masa global, atau mana-mana sumber yang sedia dahulu? Pilihan ini mengubah medan keadaan dan bukti keadilan (fairness proof).
• Adakah get_state() mesti bertahan daripada perubahan proses atau versi skema? Jika ya, simpan skalar berversi dan ID sumber sahaja, jangan sekali-kali pemegang fail (file handles), promises, atau objek penjana.

Jawapan 30 saat

"Saya terlebih dahulu mentakrifkan titik semakan sebagai elemen yang akan dikembalikan oleh panggilan next() seterusnya. Senarai tunggal menyimpan indeks dan versi sumber; pelbagai sumber menyimpan setiap kursor serta keadaan penjadual. next() memajukan kursor hanya selepas penghantaran berjaya, jadi memulihkan keadaan yang sama mengembalikan elemen yang sama dan tidak mengulangi elemen yang telah disahkan. Snapshot ialah JSON berversi, disahkan terhadap cap jari sumber dan batasan sebelum pemulihan. Versi tak segerak memisahkan I/O dalam proses daripada keadaan yang boleh dipulihkan, menyokong pembatalan, pembersihan, dan percubaan semula bagi setiap sumber, serta tidak sekali-kali mensirikan pemegang masa larian."

Jawapan mendalam langkah demi langkah

Langkah 1: Takrifkan antara muka minimum dan titik semakan

Gunakan next(), get_state(), dan set_state(state) tanpa menambah hasNext(). Lelaran terhingga mengembalikan satu hasil selesai yang konsisten atau membangkitkan pengecualian penyiapan yang dipersetujui; pemanggil tidak seharusnya mengintip ke hadapan dan meneka keadaan.

Letakkan titik semakan pada "item seterusnya", bukan "item terakhir". Sumber senarai boleh menyimpan {sourceId, version, index, done}. next() membaca items[index] dan menambah indeks hanya selepas nilai berjaya dihantar; kegagalan membaca membiarkan keadaan tidak berubah untuk percubaan semula.

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 varian (invariant) dan buktikan pemulihan

Varian utama ialah index bersamaan dengan bilangan elemen yang berjaya dihantar; indeks snapshot bersamaan dengan kursor dalam ingatan; dan versi sumber tidak berubah. next() mara hanya selepas mengembalikan nilai, manakala set_state() menerima hanya versi yang sepadan dan batasan yang sah, jadi titik semakan yang sama menghasilkan akhiran (suffix) yang sama.

Jika kontrak perniagaan adalah sekurang-kurangnya sekali (at-least-once) dan bukannya tepat sekali (exactly-once), mengulangi item terakhir antara penghantaran dan titik semakan boleh diterima, tetapi keadaan mesti mengandungi penanda pengesahan (acknowledgement marker) atau kunci keidempotensian (idempotency key). Jangan campurkan kedua-dua semantik dalam satu kontrak set_state().

Langkah 3: Lanjutkan kepada pelbagai sumber

Lelaran komposit menyimpan keadaan children[sourceId] yang bebas dan keadaan penjadual seperti baris gilir round-robin, set sumber yang selesai, dan nombor jujukan. Round-robin memilih sumber belum selesai yang seterusnya; penyusunan global memerlukan penyimpanan kepala yang dipraambil (prefetched head) bagi setiap sumber supaya perbandingan boleh dihasilkan semula selepas pemulihan.

Snapshot pelbagai sumber boleh menjadi {schema, children: [{id, state}], scheduler: {kind, cursor}, emitted}. Sahkan keahlian dan susunan sumber terlebih dahulu, pulihkan anak seterusnya, dan pulihkan penjadual yang terakhir. Jumlah kiraan tunggal tidak mencukupi kerana kemajuan sumber adalah berbeza-beza.

Langkah 4: Jadikan keadaan boleh disirikan dan boleh berkembang

Kekalkan hanya skalar, tatasusunan, dan objek berbentuk JSON dengan versi skema. Pemegang fail, sambungan rangkaian, kunci (locks), promises, timbunan penjana, dan penutupan (closures) ialah sumber masa larian; buka semula atau bina semula semasa pemulihan dan bukannya menulisnya ke dalam snapshot.

Apabila versi baharu membaca snapshot lama, jalankan migrasi yang jelas. Jika keserasian tidak pasti, tolak pemulihan dan mulakan semula dari sempadan yang selamat. Jika kandungan sumber boleh berubah, simpan ETag, panjang, checksum bahagian (chunk), atau versi logik supaya indeks yang sama tidak boleh merujuk kepada data yang berbeza secara senyap.

Langkah 5: Tambah bacaan tak segerak, pembatalan, dan percubaan semula

next() tak segerak mengembalikan promise dan boleh menunggu beberapa sumber secara serentak, tetapi komitmen keadaan masih mengikut "komit selepas penghantaran berjaya". Pembatalan menghentikan bacaan baharu, menutup fail atau sumber rangkaian, dan membiarkan kursor yang belum dikomit tidak berubah.

Kelaskan kegagalan sebagai I/O yang boleh dicuba semula, ralat format kekal, atau perubahan versi sumber. Undur (back off) dan kekalkan titik semakan untuk ralat yang boleh dicuba semula; rekod ID sumber dan ofset sebelum menamatkan sumber yang rosak secara kekal; wajibkan pengesahan semula atau snapshot baharu selepas perubahan sumber dan bukannya menukar kandungan secara senyap.

Langkah 6: Reka bentuk ujian dan kerumitan

Bagi satu sumber, sahkan bahawa next(), simpan, teruskan, dan pulihkan menghasilkan jujukan yang sama persis. Uji senarai kosong, indeks sempadan, memanggil next selepas item terakhir, set_state berulang, dan versi yang tidak sah. Ujian pelbagai sumber merangkumi satu sumber tamat awal, susunan penyiapan berbeza daripada susunan penjadualan, pembatalan, dan kegagalan satu sumber.

Operasi next dan baca/tulis snapshot sumber tunggal adalah O(1), dengan saiz keadaan O(1). Dengan m sumber, snapshot sekurang-kurangnya O(m). Heap atau kepala yang dipraambil boleh menjadikan next O(log m); round-robin boleh menjadi O(1) terlunas (amortized). Kerumitan mesti sepadan dengan penjadual yang dipilih.

Contoh jawapan berkualiti tinggi

"Saya akan terlebih dahulu menyatakan kontrak pemulihan: snapshot menamakan elemen yang mesti dikembalikan oleh panggilan next() seterusnya, dan kursor mara hanya selepas penghantaran berjaya. Lelaran senarai menyimpan ID sumber, versi, dan indeks, kemudian mengesahkan indeks; kegagalan membaca tidak mengomit kursor, jadi percubaan semula adalah selamat.

Untuk pelbagai sumber, setiap anak mengekalkan keadaannya sendiri, manakala komposit menyimpan kursor round-robin, sumber yang telah selesai, dan jujukan output. Jika susunan global diperlukan, ia juga menyimpan kepala yang dipraambil bagi setiap sumber. Snapshot ialah JSON berversi; pemegang fail, promises, dan timbunan penjana dibina semula selepas pemulihan.

Next tak segerak mungkin menunggu I/O secara serentak, tetapi komitmen keadaan tetap berlaku selepas penghantaran. Pembatalan menutup sumber dan mengekalkan keadaan yang belum dikomit. Ralat dikelaskan sebagai boleh dicuba semula, kekal, atau perubahan versi sumber. Ujian membuktikan bahawa satu snapshot menghasilkan akhiran yang sama tanpa duplikasi atau langkauan, dan bahawa perubahan susunan penyiapan masih memenuhi kontrak penjadualan. Operasi sumber tunggal adalah O(1), manakala snapshot m-sumber adalah O(m), dengan kerumitan next ditentukan oleh penjadualan round-robin atau heap."

Kesilapan lazim

• Menyimpan indeks yang dikembalikan sebagai indeks seterusnya → pemulihan mengulangi atau melangkau elemen → takrifkan semantik titik semakan dan mara selepas penghantaran.
• Mensirikan pemegang fail atau objek penjana → objek tidak bertahan selepas proses dimulakan semula → simpan skalar berversi dan bina semula sumber.
• Mengintip dengan hasNext() → sumber tak segerak boleh berubah antara mengintip dan menggunakan → biarkan next() mengembalikan nilai atau hasil penyiapan secara atomik.
• Menyimpan hanya jumlah kiraan untuk pelbagai sumber → kemajuan setiap sumber dan kedudukan penjadual hilang → simpan setiap keadaan anak dan keadaan penjadual.
• Memajukan kursor selepas kegagalan membaca → percubaan semula kehilangan data → komit hanya selepas penghantaran berjaya.
• Memulihkan tanpa menyemak versi sumber → ofset yang sama mungkin mengenal pasti kandungan yang berbeza → sahkan cap jari, panjang, atau versi logik dan tolak keadaan basi.

Soalan susulan dan respons

Bagaimana jika snapshot ditulis selepas bacaan berjaya tetapi sebelum penghantaran disahkan?

Takrifkan sempadan pengesahan. Jika snapshot boleh mendarat terlebih dahulu, sistem adalah sekurang-kurangnya sekali (at-least-once) dan setiap item memerlukan kunci keidempotensian atau penanda pengesahan. Untuk kelakuan tepat sekali (exactly-once), letakkan pengesahan penghantaran dan komit kursor dalam satu transaksi yang boleh dipulihkan atau log komit luaran.

Bagaimanakah anda mengekalkan keadilan bagi beberapa sumber tak segerak yang sedia?

Kekalkan kursor yang terakhir dipilih dalam penjadual round-robin dan majukannya selepas setiap penghantaran yang berjaya; sumber terpantas tidak boleh memonopoli output. Untuk susunan masa global, gunakan min-heap kepala sumber dan sertakan kepala heap serta peraturan perbandingan dalam snapshot.

Bolehkah fail yang ditambah semasa dijeda disambung semula dengan selamat?

Hanya jika kelakuan tambah sahaja (append-only) adalah sebahagian daripada kontrak. Simpan versi, panjang yang telah digunakan, dan checksum bahagian, kemudian sambung semula dari panjang lama. Jika fail boleh ditulis semula atau disusun semula, tolak ketidakpadanan versi dan cipta snapshot baharu.

Bagaimanakah anda membatalkan next() semasa ia menunggu beberapa operasi I/O?

Hantar isyarat pembatalan, hentikan bacaan yang belum bermula, dan tutup sumber yang telah dibuka. Tiada promise yang belum selesai boleh memajukan kursor. Panggilan next() kemudiannya sama ada mencuba semula dari titik semakan asal atau mengembalikan keadaan pembatalan yang jelas.