# H1Basic Knowledege

## H2Big O Notation

*Big O notation* is used to classify algorithms according to how their running time or space requirements grow as the input size grows.

Big O Notation | Type | Computations for 10 elements | Computations for 100 elements | Computations for 1000 elements |
---|---|---|---|---|

O(1) | Constant | 1 | 1 | 1 |

O(log N) | Logarithmic | 3 | 6 | 9 |

O(N) | Linear | 10 | 100 | 1000 |

O(N log N) | n log(n) | 30 | 600 | 9000 |

O(N^2) | Quadratic | 100 | 10000 | 1000000 |

O(2^N) | Exponential | 1024 | 1.26e+29 | 1.07e+301 |

O(N!) | Factorial | 3628800 | 9.3e+157 | 4.02e+2567 |

## H2Time Complexity

Time complexity measures the amount of time an algorithm takes to run as a function of the length of the input.

## H2Space Complexity

Space complexity measures the amount of memory an algorithm uses as a function of the length of the input.

Below is the list of some of the most used Big O notations and their performance comparisons against different sizes of the input data.

## H2Data Structure Operations Complexity

Data Structure | Access | Search | Insertion | Deletion | Comments |
---|---|---|---|---|---|

Array | 1 | n | n | n | |

Stack | n | n | 1 | 1 | |

Queue | n | n | 1 | 1 | |

Linked List | n | n | 1 | n | |

Hash Table | - | n | n | n | In case of perfect hash function costs would be O(1) |

Binary Search Tree | n | n | n | n | In case of balanced tree costs would be O(log(n)) |

B-Tree | log(n) | log(n) | log(n) | log(n) | |

Red-Black Tree | log(n) | log(n) | log(n) | log(n) | |

AVL Tree | log(n) | log(n) | log(n) | log(n) | |

Bloom Filter | - | 1 | 1 | - | False positives are possible while searching |

## H2Array Sorting Algorithms Complexity

Name | Best | Average | Worst | Memory | Stable | Comments |
---|---|---|---|---|---|---|

Bubble sort | n | n2 | n2 | 1 | Yes | |

Insertion sort | n | n2 | n2 | 1 | Yes | |

Selection sort | n2 | n2 | n2 | 1 | No | |

Heap sort | n log(n) | n log(n) | n log(n) | 1 | No | |

Merge sort | n log(n) | n log(n) | n log(n) | n | Yes | |

Quick sort | n log(n) | n log(n) | n2 | log(n) | No | Quicksort is usually done in-place with O(log(n)) stack space |

Shell sort | n log(n) | depends on gap sequence | n (log(n))2 | 1 | No | |

Counting sort | n + r | n + r | n + r | n + r | Yes | r - biggest number in array |

Radix sort | n * k | n * k | n * k | n + k | Yes | k - length of longest key |

# H1Data Structures

## H2Linked List

Note:

`let a = head;`

In this scenario, if we run`a.next = a.next.next`

, the linked list pointed to by`head`

will change because we modified the property of a node.

## H2Stack

LIFO (Last in, first out)

## H2Queue

FIFO (First in, first out)

## H2Hash Table

## H2Trie

The **trie data structure**, also known as a **prefix tree**, is a tree-like data structure used for efficient retrieval of key-value pairs. It is commonly used for implementing dictionaries and autocomplete features, making it a fundamental component in many search algorithms.

## H2Tree

**Tree Data Structure** is a hierarchical data structure in which a collection of elements known as nodes are connected to each other via edges such that there exists exactly one path between any two nodes.

**Parent Node****Child Node****Root Node****Leaf Node or External Node****Ancestor of a Node****Descendant****Sibling****Level of a node****Internal node**: A node with at least one child is called Internal Node.**Neighbor of a Node**: Parent or child nodes of that node are called neighbors of that node.**Subtree****Number of edges**: An edge can be defined as the connection between two nodes. If a tree has N nodes then it will have (N-1) edges. There is only one path from each node to any other node of the tree.**Depth of a node**: The depth of a node is defined as the length of the path from the root to that node. Each edge adds 1 unit of length to the path. So, it can also be defined as the number of edges in the path from the root of the tree to the node.**Height of a node**: The height of a node can be defined as the length of the longest path from the node to a leaf node of the tree.**Height of the Tree**: The height of a tree is the length of the longest path from the root of the tree to a leaf node of the tree.**Degree of a Node**: The number of children of a node. The degree of a leaf node must be. The degree of a tree is the maximum degree of a node among all the nodes in the tree.***0***

Adjacency List: It's a data structure used to represent a graph where each node in the graph stores a list of its neighboring vertices.

### H3Binary Tree

A Binary Tree is a non-linear data structure in which a node can have either 0, 1 or maximum 2 nodes. Each node in a binary tree is represented either as a parent node or a child node. There can be two children of the parent node, i.e., left child and right child.

### H3Binary Search Tree

A Binary Search Tree is a tree that follows some order to arrange the elements, whereas the binary tree does not follow any order. In a Binary search tree, the value of the __left__ node must be __smaller__ than the __parent node__, and the value of the __right__ node must be __greater__ than the __parent node__.

### H3Tree Traversal

## H2Graph

**Graph** Data Structure is a collection of **nodes** connected by **edges**. It’s used to represent relationships between different entities. Graph algorithms are methods used to manipulate and analyze graphs, solving various problems like __finding the shortest path__ or __detecting cycles__.

### H3Adjacency Matrix/List

### H3Detect cycle in an undirected graph

# H1Algorithms

- Sorting
- Recursion
- Backtracking

## H2Math

### H3Euclidean Algorithm

In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the **Greatest Common Divisor** (GCD) of two numbers,

## H2Sliding Window

Sliding Window problems are problems in which a fixed or variable-size window is moved through a data structure, typically an array or string, to solve problems efficiently based on continuous subsets of elements. This technique is used when we need to find subarrays or substrings according to a given set of conditions.

## H2Boyer-Moore Voting Algorithm

It's used to find the majority element among the given elements that have more than N/ 2 occurrences. This works perfectly fine for finding the majority element which takes 2 traversals over the given elements, which works in O(N) time complexity and O(1) space complexity.

## H2Greedy Algorithm

A **greedy algorithm** is a type of optimization algorithm that makes locally optimal choices at each step with the goal of finding a globally optimal solution. It operates on the principle of “taking the best option now” without considering the long-term consequences.

**Steps for Creating a Greedy Algorithm**:

**Define the problem**: Clearly state the problem to be solved and the objective to be optimized.**Identify the greedy choice**: Determine the locally optimal choice at each step based on the current state.**Make the greedy choice**: Select the greedy choice and update the current state.**Repeat**: Continue making greedy choices until a solution is reached.

## H2Dynamic Programming

**Dynamic Programming (DP)** is a method used in mathematics and computer science to solve complex problems by breaking them down into simpler subproblems. By solving each subproblem only once and storing the results, it avoids redundant computations, leading to more efficient solutions for a wide range of problems.

**How Does Dynamic Programming (DP) Work?**

**Identify Subproblems**: Divide the main problem into smaller, independent subproblems.**Store Solutions**: Solve each subproblem and store the solution in a table or array.**Build Up Solutions**: Use the stored solutions to build up the solution to the main problem.**Avoid Redundancy**: By storing solutions, DP ensures that each subproblem is solved only once, reducing computation time.

## H2Searches

### H3Binary Search

In computer science, binary search, is a search algorithm that finds the position of a target value within a __sorted array__.

**Time Complexity**: `O(log(n))`

- since we split search area by two for every next iteration.

### H3BFS

**Breadth-first Search** algorithm is used to search a __tree__ or __graph__ data structure for a node that meets a set of criteria. It begins at the root of the tree or graph and investigates all nodes at the current depth level before moving on to nodes at the next depth level.

### H3DFS

**Depth-First Search** algorithm is a __recursive__ algorithm that uses the __backtracking__ principle. It entails conducting exhaustive searches of all nodes by moving forward if possible and backtracking, if necessary.

## H2Sorting

### H3Bubble Sort

### H3插入排序

### H3快速排序

## H2Divide and Conquer

**Divide and Conquer** is a problem-solving strategy that involves breaking down a complex problem into smaller, more manageable parts, solving each part individually, and then combining the solutions to solve the original problem.

# H1Notes

`str[index]`

accessing data method is more efficient than`.at()`

,`.slice()`

etc.`Number("0")`

is more efficient than`+"0"`

.- Spread syntax is more efficient than
`split("")`

. Such as`[…"abc"]`

and`"abc".split("")`

. `Math.max|min`

is more effcient than`< >`

.`Set`

is more effcient than`Array`

in terms of searching a certain element.- Tree的DFS里，从根节点往子节点传递值的话，可以用放dfs函数的参数里；从子节点往根节点传递值，可以放dfs函数的返回值里；

# H1References

**Videos**:

**Docs**: