Big O - worst case Clasification - 3:41

• Search
  • Singly O(n)
  • Doubly O(n)
• Insert at head
  • Singly O(1)
  • Doubly O(1)
• Insert at tail
  • Singly O(1)
  • Doubly O(1)
• Remove at head
  • Singly O(1)
  • Doubly O(1)
• Remove at tail
  • Singly O(n) : because need to find new tail
  • Doubly O(1) : because tail have previous pointer which will become the new tail
• Remove at middle
  • Singly O(n)
  • Doubly O(n)

1. while
2. recursive

1. for i=0; i<n; i++ O(n)
2. for i=0; i<n; i=i+2 O(n)
3. for i=n; i>0; i=-- O(n)
4. for i=0; i<n; i=i*2 O(log n) base 2
5. for i=0; i<n; i=i*3 O(log n) base 3
6. for i=0; i<n; i=i/2 O(log n) base 2

1. Choice + decision
2. Find the base case
3. Find the small input for next call
4. Logic to do task
5. Normally ans on leaf node
6. Three type of problem solve by recursion
   1. DP: (asking about optimal) answer on the root (recursion + memory)
   2. Backtracking: (all the combination) answer on path
   3. DnC: ?

Watch till 1.11

1. Binary tree have at most two children
2. Binary search tree: Left sub tree has smaller and right sub tree have larger elements
3. examples

     5
    / \
  9     8
/       /\
1      7  10
      /\
    6   9

Above tree is not a BST as 9 is in the left subtree of 8

    1
      \
      20
      /
    19
    /
  2
    \
      3
        \
          18
        /
      17

Above tree is BST as each node's right sub tree have larger element and left have smaller element

1. Heap will be visually represent via tree

2. Heap will be stored via array

   100 /
   19 36 /\ /
   17 3 25 1 /\
   2 7

[100, 19, 36, 17, 3,25, 1, 2, 7]

Above is max heap, where root node represent the highest value in the heap. Every child will be less then their parent node

1. Heap in go require to implement container/heap interface
2. container/heap have following func which need to implement
   1. Len() int on value receiver
   2. Less(i, j int) bool on value receiver
   3. Swap(i, j int) on value receiver i<j for min heap and i>j for max heap
   4. Push(x interface{}) on pointer receiver
   5. Pop() interface{} on pointer receiver
3. heap need to init by heap.Init()
4. Push and pop will be done via heap.Push and heap.Pop

1. Subset, combination, permutation all needs backtracking algorithm
2. There are two class of problems
   1. Combination : Doesn't care about ordering ex. [1,2] and [2,1] are the same
   2. Permutation : Care about ordering ex "AB" and "BA" are different letters
3. Basic intuition:
   1. Choice : its all the choice made during the path of a tree
   2. Choose : What are going to choose on each node
   3. Explore : Explore further based on above chosen
   4. Un-choose : Un-choose so that next time, new chose can be made
4. Implement via recursion
5. Basic tricks and types of problem

https://www.youtube.com/watch?v=zL4mjpYpRmc

https://leetcode.com/explore/learn/card/binary-search/

1. Edge
2. Node/Vertex
3. Connected Graph
4. Dis-connected Graph
5. Directed and undirected graph
6. Cyclic and Acyclic graph
7. Storing connected graph

Implementation

1. Adjacency matrix
2. Adjacency list

Graph Traversal

1. DFS (Recursive & Iterative)
   1. Adjacency Matrix
   2. Adjacency List
2. BFS: Iterative
   1. Adjacency Matrix: DSA\graph\iterative_traversal.go
   2. Adjacency List

Topological Sort

1. Applicable on directed acyclic graph
2. If graph have cycle, it can't be applicable
3. It used where one item is dependent on another node. It used to find the ordering based on that.
4. Order depend upon which node pick first.
5. Sudo code
   1. Take a stack to store the order, visited array to track visited node
   2. for each node run dfs
      1. in dfs
         1. if node is already in visited; return
         2. Add node in visited
         3. for each node in adjacency list
            1. if node is not in visited, run dfs
         4. add node in stack (means during DFS, it reach to the node which doesn't have any adjacent node; means this node have no dependency)

Dynamic Programming

1. https://www.youtube.com/watch?v=9k31KcQmS_U
2. https://www.youtube.com/watch?v=8LusJS5-AGo&list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr
3. https://www.topcoder.com/thrive/articles/Dynamic%20Programming:%20From%20Novice%20to%20Advanced
4. https://www.youtube.com/watch?v=kvyShbFVaY8&list=PL_z_8CaSLPWekqhdCPmFohncHwz8TY2Go&index=3