design

• design

  • Cache - [TODO]

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)