Data structures

• A HyperLogLog is a probabilistic data structure used in order to count unique things
  • https://stackoverflow.com/questions/12327004/how-does-the-hyperloglog-algorithm-work
• Queue is used for BFS, while stack is used for DFS.
• XOR doubly linked list: Essentially utilizing the 'previous' address during traversal
• A stack can be implemented with two queues https://www.geeksforgeeks.org/implement-stack-using-queue/
• Skip list implementation?
• Red-Black Tree
  • Enumerate a finite number of cases to consider
  • Use simplified number to represent the key for nodes and sub-tree
  • How does color come into play?
• NP hard
  • traveling salesman
    • https://www.geeksforgeeks.org/travelling-salesman-problem-set-1
  • the knapsack problem
• Lowest Common Ancestor in a tree?
  • https://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/
• Prefix tree or trie

Binary-Search Tree

a rooted binary tree whose internal nodes each store a key greater than all the keys in the node's left subtree and less than those in its right subtree.

BST can be used for implementing a K→V dictionary API.

def insert(key, value, bst):
  if bst.key is None or bst.key == key: # empty tree
    bst.key = value
  elif bst.key < key:
    insert(key, value, bst.left)
  else:
    insert(key, value, bst.right)

Hash function

Hash function: uniformity.

Chaining is better than linear probing when the load factor increases.

https://softwareengineering.stackexchange.com/questions/278459/what-are-the-advantages-of-linear-probing-over-separate-chaining-or-vice-versa-w

http://cseweb.ucsd.edu/~kube/cls/100/Lectures/lec16/lec16-14.html How to choose hash function for String.