Mengimplementasikan LRU Cache dengan Get dan Put O(1)

Konteks dan Deskripsi Soal

Implementasikan LRUCache(capacity) untuk bilangan bulat positif capacity. Kunci dan nilai adalah bilangan bulat non-negatif. get(key) mengembalikan nilai yang tersimpan atau -1 saat kuncinya tidak ada. put(key, value) menyisipkan atau memperbarui sebuah kunci. get yang berhasil dan setiap put menjadikan kunci tersebut sebagai yang paling baru digunakan. Menyisipkan kunci baru saat cache penuh akan menggusur tepat satu kunci yang paling lama tidak digunakan. Kedua operasi publik harus membutuhkan waktu expected O(1).

Ini adalah pertanyaan koding struktur data, bukan perancangan distributed cache. Implementasinya adalah proses tunggal dan berutas tunggal (single-threaded); ini tidak mencakup TTL, persistensi, bobot berbasis ukuran, atau akses konkuren. "Expected O(1)" bergantung pada asumsi performa rata-rata umum untuk operasi tabel hash. Perubahan pointer pada linked list adalah worst-case O(1).

Hasil yang penting bukanlah frasa "hash map ditambah doubly linked list." Jawaban yang lengkap menjabarkan alasan mengapa kedua struktur tersebut diperlukan, menyatakan invarian map–list, menangani pembaruan kunci yang sudah ada tanpa penggusuran yang tidak disengaja, dan memverifikasi urutan setelah setiap operasi.

Hal yang Dievaluasi oleh Pewawancara

Sinyal pertama adalah menerjemahkan kebutuhan menjadi operasi. Sebuah kunci harus ditemukan tanpa pemindaian (scanning), yang membutuhkan hash map. Keterkinian (recency) harus mendukung pemindahan kecocokan sembarang ke ujung yang paling baru dan menghapus ujung yang paling lama tidak digunakan. Doubly linked list dapat melakukan keduanya dalam kerja pointer konstan ketika map sudah menyediakan node tersebut.

Sinyal kedua adalah apakah kedua struktur tersebut membentuk satu kesatuan status (state). Map tidak dapat hanya menyimpan nilai; map harus memetakan setiap kunci ke node list-nya. Setiap node list sebenarnya harus memiliki tepat satu entri map, dan setiap entri map harus menunjuk ke tepat satu node sebenarnya di dalam list. Oleh karena itu, penggusuran menghapus kunci yang sama dari kedua struktur.

Sinyal ketiga adalah disiplin pointer. Node dummy head dan tail membuat semua node sebenarnya menjadi node interior. Pelepasan (detach) dan penyisipan tidak memerlukan kasus khusus untuk entri pertama, terakhir, atau satu-satunya. Seorang kandidat harus dapat menyatakan sisi mana yang paling baru sebelum menulis kode dan mempertahankan konvensi tersebut tanpa perubahan.

Terakhir, pewawancara mencari pengujian yang mengekspos urutan, bukan hanya nilai yang dikembalikan. Memperbarui kunci yang ada pada kapasitas penuh, membaca satu kunci berulang kali, menggunakan kapasitas satu, dan menyisipkan setelah terjadi kegagalan pencarian (miss) akan mengungkap bug yang luput dari satu contoh happy-path.

Pertanyaan Klarifikasi Sebelum Menjawab

• Apakah get memperbarui keterkinian? Dalam kontrak ini, ya. peek yang bersifat read-only akan menjadi operasi yang berbeda dan tidak akan memindahkan node.
• Apakah memperbarui kunci yang sudah ada menggunakan kapasitas? Tidak. put mengubah nilai dan keterkinian dari entri yang sama; operasi ini tidak boleh menggusur kunci lain.
• Apa yang dikembalikan jika terjadi miss? Masalah ini menggunakan -1, sehingga nilai harus dibatasi sesuai ketentuan atau API harus mengembalikan nilai opsional. Di sini nilainya adalah bilangan bulat non-negatif dan -1 dicadangkan untuk miss.
• Apakah kapasitas nol valid? Implementasi ini menolak kapasitas non-positif. Mendukung nol akan mengharuskan setiap penyisipan langsung menghilang dan mengubah kontrak konstruktor.
• Haruskah jaminannya berupa strict worst-case O(1)? Tabel hash biasanya memberikan expected constant time. Jaminan strict worst-case membutuhkan struktur lookup yang berbeda atau asumsi yang lebih kuat.
• Bisakah ordered map standar digunakan? Ini mungkin dapat diterima di lingkungan produksi atau latihan singkat, tetapi pewawancara tetap dapat meminta implementasi linked-list dasar beserta invarian-invariannya.
• Apakah thread safety diperlukan? Tidak. Jika ditambahkan, ingat bahwa get memutasi keterkinian, sehingga ini merupakan operasi penulisan (write) untuk tujuan sinkronisasi.

Kerangka Jawaban 30 Detik

“Saya memerlukan pencarian dan pembaruan keterkinian dengan waktu expected constant, jadi saya akan memetakan setiap kunci ke sebuah node dalam doubly linked list. Sisi head adalah yang paling baru dan sisi tail adalah yang paling lama tidak digunakan; node sentinel membuat pelepasan dan penyisipan menjadi seragam. Sebuah hit atau pembaruan akan memindahkan node-nya ke depan. Penyisipan baru yang melebihi kapasitas akan menghapus tail.prev dari kedua struktur. Karena map dan list berisi node sebenarnya yang sama, get dan put memiliki kompleksitas expected O(1), dengan ruang O(capacity).”

Jawaban Mendalam Langkah demi Langkah

List saja dapat mempertahankan keterkinian, tetapi menemukan kunci atau menghapus entri sembarang membutuhkan biaya O(n). Map saja dapat menemukan nilai dengan cepat, tetapi tidak dapat mengidentifikasi kunci yang paling lama tidak digunakan tanpa memindai atau menyimpan struktur pengurutan kedua. Array ditambah map masih memiliki pergeseran O(n) atau penemuan predecessor. Kedua persyaratan tersebut memaksa adanya indeks pencarian dan urutan yang dapat dimutasi.

Gunakan orientasi ini di sepanjang jawaban:

head <-> most recent <-> ... <-> least recent <-> tail

Sentinel tidak pernah masuk ke dalam map dan tidak pernah dihitung ke dalam kapasitas. Setiap node sebenarnya menyimpan key, value, prev, dan next; menyimpan kunci diperlukan karena penggusuran dimulai dari tail.prev dan harus menghapus entri map yang cocok tanpa pemindaian terbalik (reverse scan).

Empat invarian membuat implementasi ini dapat ditinjau dengan jelas:

1. head.next adalah node sebenarnya yang paling baru digunakan, dan tail.prev adalah node sebenarnya yang paling lama tidak digunakan ketika cache tidak kosong.
2. Kunci pada map dan node list sebenarnya mendeskripsikan kumpulan entri yang sama, secara satu-ke-satu (one-to-one).
3. Untuk setiap pasangan yang berdekatan, left.next is right dan right.prev is left.
4. Setelah setiap operasi publik, 0 <= len(nodes) <= capacity.

Implementasi ini menjaga manipulasi pointer dalam dua fungsi pembantu (helpers) karena get dan put sama-sama menggunakannya kembali:

class Node:
    __slots__ = ("key", "value", "prev", "next")

    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


class LRUCache:
    def __init__(self, capacity: int):
        if capacity <= 0:
            raise ValueError("capacity must be positive")

        self.capacity = capacity
        self.nodes = {}
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _detach(self, node: Node) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def _attach_after_head(self, node: Node) -> None:
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def _mark_recent(self, node: Node) -> None:
        self._detach(node)
        self._attach_after_head(node)

    def get(self, key: int) -> int:
        node = self.nodes.get(key)
        if node is None:
            return -1

        self._mark_recent(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        node = self.nodes.get(key)
        if node is not None:
            node.value = value
            self._mark_recent(node)
            return

        node = Node(key, value)
        self.nodes[key] = node
        self._attach_after_head(node)

        if len(self.nodes) > self.capacity:
            victim = self.tail.prev
            self._detach(victim)
            del self.nodes[victim.key]

Urutan penetapan pointer di dalam _attach_after_head sangat penting. Node baru pertama-tama menangkap node pertama lama, kemudian node lama tersebut menunjuk kembali ke node baru, dan baru setelah itu head.next berubah. Menimpa head.next terlalu cepat dapat menghilangkan tetangga yang masih membutuhkan pembaruan pada prev-nya.

Kebenaran logika ini dibuktikan melalui induksi atas operasi-operasinya. Inisialisasi memenuhi keempat invarian. Sebuah miss tidak mengubah apa pun. Sebuah hit atau pembaruan kunci yang sudah ada melepaskan satu node yang terpetakan dan memasukkan kembali node yang sama di depan, sehingga keanggotaan dan ukuran tidak berubah. Penyisipan baru menambahkan node ke kedua struktur; jika ukuran menjadi capacity + 1, menghapus tail.prev dari list dan kuncinya dari map akan memulihkan himpunan satu-ke-satu dan batas kapasitas. Kapasitas positif memastikan elemen yang digusur adalah node sebenarnya.

Dengan kapasitas dua, pelacakan langkah put(1,10), put(2,20), get(1), put(3,30), put(1,15) menghasilkan urutan keterkinian [1], [2,1], [1,2], [3,1], [1,3]. Kunci 2 digusur, sementara memperbarui kunci 1 mengubah nilainya tanpa menggusur kunci 3.

Di bawah performa rata-rata tabel hash, setiap metode publik melakukan satu pencarian ditambah sejumlah tetap operasi pointer dan map, sehingga waktu yang diharapkan adalah O(1). Map dan list menampung paling banyak capacity node sebenarnya, sehingga ruangnya adalah O(capacity). Ini bukan jaminan tabel hash strict worst-case.

Validasi harus menggabungkan pelacakan contoh dengan pemeriksaan invarian. Ujilah miss pada cache kosong, penolakan kapasitas nol, kapasitas satu, nilai berulang pada kunci berbeda, pembaruan pada kapasitas penuh, hit berulang, penggusuran bergantian, dan aliran operasi acak yang panjang. Untuk pengujian acak, bandingkan hasil dan urutannya dengan model referensi O(n) sederhana dan setelah setiap operasi lakukan assert pada pointer timbal balik, ketiadaan node duplikat, kesetaraan map–list, dan batas kapasitas.

Access-ordered map dapat mengekspresikan kebijakan yang sama secara lebih ringkas jika penggunaan pustaka diizinkan. LinkedHashMap milik Java mendukung access order dan hook penghapusan entri tertua (eldest-entry). Itu adalah opsi produksi yang berguna, tetapi tidak menggantikan pembuktian dalam wawancara. Pisahkan juga LRU in-process yang persis dengan penggusuran di tingkat produksi: sebuah server mungkin menggunakan approximate LRU berbasis sampel untuk mengurangi metadata global dan perebutan sumber daya (contention).

Contoh Jawaban Berkualitas Tinggi

“Pertama-tama saya akan menetapkan kontraknya: kapasitas positif, get mengembalikan -1 jika terjadi miss, dan setiap hit atau put memperbarui keterkinian. Memperbarui kunci yang sudah ada tidak menambah ukuran. Targetnya adalah expected O(1), berdasarkan pencarian tabel hash rata-rata.

Sebuah hash map menyelesaikan pencarian kunci tetapi tidak dengan urutan penggusuran. Doubly linked list menyelesaikan masalah pengurutan dan memungkinkan saya melepaskan node sembarang dalam kerja pointer konstan, asalkan saya sudah memegang node tersebut. Oleh karena itu, saya menyimpan key -> node di dalam map dan mengurutkan node dari yang paling baru setelah dummy head hingga yang paling lama tidak digunakan sebelum dummy tail. Setiap node menyimpan kuncinya sehingga penggusuran pada tail juga dapat menghapus entri map yang bersangkutan.

Invarian kuncinya adalah bahwa map dan node list sebenarnya merupakan himpunan yang sama. Pada saat hit, saya melepaskan node tersebut dan menyisipkannya setelah head. Pada saat update, saya mengubah nilainya dan melakukan pemindahan yang sama. Pada saat put baru, saya menambahkannya ke kedua struktur; jika ukuran melebihi kapasitas, saya menghapus tail.prev dari keduanya. Sentinel membuat operasi-operasi ini identik untuk entri pertama, terakhir, maupun satu-satunya entri.

Saya akan menguji kapasitas satu, pembaruan saat penuh, get berulang yang mengubah korban penggusuran, dan miss yang tidak boleh mengubah urutan. Saya juga akan menelusuri list setelah setiap operasi acak dan membandingkannya dengan model referensi yang lambat. Kompleksitas akhirnya adalah expected O(1) per operasi dan ruang O(capacity).”

Kesalahan Umum

• Hanya menyimpan nilai di dalam map → operasi hit masih perlu mencari pada struktur urutan → petakan setiap kunci langsung ke node list-nya.
• Menggunakan singly linked list → map menyediakan node tetapi bukan pendahulunya (predecessor), sehingga penghapusan sembarang dapat memerlukan pemindaian → simpan prev dan next.
• Lupa menyertakan kunci di dalam setiap node → penggusuran pada tail tidak dapat menghapus entri map tanpa pencarian terbalik → simpan kunci dan nilai di dalam node.
• Memperlakukan urutan penyisipan sebagai keterkinian → get yang berhasil kemudian gagal mengubah target penggusuran berikutnya → pindahkan setiap hit ke ujung yang paling baru.
• Melakukan penggusuran pada pembaruan kunci yang sudah ada → ukuran tidak bertambah, sehingga entri lain yang tidak terkait malah hilang → tangani pembaruan dan kembalikan nilai sebelum pemeriksaan kapasitas entri baru.
• Menghapus korban penggusuran hanya dari satu struktur → entri map yang basi atau node list siluman akan merusak operasi berikutnya → lakukan penggusuran secara simetris dan uji kesetaraan map–list.
• Menulis percabangan terpisah untuk head, tail, dan elemen tunggal → penanganan kasus pointer berlipat ganda dan salah satu batasan pada akhirnya akan menyimpang → gunakan dua sentinel permanen.
• Mengklaim strict O(1) → tabel hash umumnya memberikan batas expected dan kinerjanya dapat menurun jika terjadi tabrakan (collisions) → nyatakan asumsi hashing tersebut.
• Hanya menguji nilai kembalian → nilai yang benar dapat menyembunyikan urutan yang rusak hingga terjadi penggusuran di kemudian hari → periksa (assert) seluruh urutan keterkinian dan invarian pointer.

Pertanyaan Lanjutan dan Jawabannya

Pertanyaan Lanjutan 1: Bagaimana Anda membuatnya thread-safe?

get adalah operasi penulisan karena memodifikasi list. Ekstensi terprogram paling sederhana yang benar adalah menempatkan satu mutex di sekeliling keseluruhan get atau put, menjaga pembaruan map dan list tetap atomik. Read–write locking tidak menjadikan hit biasa sebagai operasi pembacaan (reader). Sharding mengurangi perebutan akses, tetapi setiap shard kemudian memiliki urutan LRU-nya sendiri; cara ini tidak lagi mengimplementasikan satu LRU global yang eksak kecuali mekanisme pengurutan bersama diperkenalkan kembali.

Pertanyaan Lanjutan 2: Bagaimana Anda menambahkan kedaluwarsa TTL?

TTL dan keterkinian adalah aturan penggusuran yang terpisah. Sebuah hit harus terlebih dahulu menolak entri yang telah kedaluwarsa, sementara put mungkin perlu menghapus entri yang kedaluwarsa sebelum menerapkan kebijakan kapasitas. Min-heap untuk waktu kedaluwarsa mendukung pembersihan malas (lazy cleanup) tetapi menambah pemeliharaan O(log n) dan rekaman heap yang basi; timing wheel mengubah presisi dan implementasi. Jangan terus mengklaim kedua operasi adalah O(1) tanpa mendefinisikan ulang mekanisme kedaluwarsa dan batasannya.

Pertanyaan Lanjutan 3: Bisakah Anda menyediakan strict worst-case O(1)?

Bagian linked list sudah memiliki jumlah operasi pointer yang konstan secara mutlak. Bagian pencarian bergantung pada jaminan tabel hash. Mencapai pencarian konstan strict worst-case membutuhkan model kamus (dictionary) yang lebih kuat, semesta kunci terbatas dengan pengalamatan langsung (direct addressing), atau asumsi hashing khusus. Dalam hash map bahasa pemrograman biasa, jelaskan hasilnya sebagai expected atau amortized O(1) sesuai dengan kontrak implementasi tersebut.

Pertanyaan Lanjutan 4: Mengapa tidak menggunakan LinkedHashMap atau OrderedDict?

Gunakan pustaka tersebut jika semantik access-order dan penggusurannya cocok dengan produk dan kode pointer manual tidak memberikan nilai tambah. Dalam wawancara, jelaskan terlebih dahulu invarian dasar map dan linked-order, kemudian tawarkan alternatif pustaka tersebut. Pastikan apakah pembaruan, pembacaan, iterasi, dan penghapusan entri tertua dihitung sebagai akses; map terurut dengan nama serupa tidak semuanya memiliki semantik keterkinian yang identik.

Pertanyaan Lanjutan 5: Apakah Anda akan menggunakan LRU eksak di server cache skala besar?

Tidak secara otomatis. Mempertahankan satu urutan akses global yang eksak menambah beban penulisan metadata dan menjadi titik perebutan (contention point) pada setiap hit. Cache produksi dapat membagi urutan (shard), mengambil sampel kunci kandidat, atau memilih LFU jika frekuensi memprediksi penggunaan ulang dengan lebih baik. Pilihan-pilihan tersebut mengorbankan ketepatan pemilihan korban demi memori dan throughput. Struktur data wawancara ini tetap berguna karena membuat kebijakan eksak dan invarian-invariannya dapat diuji.