The idea is to focus on implementing basic important data structures and algorithms on very basic problems. These data structures are not exhaustive, but these are the algorithms that we occasionally come across. This would help in two ways:
- Learn the exact insights and mechanisms about algorithms by heart.
- Developing Template for the common data structures and algorithms for later reuse.
Note:
-
When using python, use pypy in contests, if available, when solving questions because it's a faster alternative to cpython. Just read about it.
-
All FAANG companies mostly focus on these algorithms only. This are high leverage algorithms from the interview perspective.
- (Two Pointers) Floyd's Algorithm (The Tortoise and the Hare)
- (Two Pointers) Old and new state
- (Two Pointers) Start and end of sliding window
- Linked List
- Doubly Linked List
- Circular Linked List
- Hash Table
- Stack
- Monotonic stack
- Queue
- Recursion example
- Divide and Conquer
- Insertion Sort
- Merge Sort/(Two Pointers) Pointer-1 and pointer-2 from two sequences
- Bubble Sort
- Selection Sort
- Quick Sort
- Counting Sort
- (Order Statistics) Quick Select
- Binary Search/ (Two Pointers) Left and right boundary
- Binary Search(using bisect)
- Heap/Priority Queue
- Trie
- Rolling hash
- Disjoint Set
- Binary Tree
- Binary Search Tree
- Adjacency List
- Adjacency Matrix
- Edge List
- Breadth First Search
- Depth First Search
- Tree Traversal (Inorder, Preorder, Postorder, Level Order)
- Dijkstra's Algorithm (Priority queue)
- Bellman Ford Algoritm
- Floyd Warshall Algorithm
- Prim's Algorithm
- Krushkal's Algorithm
- Eular Path/Circuit
- Kosaraju’s algorithm(Strongly connected components)
- Detecting Cycle in graph(Back/Forward/tree edge)
- Topological Sort
- Backtracking
- Greedy Algorithm Knapsack
- Dynamic Programming Top down DP
- Bottom Up DP
- DP with bit masking
- Euclid's Algorithm (Greatest common divisor)
- Exponentiation algorithm (Exponentiation by squaring D&C)
- Sieve of Eratosthenes
For more advanced topics and deep dive into competitive programming, refer this book: https://cses.fi/book/book.pdf as suggested by top coders.
I came across some new things about python while learning. You might also come across these at some time. Read these blogs for help understanding them, beforehand, so that you don't get stuck like me:
- https://book.pythontips.com/en/latest/for_-_else.html
- https://stackoverflow.com/questions/1907565/c-and-python-different-behaviour-of-the-modulo-operation
- https://www.programiz.com/python-programming/global-local-nonlocal-variables#:~:text=Nonlocal%20variables%20are%20used%20in,keywords%20to%20create%20nonlocal%20variables.
- https://stackoverflow.com/a/9674327/6725646
| Input size | Target time complexity |
|---|---|
| n ≤ 12 | O(n!) |
| n ≤ 25 | O(2^n) |
| n ≤ 100 | O(n^4) |
| n ≤ 500 | O(n^3) |
| n ≤ 10 000 | O(n^2) |
| n ≤ 1 000 000 | O(n log n) |
| n ≤ 100 000 000 | O(n) |
| n > 100 000 000 | O(1) or O(log n) or O(n ^ (1/2)) |
Are there any other algorithm that I might be missing? Please open a pull request and contribute! Let's learn together.
- https://www.programiz.com/
- https://www.geeksforgeeks.org/
- https://codeforces.com/blog/entry/21344
- https://www.pluralsight.com/guides/algorithm-templates:-introduction
- https://leetcode.com/problems/sum-of-subarray-minimums/discuss/178876/stack-solution-with-very-detailed-explanation-step-by-step
- https://leetcode.com/problems/binary-tree-right-side-view/solution/
- https://realpython.com/python-recursion/
- https://www.youtube.com/watch?v=pPiSMPWKZ3E
- https://medium.com/techtofreedom/algorithms-for-interview-2-monotonic-stack-462251689da8
- https://www.youtube.com/watch?v=rf6uf3jNjbo
- https://towardsdatascience.com/implementing-a-trie-data-structure-in-python-in-less-than-100-lines-of-code-a877ea23c1a1
- https://codeforces.com/blog/entry/60445
- https://www.youtube.com/watch?v=wU6udHRIkcc
- https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/
- https://www.hackerearth.com/practice/algorithms/graphs/minimum-spanning-tree/tutorial/
- https://www.youtube.com/watch?v=5M-m62qTR-s
- https://www.youtube.com/watch?v=AamHZhAmR7o
- https://www.geeksforgeeks.org/strongly-connected-components/
- https://favtutor.com/blogs/topological-sort-python
- https://medium.com/algorithms-and-leetcode/backtracking-e001561b9f28
- https://www.geeksforgeeks.org/greedy-algorithms/
- https://www.youtube.com/watch?v=YBSt1jYwVfU&list=PLl0KD3g-oDOGJUdmhFk19LaPgrfmAGQfo
- https://www.youtube.com/playlist?list=PL_z_8CaSLPWekqhdCPmFohncHwz8TY2Go
- https://medium.com/analytics-vidhya/bits-bitmasking-62277789f6f5
- https://www.youtube.com/watch?v=B5HKW99AvV0
- https://codecrucks.com/exponential-problem-solving-using-divide-and-conquer/
- https://python.plainenglish.io/prime-numbers-using-sieve-of-eratosthenes-in-python-b917ae6188c7
- https://www.geeksforgeeks.org/sieve-of-eratosthenes/
- https://gobyexample.com/