What we discussed

Data Structures

  1. Lists
    1. ArrayList - list made using arrays, Advantage is random access is fast, disadvantage is when scalling up access becomes slow
    2. LinkedList - list made using nodes, Advantage is scalling up is easy, disadvantage is random access is slow
  2. Queues - FIFO First In First Out
  3. Stacks - LIFO Last In First Out
  4. Heaps/ Priority Queue - Special kind of tree, where root is always the max or min element
    1. Max Heap - Root node is always max
    2. Min Heap - Priority Queue - Root node is always min
  5. Trees
    1. Binary Tree
      1. Binary Search Tree - A special kind of tree where left node is always smaller than root and right node is always greater than root
    2. Self Balancing trees
      1. AVL Tree - A special kind of tree where height of left and right subtree of every node differs by atmost 1
      2. Red Black Tree - A special kind of tree where height of left and right subtree of every node differs by atmost 1 and root is always black
    3. N-Arry Tree - A tree where each node can have atmost n children 6. Maps - Key Value Pair
    4. HashMap - A map where keys are stored in a hash table
    5. Tree Map - A map where keys are stored in a tree, so keys are always sorted, so we can do range queries. Keys have to be comparable though
  6. Graphs - A set of nodes connected by edges
  7. Cyclic - A graph where there is a cycle
  8. Acyclic - A graph where there is no cycle
  9. Trie -- for dealing with string search - A special kind of tree where each node has k children if our search space is k characters, basically one child for each character
  10. Segment Tree - A special kind of tree where each node stores the result of a range of values
  11. Fenwik Trees / Binary Indexed Trees - A special kind of tree where each node stores the result of a range of values, but it is more space efficient than segment tree because it uses an array instead of a tree and we store the result of a range of values in a node only if that node is a power of 2
  12. Suffix Tree - A special kind of tree where each node stores a suffix of a string
  13. Suffix Array - A special kind of array where each element stores a suffix of a string

Algorithms

  1. Searching
  2. Linear Search- O(n) - search through each element one by one
  3. Binary Search - O(log(n)) - search by dividing the search space into half each time and searching in the half where the element can be, only works on sorted arrays
  4. Sorting
    1. Bubble Sorts - O(n^2) - keep swapping adjacent elements if they are not in order
    2. Insertion Sort - O(n^2) - keep inserting elements in the right place. basically pick an element and insert it into right spot
    3. Selection Sort - O(n^2) - keep selecting the smallest element and putting it in the right place. Select a spot and pick right element
    4. Bucket Sort - O(n) - only works on integers, create buckets and put elements in the right bucket, then sort each bucket
    5. counting Sort - O(n) - only works on integers, create buckets and put elements in the right bucket, then empty the buckets
    6. Radix Sort - O(n*k) where k is number of digits - only works on integers, sort by each digit from least significant to most significant using bucket sort
    7. Quick Sort - O(n^2) | avg case - O(nlog(n)) - pick a pivot and put all elements smaller than pivot to the left and all elements greater than pivot to the right, then sort the left and right subarrays
    8. Merge Sort - O(nlog(n)) - divide the array into two halves, sort each half and then merge the two sorted halves
    9. heap sort - O(nlog(n)) - create a max heap, then keep removing the root and putting it at the end of the array
  5. Graph
    1. BFS - O(V+E) - Breadth First Search - visit all nodes at a level before going to the next level, where V is number of vertices and E is number of edges
    2. DFS - O(V+E) - Depth First Search - visit all nodes in a path before going to the next path, where V is number of vertices and E is number of edges
    3. Topological Sort - O(V+E) - Visit nodes which have no incoming edges first, where V is number of vertices and E is number of edges
    4. FloodFill - O(V+E) - Visit all nodes connected to a node, where V is number of vertices and E is number of edges
    5. Shortest path algos
      1. **Dijkstra's **- O(V+E) - Find shortest path from a source to all other nodes, where V is number of vertices and E is number of edges
      2. **Bellman Ford **- O(VE) - Find shortest path from a source to all other nodes, where V is number of vertices and E is number of edges
    6. Union Find / Disjoint set union - O(log(n)) - Find if two nodes are connected or not, where n is number of nodes 7.** Min Spanning Tree **- O(Elog(E)) - Find a tree which connects all nodes with minimum cost, where E is number of edges
      1. **Prims/ Kruskal's **- O(Elog(E)) - Find a tree which connects all nodes with minimum cost, where E is number of edges

For Tree Map

class Node:
        Key
        Value
        Node left, right

For Trie

class TrieNode:
        TrieNode[] children = new TrieNode[num-of-chars];
        boolean isWordEnd;