design
design
432.All-O-one-Data-Structure (H) 380.Insert-Delete-GetRandom-O(1) (M+) 381.Insert-Delete-GetRandom-O1-Duplicates-allowed (H-) 716.Max-Stack (M+) 355.Design-Twitter (H) 535.Encode-and-Decode-TinyURL (M) 631.Design-Excel-Sum-Formula (H) 642.Design-Search-Autocomplete-System (M+) 895.Maximum-Frequency-Stack (H) 1146.Snapshot-Array (H) 1172.Dinner-Plate-Stacks (H) 1381.Design-a-Stack-With-Increment-Operation (H-) 1352.Product-of-the-Last-K-Numbers (M+) 1418.Display-Table-of-Food-Orders-in-a-Restaurant (H-) 1622.Fancy-Sequence (H+)
Cache - [TODO]
146.LRU-Cache (H-)\
Brute force: Use a single dictionary impl, key -> (value, timestamp)
Get: O(1)
Set: O(n) because need to pop out elements if exceed maximum capacity
Complexity optimal: Dictionary + LinkedList
Get: O(1)
Set: O(1)
Simplest: Use the Python bulit-in OrderedDict impl (not SortedDict which order items based on keys) https://www.kunxi.org/2014/05/lru-cache-in-python/
Get: O(1)
Set: O(1)
460.LFU Cache (H)\
Brute force: Use a single dictionary impl, key -> (value, frequency)
Get: O(1)
Set: O(nlogn)
Direct inherit from LRU: Dictionary + linkedlist. Sort linkedlist using bubblesort https://www.kunxi.org/2016/12/lfu-cache-in-python/
Get: O(1)
Set: O(N) in LRU there is no sorting needed, but in LFU there is.
Dictionary + BST tree:
Get: O(1) + log(N) because BST needs to be balanced
Set: O(1) + log(N) because BST needs to delete element
MY original solution: https://www.kunxi.org/2016/12/lfu-cache-in-python/
One dictionary: key -> freq, another dictionary freq -> defaultdict(ordereddict)
Get: O(1)
Set: O(1)
Last updated