Silabus Pelajaran 134 dari 148 · Kalahkan Ghost kamu
Kalahkan Ghost kamu

Tanpa cache: diskon warisan

Kenapa ini penting "Ini mengulang pekerjaan, jadi ingatlah jawabannya" adalah salah satu kebiasaan terkuat dalam pemrograman, baik manusia maupun AI. Kadang pekerjaan tidak perlu diulang sama sekali.

Kategori toko

A membentuk sebuah pohon: Garden ada di bawah Home, Tools ada di bawah Garden, dan seterusnya. Manajer pemasaran bisa mengatur diskon pada kategori apa pun, dan itu berlaku untuk semua yang ada di bawahnya kecuali kategori yang lebih dekat mengatur diskonnya sendiri. Checkout mencari diskon efektif untuk ribuan kategori sekaligus.

Data

parents = {"home": None, "garden": "home", "tools": "garden", "seeds": "garden"}
own = {"garden": 10, "seeds": 25}           # discounts set directly, in percent
queries = ["tools", "seeds", "home"]
# effective_discounts(parents, own, queries) -> [10, 25, 0]

Solusi jelas untuk jalan yang berulang ke atas pohon adalah cache. Di masalah ini cache dilarang. Cari cara yang tidak mengulang pekerjaan sejak awal.

Giliranku

Tulis effective_discounts(parents, own, queries). parents memetakan setiap kategori ke induknya, atau None untuk kategori tingkat atas (bisa ada beberapa, dan dict tidak berurutan). own memetakan beberapa kategori ke diskonnya sendiri. Untuk setiap kategori di queries, kembalikan diskon dari kategori terdekat di jalurnya ke atas, dimulai dari dirinya sendiri, yang punya diskon di own; 0 jika tidak ada. Aturan: jangan pakai cache atau memo: jangan pakai dekorator cache functools, jangan pakai nama yang mengandung "cache" atau "memo", dan jangan simpan jawaban yang sudah dikerjakan karena kueri memintanya dan menyimpannya (memo dengan nama lain). Telusuri seluruh pohon dulu, baru baca kueri. Budget: maksimal 500,000 langkah (steps()) untuk 3,000 kategori, pohon hingga beberapa ratus level dalam, dan 20,000 pencarian.

Ada masalah di pelajaran ini? Laporkan · Tanya tentang pelajaran ini

Latihan ini akan segera dibuka

Selesaikan pelajaran sebelumnya agar pelajaran ini terbuka. Seluruh kursus ini gratis, tidak butuh akun, dan kamu bisa baca pelajaran ini sekarang.