Temu Duga Pengekodan: Laksanakan Tatasusunan Syot Kilat (Snapshot Array)

Masalah dan Konteks yang Berkenaan

Laksanakan tatasusunan dengan panjang tetap yang bermula dengan sifar pada setiap indeks dan menyokong tiga operasi:

• set(index, value) mengubah satu elemen dalam versi semasa yang belum disyot kilat.
• snap() menyimpan versi semasa dan mengembalikan ID-nya. ID bermula pada 0 dan meningkat sebanyak satu.
• get(index, snapId) mengembalikan nilai pada index semasa syot kilat snapId diambil.

Andaikan 1 <= length <= 50,000, 0 <= value <= 10^9, indeks dan ID syot kilat adalah sah, dan paling banyak 50,000 panggilan dibuat merentasi semua operasi. Penyelesaian harus menerangkan kedua-dua tingkah laku API dan sebab keadaan yang disimpannya mencukupi untuk setiap pertanyaan sejarah.

Ini adalah soalan pengekodan dan struktur data. Prompt awam ini muncul dalam koleksi latihan temu duga semasa, dan isyarat berguna adalah sama ada calon boleh menggantikan syot kilat penuh dengan rekod perubahan tidak boleh ubah (immutable), kemudian mencari rekod sejarah yang betul menggunakan pertanyaan pendahulu (predecessor query).

Perkara yang Dinilai oleh Penemu Duga

Isyarat pertama ialah pemodelan kos. Menyalin semua nilai length pada setiap snap adalah mudah difahami, tetapi ia menelan kos masa dan ruang O(length) bagi setiap syot kilat walaupun hanya satu indeks yang berubah. Dengan 50,000 elemen dan 50,000 operasi, arah kes terburuk tersebut adalah terlalu besar tanpa keperluan.

Isyarat kedua ialah memilih indeks yang sepadan dengan pertanyaan. get sentiasa membekalkan indeks tatasusunan, jadi simpan sejarah perubahan yang diisih bagi setiap indeks. Entri sejarah [s, v] bermakna nilai v mula berkuat kuasa bermula pada ID syot kilat s. Jawapannya ialah entri dengan s <= snapId terbesar, yang merupakan carian pendahulu standard.

Isyarat ketiga ialah semantik syot kilat. Beberapa panggilan set ke indeks yang sama sebelum snap seterusnya tergolong dalam satu versi; hanya nilai terakhir yang perlu kekal. Menambah entri pendua dengan ID syot kilat yang sama membazirkan ruang dan boleh menjadikan invarian sejarah lebih sukar dinyatakan. Menggabungkannya (coalescing) memastikan ID sentiasa meningkat secara ketat.

Akhir sekali, jawapan yang kukuh menyatakan invarian, membuktikan carian binari, dan menguji sempadan masa: sifar awal, beberapa penulisan sebelum syot kilat, penulisan selepas syot kilat, indeks yang tidak disentuh, dan pertanyaan antara perubahan yang jarang (sparse).

Soalan Penjelasan Sebelum Menjawab

• Adakah snap() mengembalikan ID sebelum atau selepas memajukannya? Ia mengembalikan ID semasa, kemudian maju ke versi kerja seterusnya.
• Bolehkah set dipanggil beberapa kali sebelum snap? Ya. Penulisan terakhir pada sesuatu indeks dalam versi tersebut akan diguna pakai.
• Bolehkah get membaca keadaan semasa yang belum disyot kilat? Tidak. Ia menerima ID sah yang dikembalikan oleh snap() sebelumnya.
• Adakah panjang dan julat indeks ditetapkan? Ya. Tiada penambahan, pemadaman, atau saiz semula.
• Bolehkah ID syot kilat dilangkau? Sesuatu indeks mungkin tidak mengalami perubahan dalam banyak syot kilat berturut-turut, walaupun ID global kekal berturutan.
• Adakah kita memerlukan keselamatan benang (thread safety)? Tidak untuk kontrak temu duga dalam memori ini. Mutasi serentak akan memerlukan penyegerakan luaran di sekitar set dan snap.
• Apakah yang patut dikembalikan oleh indeks yang tidak disentuh? Sifar untuk setiap syot kilat.
• Adakah ketahanan merentasi mula semula proses (process restarts) diperlukan? Tidak. Itu akan menambah keperluan penyirikan (serialization) dan ketahanan di luar masalah struktur data ini.

Rangka Kerja Jawapan 30 Saat

"Saya akan mengekalkan sejarah yang diisih bagi setiap indeks tatasusunan dan bukannya menyalin keseluruhan tatasusunan. Mulakan setiap sejarah dengan [0, 0]. ID syot kilat semasa bermula pada sifar. Pada set, tulis ganti entri terakhir jika ia sudah tergolong dalam ID semasa; jika tidak, tambahkan [currentId, value]. Pada snap, kembalikan currentId dan tingkatkannya. Pada get, lakukan carian binari pada sejarah indeks tersebut untuk entri pertama yang ID-nya lebih besar daripada snapId, kemudian kembalikan nilai sebelumnya. Sejarah mempunyai ID yang meningkat secara ketat, dan sentinel menjamin kewujudan pendahulu. Pembinaan adalah O(length), set dan snap adalah O(1) terpelunasan, get adalah O(log h), dan ruang adalah O(length + u) untuk u perubahan yang dikekalkan."

Perbincangan Mendalam Langkah demi Langkah

Langkah 1: Tolak salinan penuh selepas mengukurnya secara kuantitatif.

Pelaksanaan langsung mengekalkan tatasusunan yang boleh diubah dan menyalin kesemuanya ke dalam senarai pada setiap snap. Ia memberikan O(1) bagi set dan get, tetapi snap menelan kos O(length) dan setiap syot kilat menyimpan nilai length. Ini membazirkan kos untuk indeks yang tidak berubah.

Satu log peristiwa global mengelakkan penyalinan, tetapi get(index, snapId) mungkin mengimbas ke belakang merentasi kemas kini untuk indeks yang tidak berkaitan. Pertanyaan telah menamakan indeks, jadi membahagikan sejarah mengikut indeks menyingkirkan peristiwa yang tidak relevan.

Langkah 2: Tentukan maksud satu entri sejarah.

Untuk satu indeks, andaikan sejarah yang dikekalkannya ialah:

[[0, 0], [2, 7], [5, 4]]

Nilainya ialah 0 untuk syot kilat 0 dan 1, 7 untuk syot kilat 2 hingga 4, dan 4 dari syot kilat 5 dan seterusnya. Setiap entri ialah titik perubahan, bukan salinan untuk satu syot kilat. Oleh itu, rekod yang diingini untuk syot kilat t ialah rekod paling kanan yang ID-nya paling banyak t.

Mulakan setiap indeks dengan [0, 0]. Sentinel ini menyatakan nilai awal dan menjamin bahawa setiap pertanyaan syot kilat yang sah mempunyai pendahulu, jadi get tidak memerlukan cabang sejarah kosong.

Langkah 3: Gabungkan penulisan di dalam versi semasa.

Sebelum snap pertama, ID semasa ialah 0. Jika set(3, 5) diikuti oleh set(3, 8), syot kilat 0 mesti mengandungi 8. Panggilan kedua menulis ganti [0, 5] dengan [0, 8]. Selepas snap() memajukan ID semasa, penulisan seterusnya menambah rekod baharu.

Ini mengekalkan invarian bahawa ID syot kilat dalam setiap sejarah meningkat secara ketat dan setiap sejarah mengandungi paling banyak satu rekod untuk mana-mana ID. Bilangan perubahan yang dikekalkan tidak melebihi bilangan panggilan set.

Langkah 4: Laksanakan carian pendahulu batas atas (upper-bound).

type Version = [snapId: number, value: number];

class SnapshotArray {
  private readonly histories: Version[][];
  private currentSnapId = 0;

  constructor(length: number) {
    this.histories = Array.from({ length }, () => [[0, 0]]);
  }

  set(index: number, value: number): void {
    const history = this.histories[index];
    const latest = history[history.length - 1];

    if (latest[0] === this.currentSnapId) {
      latest[1] = value;
    } else {
      history.push([this.currentSnapId, value]);
    }
  }

  snap(): number {
    return this.currentSnapId++;
  }

  get(index: number, snapId: number): number {
    const history = this.histories[index];
    let left = 0;
    let right = history.length;

    while (left < right) {
      const middle = left + Math.floor((right - left) / 2);
      if (history[middle][0] <= snapId) {
        left = middle + 1;
      } else {
        right = middle;
      }
    }

    return history[left - 1][1];
  }
}

Carian menggunakan selang separuh terbuka [left, right). Pada penamatan, left ialah kedudukan pertama dengan ID yang lebih besar daripada snapId. Pendahulunya ialah entri paling kanan dengan ID paling banyak snapId. Ini adalah pemetakan batas atas yang sama yang didokumentasikan oleh pustaka dwibahagian (bisection) standard.

Langkah 5: Buktikan ketepatan daripada invarian.

Bagi setiap indeks, rekod mempunyai ID yang meningkat secara ketat. Rekod [s, v] dicipta atau dimuktamadkan sebelum syot kilat s diambil dan kekal sebagai nilai berkuat kuasa sehingga rekod seterusnya untuk indeks tersebut. Oleh itu, dalam kalangan rekod yang ID-nya tidak melebihi syot kilat yang diminta, rekod dengan ID terbesar adalah tepat penulisan terakhir yang boleh dilihat oleh syot kilat tersebut.

Carian binari mengembalikan rekaman pertama selepas awalan yang layak itu, jadi left - 1 memilih ID terbesarnya. Sentinel [0, 0] menjadikan awalan yang layak tidak kosong untuk setiap ID syot kilat yang sah. Oleh itu, get mengembalikan nilai yang diperlukan.

Langkah 6: Analisis kerumitan dan sahkan sempadan.

Mencipta sejarah menelan kos masa dan ruang O(length). set membaca atau menambah pada hujung satu sejarah dalam masa terpelunasan O(1). snap ialah O(1). Jika sesuatu indeks mempunyai h rekod yang dikekalkan, get menelan kos O(log h). Merentasi objek, ruang ialah O(length + u), dengan u ialah bilangan rekod perubahan bukan sentinel yang dikekalkan dan u paling banyak bilangan panggilan set.

Sekurang-kurangnya, uji:

Ujian perbezaan rawak boleh membandingkan struktur ini dengan garis dasar salinan penuh. Garis dasar tersebut terlalu mahal untuk kekangan pengeluaran tetapi merupakan orakel ujian yang mudah dan boleh dipercayai.

Contoh Jawapan Berkualiti Tinggi

"Pertanyaan utama ialah carian sejarah untuk satu indeks yang diketahui, jadi saya akan mengekalkan sejarah perubahan yang teratur bagi setiap indeks. Setiap sejarah bermula dengan [0, 0]; pasangan [s, v] bermakna v berkuat kuasa dari syot kilat s sehingga pasangan seterusnya.

ID semasa bermula pada sifar. set hanya melihat pada pasangan terakhir. Jika pasangan itu sudah menggunakan ID semasa, ia menggantikan nilainya kerana penulisan terakhir sebelum syot kilat menang. Jika tidak, ia menambah pasangan baharu. snap mengembalikan ID semasa dan meningkatkannya.

Untuk get(index, snapId), saya menjalankan carian batas atas pada sejarah indeks tersebut: cari pasangan pertama dengan ID lebih besar daripada ID yang diminta dan kembalikan nilai pasangan sebelumnya. ID bagi setiap indeks meningkat secara ketat, dan sentinel awal menjamin bahawa pendahulu wujud. Pendahulu ini tepat merupakan nilai terakhir yang ditulis tidak lewat daripada syot kilat yang diminta.

Pembinaan menelan kos O(length). set dan snap adalah O(1) terpelunasan, get ialah O(log h) untuk rekod perubahan h indeks tersebut, dan jumlah ruang ialah O(length + u). Saya akan menguji sifar awal, penetapan berulang sebelum satu syot kilat, perubahan jarang merentasi beberapa syot kilat, bacaan lampau selepas penulisan kemudian, indeks yang tidak disentuh, dan surihan rawak terhadap orakel salinan penuh."

Kesilapan Biasa

• Menyalin keseluruhan tatasusunan pada setiap syot kilat → masa dan ruang berskala dengan semua indeks, termasuk yang tidak berubah → simpan hanya titik perubahan bagi setiap indeks.
• Mengekalkan satu log kemas kini global → bacaan mungkin mengimbas indeks yang tidak berkaitan → bahagikan sejarah mengikut indeks yang dibekalkan dalam setiap pertanyaan.
• Menambah setiap set → penulisan berulang dalam satu versi mencipta ID pendua dan rekod yang dibazirkan → tulis ganti hujung apabila ia mempunyai ID semasa.
• Mencari ID syot kilat yang tepat → sesuatu indeks mungkin tidak berubah dalam syot kilat tersebut → cari ID tercatat terbesar yang kurang daripada atau sama dengan permintaan.
• Menggunakan batas bawah (lower bound) dan mengembalikannya secara terus → ia mungkin menghala ke perubahan yang lebih lewat → dapatkan batas atas permintaan dan kembalikan pendahulu.
• Memulakan sejarah kosong → indeks yang tidak disentuh memerlukan kes khas → benihkan setiap sejarah dengan [0, 0].
• Meningkatkan sebelum kembali daripada snap → ID pertama yang dikembalikan menjadi 1 dan rekod beralih versi → kembalikan ID semasa, kemudian tingkatkan.
• Mendakwa get ialah O(log length) → ia mencari rekod perubahan untuk satu indeks → nyatakan O(log h) dan takrifkan h.
• Menguji hanya contoh yang diterbitkan → penulisan ganti versi yang sama dan sejarah yang jarang kekal tidak disahkan → tambah kes sempadan dan orakel perbezaan.

Soalan Susulan dan Maklum Balas

Susulan 1: Bolehkah snap() menjadi O(1) jika syot kilat mesti tidak boleh ubah?

Ya. Sifat tidak boleh ubah adalah secara logik: selepas ID dikembalikan, penulisan masa hadapan ditambah di bawah ID yang lebih besar dan tidak pernah memutasikan rekod milik ID yang lebih lama. snap() hanya memajukan sempadan versi; ia tidak perlu menjelmakan salinan penuh.

Susulan 2: Mengapa menggunakan sejarah bagi setiap indeks berbanding peta (map) bagi setiap syot kilat?

Peta bagi setiap syot kilat menyebabkan carian titik perlu mencari ke belakang merentasi syot kilat sehingga ia menemui indeks tersebut. Sejarah bagi setiap indeks menyusun rekod mengikut kunci pertanyaan pertama, jadi get hanya mencari perubahan yang relevan. Peta berorientasikan syot kilat boleh berguna apabila pertanyaan utama ialah "senaraikan semua yang berubah dalam syot kilat s", yang merupakan kontrak berbeza.

Susulan 3: Bolehkah get menggunakan carian binari pustaka standard?

Ya, apabila bahasa tersebut mendedahkan kontrak batas atas yang tepat untuk sesuatu kunci. Contohnya, kedudukan dwibahagian kanan (right-bisection) ialah titik sisipan selepas ID sedia ada sama dengan snapId; menolak satu menghasilkan pendahulu. Sahkan pengekstrakan kunci dan tingkah laku keserentakan dalam dokumentasi pustaka daripada menganggap semua pembantu carian binari mengembalikan batas yang sama.

Susulan 4: Apakah yang berubah jika syot kilat boleh dipadamkan?

Mula-mula tentukan sama ada memadamkan satu ID juga menjadikan syot kilat kemudian tidak boleh diakses atau sama ada ID kekal stabil. ID yang stabil biasanya memerlukan pengiraan rujukan (reference counting) atau pemadatan (compaction) yang mengekalkan setiap nilai yang masih boleh dicapai oleh syot kilat yang dikekalkan. Memadamkan satu rekod secara membuta tuli boleh mengubah nilai yang diwarisi oleh syot kilat kemudian.

Susulan 5: Bagaimanakah anda akan mengekalkan ketahanan struktur ini?

Simpan rekod perubahan tambah sahaja (append-only) yang berkunci (array_id, index, snap_id) dan terbitkan sempadan syot kilat tahan lama hanya selepas semua penulisan sebelumnya dikomitkan. Pembacaan memerlukan indeks pendahulu pada (array_id, index, snap_id). Pemulihan, transaksi, dan pemadatan kemudiannya menjadi kebimbangan sistem storan di luar pelaksanaan temu duga dalam memori ini.

Susulan 6: Bagaimana jika bacaan jauh melebihi penulisan untuk tatasusunan tetap yang kecil?

Salinan penuh mungkin menjadi munasabah jika tatasusunan adalah kecil dan bacaan O(1) lebih penting daripada kos syot kilat. Bandingkan panjang sebenar, bilangan syot kilat, kadar bacaan, dan belanjawan memori. Reka bentuk sejarah perubahan mengoptimumkan penulisan yang jarang dan penciptaan syot kilat; ia tidak secara automatik terbaik untuk setiap beban kerja.