Wawancara Coding: Mengimplementasikan Snapshot Array

Masalah dan Konteks yang Berlaku

Implementasikan array dengan panjang tetap yang dimulai dengan nilai nol di setiap indeks dan mendukung tiga operasi:

• set(index, value) mengubah satu elemen pada versi saat ini yang belum di-snapshot.
• snap() menyimpan versi saat ini dan mengembalikan ID-nya. ID dimulai dari 0 dan bertambah satu demi satu.
• get(index, snapId) mengembalikan nilai pada index saat snapshot snapId diambil.

Asumsikan 1 <= length <= 50,000, 0 <= value <= 10^9, indeks, dan ID snapshot valid, serta paling banyak 50.000 panggilan dilakukan di seluruh operasi. Solusi harus menjelaskan perilaku API dan mengapa state yang disimpan mencukupi untuk setiap kueri historis.

Ini adalah pertanyaan coding dan struktur data. Soal publik ini muncul dalam kumpulan latihan wawancara saat ini, dan sinyal yang berguna adalah apakah seorang kandidat dapat mengganti snapshot penuh dengan rekaman perubahan yang tidak dapat diubah (immutable), lalu menemukan rekaman historis yang benar menggunakan kueri pendahulu (predecessor query).

Hal yang Dievaluasi Pewawancara

Sinyal pertama adalah pemodelan biaya (cost modeling). Menyalin semua length nilai pada setiap snap mudah dipahami, tetapi ini memakan waktu dan ruang O(length) per snapshot bahkan ketika hanya satu indeks yang berubah. Dengan 50.000 elemen dan 50.000 operasi, arah kasus terburuk (worst-case) tersebut menjadi terlalu besar tanpa perlu.

Sinyal kedua adalah memilih indeks yang cocok dengan kueri. get selalu menyediakan indeks array, jadi simpanlah riwayat perubahan yang terurut per indeks. Entri riwayat [s, v] berarti nilai v mulai berlaku sejak ID snapshot s. Jawabannya adalah entri dengan s <= snapId terbesar, yang merupakan pencarian pendahulu (predecessor search) standar.

Sinyal ketiga adalah semantik snapshot. Beberapa panggilan set ke indeks yang sama sebelum snap berikutnya termasuk dalam satu versi; hanya nilai terakhir yang harus dipertahankan. Menambahkan entri duplikat dengan ID snapshot yang sama akan membuang-buang ruang dan dapat membuat invarian riwayat lebih sulit dinyatakan. Menggabungkannya (coalescing) menjaga ID tetap meningkat secara ketat (strictly increasing).

Terakhir, jawaban yang kuat menyatakan invarian, membuktikan pencarian biner, dan menguji batas waktu: nol awal, beberapa penulisan sebelum snapshot, penulisan setelah snapshot, indeks yang tidak tersentuh, dan kueri di antara perubahan yang jarang (sparse).

Pertanyaan Klarifikasi Sebelum Menjawab

• Apakah snap() mengembalikan ID sebelum atau sesudah memajukannya? Metode ini mengembalikan ID saat ini, lalu maju ke versi kerja berikutnya.
• Bisakah set dipanggil beberapa kali sebelum snap? Ya. Penulisan terakhir ke sebuah indeks pada versi tersebut yang berlaku.
• Bisakah get membaca state saat ini yang belum di-snapshot? Tidak. Metode ini menerima ID valid yang dikembalikan oleh snap() sebelumnya.
• Apakah panjang dan rentang indeks bersifat tetap? Ya. Tidak ada penyisipan, penghapusan, atau pengubahan ukuran (resizing).
• Bisakah ID snapshot terlewati? Sebuah indeks mungkin tidak mengalami perubahan dalam banyak snapshot berturut-turut, meskipun ID global tetap berurutan.
• Apakah kita memerlukan thread safety? Tidak untuk kontrak wawancara in-memory ini. Mutasi konkuren akan memerlukan sinkronisasi eksternal di sekitar set dan snap.
• Apa yang harus dikembalikan oleh indeks yang tidak pernah disentuh? Nol untuk setiap snapshot.
• Apakah persistensi lintas restart proses diperlukan? Tidak. Hal itu akan menambahkan persyaratan serialisasi dan durabilitas di luar masalah struktur data ini.

Kerangka Jawaban 30 Detik

“Saya akan menyimpan riwayat yang terurut untuk setiap indeks array alih-alih menyalin seluruh array. Inisialisasi setiap riwayat dengan [0, 0]. ID snapshot saat ini dimulai dari nol. Pada set, timpa entri terakhir jika sudah milik ID saat ini; jika tidak, tambahkan [currentId, value]. Pada snap, kembalikan currentId dan inkremen nilainya. Pada get, lakukan pencarian biner pada riwayat indeks tersebut untuk menemukan entri pertama yang ID-nya lebih besar dari snapId, lalu kembalikan nilai sebelumnya (preceding value). Riwayat memiliki ID yang meningkat secara ketat, dan sentinel menjamin adanya pendahulu. Konstruksi membutuhkan O(length), set dan snap bernilai amortisasi O(1), get adalah O(log h), dan ruang yang digunakan adalah O(length + u) untuk u perubahan yang disimpan.”

Pembahasan Mendalam Langkah demi Langkah

Langkah 1: Menolak salinan penuh setelah menguantifikasinya.

Implementasi langsung mempertahankan array yang dapat diubah (mutable) dan menyalin seluruh isinya ke dalam list pada setiap snap. Pendekatan ini memberikan O(1) untuk set dan get, tetapi snap memakan biaya O(length) dan setiap snapshot menyimpan length nilai. Ini membebani biaya untuk indeks yang tidak berubah.

Log event global tunggal menghindari penyalinan, tetapi get(index, snapId) mungkin harus memindai mundur melintasi pembaruan untuk indeks yang tidak terkait. Kueri sudah menyebutkan indeks tertentu, sehingga mempartisi riwayat berdasarkan indeks akan menghilangkan event yang tidak relevan.

Langkah 2: Mendefinisikan arti satu entri riwayat.

Untuk satu indeks, misalkan riwayat yang tersimpan adalah:

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

Nilainya adalah 0 untuk snapshot 0 dan 1, 7 untuk snapshot 2 hingga 4, dan 4 dari snapshot 5 dan seterusnya. Setiap entri adalah titik perubahan, bukan salinan untuk satu snapshot. Oleh karena itu, rekaman yang diinginkan untuk snapshot t adalah rekaman paling kanan yang ID-nya paling banyak t.

Inisialisasi setiap indeks dengan [0, 0]. Sentinel ini menyatakan nilai awal dan menjamin bahwa setiap kueri snapshot yang valid memiliki pendahulu, sehingga get tidak memerlukan percabangan untuk riwayat kosong.

Langkah 3: Menggabungkan penulisan di dalam versi saat ini.

Sebelum snap pertama, ID saat ini adalah 0. Jika set(3, 5) diikuti oleh set(3, 8), snapshot 0 harus berisi 8. Panggilan kedua menimpa [0, 5] dengan [0, 8]. Setelah snap() memajukan ID saat ini, penulisan berikutnya akan menambahkan rekaman baru.

Hal ini mempertahankan invarian bahwa ID snapshot di setiap riwayat meningkat secara ketat dan setiap riwayat berisi paling banyak satu rekaman untuk ID apa pun. Jumlah perubahan yang disimpan tidak lebih besar dari jumlah panggilan set.

Langkah 4: Mengimplementasikan pencarian pendahulu 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];
  }
}

Pencarian menggunakan interval setengah terbuka [left, right). Saat terminasi, left adalah posisi pertama dengan ID yang lebih besar dari snapId. Pendahulunya adalah entri paling kanan dengan ID paling banyak snapId. Ini adalah partisi upper-bound yang sama seperti yang didokumentasikan oleh pustaka biseksi standar.

Langkah 5: Membuktikan kebenaran dari invarian.

Untuk setiap indeks, rekaman memiliki ID yang meningkat secara ketat. Rekaman [s, v] dibuat atau diselesaikan sebelum snapshot s diambil dan tetap menjadi nilai efektif sampai rekaman berikutnya untuk indeks tersebut. Oleh karena itu, di antara rekaman yang ID-nya tidak melebihi snapshot yang diminta, rekaman dengan ID terbesar tepat merupakan penulisan terakhir yang terlihat oleh snapshot tersebut.

Pencarian biner mengembalikan rekaman pertama setelah prefiks yang memenuhi syarat tersebut, sehingga left - 1 memilih ID terbesarnya. Sentinel [0, 0] membuat prefiks yang memenuhi syarat menjadi tidak kosong untuk setiap ID snapshot yang valid. Dengan demikian, get mengembalikan nilai yang diperlukan.

Langkah 6: Menganalisis kompleksitas dan memverifikasi batasan.

Membuat riwayat memakan waktu dan ruang O(length). set membaca atau menambahkan ke ujung satu riwayat dalam waktu teramortisasi O(1). snap adalah O(1). Jika sebuah indeks memiliki h rekaman yang disimpan, get membutuhkan biaya O(log h). Di seluruh objek, ruang yang digunakan adalah O(length + u), di mana u adalah jumlah rekaman perubahan non-sentinel yang disimpan dan u paling banyak sejumlah panggilan set.

Minimal, uji:

Uji diferensial acak dapat membandingkan struktur ini terhadap baseline penyalinan penuh. Baseline terlalu mahal untuk batasan produksi tetapi merupakan oracle pengujian yang sederhana dan dapat dipercaya.

Contoh Jawaban Berkualitas Tinggi

“Kueri utamanya adalah pencarian historis untuk satu indeks yang diketahui, jadi saya akan menyimpan riwayat perubahan yang terurut per indeks. Setiap riwayat dimulai dengan [0, 0]; pasangan [s, v] berarti v berlaku mulai snapshot s hingga pasangan berikutnya.

ID saat ini dimulai dari nol. set hanya memeriksa pasangan terakhir. Jika pasangan tersebut sudah menggunakan ID saat ini, metode ini mengganti nilainya karena penulisan terakhir sebelum snapshot yang berlaku. Jika tidak, metode ini menambahkan pasangan baru. snap mengembalikan ID saat ini dan menginkremennya.

Untuk get(index, snapId), saya menjalankan pencarian upper-bound pada riwayat indeks tersebut: temukan pasangan pertama dengan ID lebih besar dari ID yang diminta dan kembalikan nilai pasangan sebelumnya. ID per indeks meningkat secara ketat, dan sentinel awal menjamin bahwa pendahulunya selalu ada. Pendahulu ini tepat merupakan nilai terakhir yang ditulis tidak lebih lambat dari snapshot yang diminta.

Konstruksi membutuhkan biaya O(length). set dan snap teramortisasi sebesar O(1), get adalah O(log h) untuk h rekaman perubahan indeks tersebut, dan total ruang adalah O(length + u). Saya akan menguji nilai nol awal, set berulang sebelum satu snapshot, perubahan yang jarang di beberapa snapshot, pembacaan masa lalu setelah penulisan kemudian, indeks yang tidak tersentuh, dan trace acak terhadap oracle penyalinan penuh.”

Kesalahan Umum

• Menyalin seluruh array pada setiap snapshot → waktu dan ruang berskala dengan semua indeks, termasuk yang tidak berubah → hanya simpan titik perubahan per indeks.
• Menyimpan satu log pembaruan global → pembacaan dapat memindai indeks yang tidak relevan → partisi riwayat berdasarkan indeks yang diberikan dalam setiap kueri.
• Menambahkan setiap set → penulisan berulang dalam satu versi membuat ID duplikat dan rekaman terbuang → timpa entri terakhir saat entri tersebut memiliki ID saat ini.
• Mencari ID snapshot yang tepat → sebuah indeks mungkin tidak berubah dalam snapshot tersebut → temukan ID tercatat terbesar yang kurang dari atau sama dengan permintaan.
• Menggunakan lower bound dan mengembalikannya secara langsung → ini mungkin menunjuk ke perubahan setelahnya → cari upper-bound permintaan dan kembalikan pendahulunya.
• Memulai riwayat dalam keadaan kosong → indeks yang belum tersentuh memerlukan penanganan kasus khusus → isi setiap riwayat awal dengan [0, 0].
• Menginkremen sebelum mengembalikan dari snap → ID pertama yang dikembalikan menjadi 1 dan rekaman bergeser versi → kembalikan ID saat ini, lalu inkremen.
• Mengklaim get adalah O(log length) → metode ini mencari rekaman perubahan untuk satu indeks → nyatakan O(log h) dan definisikan h.
• Hanya menguji contoh yang dipublikasikan → penimpaan pada versi yang sama dan riwayat yang jarang tetap tidak terverifikasi → tambahkan kasus batas dan oracle diferensial.

Pertanyaan Lanjutan dan Tanggapan

Lanjutan 1: Bisakah snap() bernilai O(1) jika snapshot harus bersifat immutable?

Ya. Imutabilitas bersifat logis: setelah ID dikembalikan, penulisan di masa mendatang akan ditambahkan di bawah ID yang lebih besar dan tidak pernah memutasi rekaman milik ID yang lebih lama. snap() hanya memajukan batas versi; metode ini tidak perlu mematerialisasi salinan penuh.

Lanjutan 2: Mengapa menggunakan riwayat per indeks alih-alih map per snapshot?

Map per snapshot membuat pencarian titik harus memindai mundur melintasi snapshot sampai menemukan indeks tersebut. Riwayat per indeks menyusun rekaman berdasarkan kunci kueri pertama, sehingga get hanya mencari perubahan yang relevan. Map yang berorientasi snapshot bisa berguna ketika kueri utamanya adalah “enumerasikan semua yang berubah dalam snapshot s,” yang merupakan kontrak berbeda.

Lanjutan 3: Bisakah get menggunakan pencarian biner dari pustaka standar?

Ya, jika bahasa tersebut menyediakan kontrak upper-bound yang tepat untuk sebuah kunci. Misalnya, posisi right-bisection adalah titik penyisipan setelah ID yang ada yang bernilai sama dengan snapId; mengurangi satu menghasilkan pendahulunya. Konfirmasikan ekstraksi kunci dan perilaku konkurensi dalam dokumentasi pustaka daripada mengasumsikan semua fungsi pembantu pencarian biner mengembalikan batasan yang sama.

Lanjutan 4: Apa yang berubah jika snapshot dapat dihapus?

Pertama tentukan apakah menghapus satu ID juga membuat snapshot berikutnya tidak dapat diakses atau apakah ID tetap stabil. ID yang stabil biasanya memerlukan reference counting atau pemadatan (compaction) yang mempertahankan setiap nilai yang masih dapat dijangkau oleh snapshot yang dipertahankan. Menghapus satu rekaman secara membabi buta dapat mengubah nilai yang diwarisi oleh snapshot berikutnya.

Lanjutan 5: Bagaimana Anda membuat struktur ini persisten?

Simpan rekaman perubahan yang bersifat append-only dengan kunci (array_id, index, snap_id) dan publikasikan batas snapshot yang tahan lama (durable) hanya setelah semua penulisan sebelumnya selesai di-commit. Pembacaan memerlukan indeks pendahulu pada (array_id, index, snap_id). Pemulihan, transaksi, dan pemadatan kemudian menjadi perhatian sistem penyimpanan di luar implementasi wawancara in-memory ini.

Lanjutan 6: Bagaimana jika pembacaan jauh lebih banyak daripada penulisan untuk array kecil dengan panjang tetap?

Salinan penuh bisa menjadi masuk akal jika array berukuran kecil dan pembacaan O(1) lebih diprioritaskan daripada biaya snapshot. Bandingkan panjang aktual, jumlah snapshot, tingkat pembacaan, dan anggaran memori. Desain riwayat perubahan mengoptimalkan penulisan yang jarang dan pembuatan snapshot; desain ini tidak serta-merta menjadi yang terbaik untuk setiap beban kerja (workload).