- Linked List
- Queue
- Stack
- Hash Table
- Heap
- Priority Queue
- Trie
- Tree
- Binary Search Tree
- AVL Tree
- Red-Black Tree
- Suffix Tree
- Segment Tree or Interval Tree
- Binary Indexed Tree or Fenwick Tree
- Graph (both directed and undirected)
- Disjoint Set
- Math
- Factorial
- Fibonacci Number
- Primality Test (trial division method)
- Euclidean Algorithm - calculate the Greatest Common Divisor (GCD)
- Least Common Multiple (LCM)
- Integer Partition
- Sets
- Cartesian Product - product of multiple sets
- Power Set - all subsets of the set
- Permutations (with and without repetitions)
- Combinations (with and without repetitions)
- Fisher–Yates Shuffle - random permutation of a finite sequence
- Longest Common Subsequence (LCS)
- Longest Increasing subsequence
- Shortest Common Supersequence (SCS)
- Knapsack Problem - "0/1" and "Unbound" ones
- Maximum Subarray - "Brute Force" and "Dynamic Programming" (Kadane's) versions
- String
- Levenshtein Distance - minimum edit distance between two sequences
- Hamming Distance - number of positions at which the symbols are different
- Knuth–Morris–Pratt Algorithm - substring search
- Rabin Karp Algorithm - substring search
- Longest Common Substring
- Search
- Sorting
- Tree
- Depth-First Search (DFS)
- Breadth-First Search (BFS)
- Graph
- Depth-First Search (DFS)
- Breadth-First Search (BFS)
- Dijkstra Algorithm - finding shortest path to all graph vertices
- Bellman-Ford Algorithm - finding shortest path to all graph vertices
- Detect Cycle - for both directed and undirected graphs (DFS and Disjoint Set based versions)
- Prim’s Algorithm - finding Minimum Spanning Tree (MST) for weighted undirected graph
- Kruskal’s Algorithm - finding Minimum Spanning Tree (MST) for weighted undirected graph
- Topological Sorting - DFS method
- Articulation Points - Tarjan's algorithm (DFS based)
- Bridges - DFS based algorithm
- Eulerian Path and Eulerian Circuit - Fleury's algorithm - Visit every edge exactly once
- Hamiltonian Cycle - Visit every vertex exactly once
- Strongly Connected Components - Kosaraju's algorithm < 9EF3 /ul>
- Uncategorized
- Greedy
- Unbound Knapsack Problem
- Dijkstra Algorithm - finding shortest path to all graph vertices
- Prim’s Algorithm - finding Minimum Spanning Tree (MST) for weighted undirected graph
- Kruskal’s Algorithm - finding Minimum Spanning Tree (MST) for weighted undirected graph
- Divide and Conquer
- Tower of Hanoi
- Euclidean Algorithm - calculate the Greatest Common Divisor (GCD)
- Permutations (with and without repetitions)
- Combinations (with and without repetitions)
- Merge Sort
- Quicksort
- Tree Depth-First Search (DFS)
- Graph Depth-First Search (DFS)
- Dynamic Programming
- Fibonacci Number
- Levenshtein Distance - minimum edit distance between two sequences
- Longest Common Subsequence (LCS)
- Longest Common Substring
- Longest Increasing subsequence
- Shortest Common Supersequence
- 0/1 Knapsack Problem
- Integer Partition
- Maximum Subarray
- Bellman-Ford Algorithm - finding shortest path to all graph vertices
- Backtracking
- Hamiltonian Cycle - Visit every vertex exactly once
- N-Queens Problem
- Knight's Tour
- Branch & Bound
Install all dependencies
npm i
Run all tests
npm test
Run tests by name
npm test -- -t 'LinkedList'
You may play with data-structures and algorithms in ./src/playground/playground.js file and write
tests for it in ./src/playground/__test__/playground.test.js.
Then just simply run the following command to test if your playground code works as expected:
npm test -- -t 'playground'
▶ Data Structures and Algorithms on YouTube
Order of growth of algorithms specified in Big O notation.
Source: Big O Cheat Sheet.
Below is the list of some of the most used Big O notations and their performance comparisons against different sizes of the input data.
| Big O Notation | Computations for 10 elements | Computations for 100 elements | Computations for 1000 elements |
|---|---|---|---|
| O(1) | 1 | 1 | 1 |
| O(log N) | 3 | 6 | 9 |
| O(N) | 10 | 100 | 1000 |
| O(N log N) | 30 | 60 | 9000 |
| O(N^2) | 100 | 10000 | 1000000 |
| O(2^N) | 1024 | 1.26e+29 | 1.07e+301 |
| O(N!) | 3628800 | 9.3e+157 | 4.02e+2567 |
| Data Structure | Access | Search | Insertion | Deletion |
|---|---|---|---|---|
| Array | 1 | n | n | n |
| Stack | n | n | 1 | 1 |
| Queue | n | n | 1 | 1 |
| Linked List | n | n | 1 | 1 |
| Hash Table | - | n | n | n |
| Binary Search Tree | n | n | n | 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) |
| Name | Best | Average | Worst | Memory | Stable |
|---|---|---|---|---|---|
| Bubble sort | n | n^2 | n^2 | 1 | Yes |
| Insertion sort | n | n^2 | n^2 | 1 | Yes |
| Selection sort | n^2 | n^2 | n^2 | 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) | n^2 | log(n) | No |
| Shell sort | n log(n) | depends on gap sequence | n (log(n))^2 | 1 | No |