Sets – Doesn’t maintain order and doesn’t allow repeated elements.
Stacks – Depth-first search, behave similar to recursion and can be a replacement for it.
Queues – Breadth-first search
Heaps – (Priority queue)
- Insertion – O(logn)
- Extract min/max – O(logn)
- Heapify – O(n)
- Delete – O(logn)
- Scheduled event managing.
- Median maintenance – using two heaps, one max heap, and one min heap.
- Dijkstra Algorithm – O(m log n)
Search trees –
- All the nodes should be connected.
- should not have cycles.
- Balanced binary search trees:
- Red-black trees.
- AVL trees.
- Splay trees.
Hash tables –
- When you don’t need to remember ordering, minimum or maximum.
- To check whether an element exists – O(1)
- Insertions and deletions – O(1)
- 2-sum problem.
- Hash function:
- Resolving collisions:
- Chaining: Linked lists inside each bucket.
- open addressing (probe sequence) – one object per bucket.
- Choose num of buckets as a prime number.
- Load factor: Num of objects/ Num of buckets.
- Every hash function has a pathological data set.
- Randomization from a family of hash functions at runtime.
Hashing – Use a hash function which deduces the index in which to store the value based on the digits of the value itself (usually last few digits). Store the value in the provided index. when you want to lookup, it is of O(1), since lookup from an indexed array is of constant time.
Bloom filters –
- More space efficient than hash tables.
- No deletions.
- Small false positive probability – might say x has been inserted even though it hasn’t been.
- Fast inserts and lookups.
- List of forbidden passwords.
- Network routers – Limited memory, need to be super fast.