Category: custom_ds
-
LeetCode 146. LRU Cache
link Dict and LinkedList If we did not have to evict keys, we could just keep a {key -> value} map. When there are too many keys, we need to evict the least-recently-used key therefore the key for which a get or put was called furthest into the past. As a result, we need to…
-
LeetCode 981: Time Based Key-Value Store
link Note, if get() is called for a timestamp that was not set, we need to find the latest value until that timestamp. In other words, say for a key, we have (1, val1), (2, val2, 2), (5, val3) where 1, 2, and 5 are timestamps. For that key, if get() is now called with…
-
LeetCode 1146. Snapshot Array
link We keep the below three pieces of information: On get(), we may need to search through earlier snapshots to get the value at an index that has not changed for a while. Say snap‘s have been called. Operation Time Space __init__ set snap get