Cerință
Un cache poate păstra cel mult c perechi cheie-valoare. Operația 1 k caută cheia k: afișează valoarea sau -1 dacă lipsește. O căutare reușită face cheia cea mai recent utilizată. Operația 2 k v inserează sau actualizează valoarea și face cheia cea mai recentă. Dacă se depășește capacitatea, elimină cheia nefolosită de cel mai mult timp. Simulează cache-ul LRU; o căutare eșuată nu modifică ordinea.
Tip de problemă: LRU Cache.
Date de intrare
Prima linie: c și q. Urmează q operații de forma 1 k sau 2 k v.
Date de ieșire
Pentru fiecare operație 1, afișează rezultatul pe o linie. Operațiile 2 nu produc ieșire.
Restricții
1 ≤ c,q ≤ 2000; 1 ≤ k ≤ 2000; 0 ≤ v ≤ 1000000000. Există cel puțin o căutare.
Observații
Raportată de un candidat: LRU Cache la Amazon (screening telefonic, mai 2019).
Adaptare Algo25: Operații numerice pe chei întregi, capacitate fixă și ieșire deterministă.
Sursa relatării: https://leetcode.com/discuss/post/302349/amazon-sde-unknown-may-2019-reject/
Exemple
2 EXEMPLEExemplul 1
Exemplul 1, reprezentat vizual. O citire reușită mută cheia la început. Când cache-ul este plin, cheia de la final este eliminată.Mărește schema ↗Date de intrare
2 6
2 4 40
2 7 70
1 4
2 8 80
1 7
1 8
Date de ieșire
40
-1
80
Exemplul 2
Date de intrare
1 4
1 2
2 2 0
2 2 9
1 2
Date de ieșire
-1
9
Ai nevoie de un indiciu?
Descoperă doar cât îți trebuie. Indiciile nu scad punctajul.
Trimite o soluție
Se verifică autentificarea…
Deschide atelierul cu sugestii și teste locale în 4 limbaje →