← Semua lesson · Pattern 1 dari 15 · variasi 2 · lanjutan dari “sudah pernah lihat belum?”

Hashing: “sudah berapa kali?”

1. Cerita

Kamu pegang log transaksi kafe hari ini: kopi, teh, kopi, roti, kopi. Manajer tanya: “Produk apa yang paling laku?”

Di Excel, ada dua cara:

Tabel kecil itu adalah dict Python: key = nama produk, value = jumlahnya. Di lesson 1, buku catatan kita (set) hanya bisa jawab “ada atau tidak?”. Dict bisa menyimpan informasi tambahan per key — di sini: hitungan.

2. Kenapa

Masalahnya: menghitung ulang hal yang sama. Cara A menghitung “kopi” tiga kali (di baris 1, 3, dan 5), dan tiap kali membaca semua data dari awal.

Sinyal di soal: paling sering, frekuensi, jumlah kemunculan, anagram, apakah dua list isinya sama, kelompokkan berdasarkan…

3. Brute force & 4. Aha

Satu baris di Cara A = membaca 5 transaksi, jadi “Kerja” naik 5.

Aha: Cara A tidak menyimpan hasil hitungannya, jadi ia menghitung “kopi” dari nol tiga kali. Cara B menyimpan hitungan di dict dan cukup menambah +1. 25 vs 8. Dengan 10.000 transaksi: 100 juta vs ±10.000.

5. Kode

Brute force (COUNTIF tiap baris):

def most_sold(items):
    best, best_count = None, 0
    for x in items:              # tiap baris…
        c = 0
        for y in items:          # …baca semua transaksi lagi
            if y == x:
                c += 1
        if c > best_count:
            best, best_count = x, c
    return best

O(n²) time — loop di dalam loop. O(1) space — tidak menyimpan apa-apa.

Hashing (PivotTable):

def most_sold(items):
    count = {}                              # tabel pivot kosong
    for x in items:
        count[x] = count.get(x, 0) + 1      # belum ada → mulai dari 0, lalu +1
    return max(count, key=count.get)        # key dengan value terbesar

O(n) time — tiap transaksi dibaca sekali. O(k) space — k = jumlah produk berbeda (3), bukan jumlah transaksi.

Versi singkat dari stdlib: Counter(items).most_common(1) — lihat patterns/00_stdlib.py. Di interview, boleh pakai, tapi pastikan kamu bisa menulis versi dict-nya.

Cek ingatan: set atau dict?

Jawab dalam hati dulu, baru klik.

Cek apakah ada email pelanggan yang terdaftar dua kali.

set — cukup “sudah pernah lihat?”.

Hitung berapa kali tiap kata muncul di review produk.

dict — kata → jumlah.

Cari dua harga yang totalnya pas Rp100.000, dan kembalikan posisi keduanya.

dict — harga → posisi. Butuh info tambahan (posisi), bukan sekadar ada/tidak. Kenal soal ini? Itu Two Sum.

Apakah “listen” dan “silent” terdiri dari huruf yang sama persis?

dict — hitung tiap huruf di kedua kata, bandingkan kedua tabel. Ini “Valid Anagram”.

6. Giliranmu

  1. Two Sum dulu (dari lesson 1) — leetcode.com/problems/two-sum. Pertanyaan kunci: dict-mu menyimpan apa → apa?
  2. Lalu Group Anagrams — leetcode.com/problems/group-anagrams. Pertanyaan kunci: kata-kata yang satu kelompok, punya label apa yang sama?

Tiap soal: cp templates/problem.py patterns/01_hashing/<nama>.py → brute force dulu → baru hashing → uv run pytest file itu.

Stuck? Ketik hint ke tutor — satu tingkat per permintaan. Ada yang belum jelas? Tanya saja ke agent, kapan pun.

Sumber utama: NeetCode roadmap → Arrays & Hashing (tonton “Valid Anagram” dan “Group Anagrams”).