This repository will document my journey of obtaining of computer science fundamentals, such as data structures and algorithms. I will add the most relevant and important imformation that I find on my journey, and document it here in the readme. The subsequent repository directories will contain the codebase for implementing these datastructures and algorithms. Thank you for visiting!
O(1) - Constant time
- Same amount of time, regardless of the number of elements
i.e. Random accesss array
O(log n) - Logarithmic
- When doubling the number of elements doesn't double the time (binary trees)
i.e. Search algorithms
O(n) - Linear
- Adding element increases the runtime linearly
i.e. Looping an array/list
O(n log n) - Quasilinear
- Every element has to be compared with every other element. Lots of comparisons
i.e. Sorting algorithms
O(n^2) - Quadratic
- 2, 4, 8, 16, 32, 64 Increasing quadratically
i.e. Nested loops
O(2^n) - Exponential. Recursion
i.e. Fibonacci series
Operation takes same amoutn of time (regardless of the number of elements) O(1) i.e.
if(n = 10) {}
int j = 8*1000;
Iterating through a collection (for loop, while loop) O(n) i.e.
for (...) {}
while (...)
Looping through same collection x2 (nested) O(n^2) i.e.
for (int i) {
for (int j) {
}
}
Fibonacci series - recursion O(branch^depth) 2^n i.e.
Searching sorted array (i.e. binary tree) O(log n) i.e.
Sorting O(n log n) i.e.
Drop the non-dominant terms
O(n^2 + n) -> O(n^2)
Drop the constants
O(3n) -> O(n)
for (int n: arrayN) {
print(n);
}
for (int n:arrayN) {
for(int m: arrayM) {
print(n + "," + n);
}
⚠️ Note: Not O(n^2)
Reduce these
O(n + log n) -> ?
Click to see answer!
O(n)O(7*2^n + 5000*n^99) -> ?
Click to see answer!
O(2^n)Which is equivalent to O(n)?
O(n + m) where m < n/2 ?
Click to see answer!
EquivalentO(2n) ?
Click to see answer!
EquivalentO(n + log n) ?
Click to see answer!
EquivalentO(n + m) ?
Click to see answer!
Not EquivalentArray - killer feature is O(1) random access (get/set)
- Can hold anything
- Fixed size
- Random access
Get O(1)
Set O(1)
Insert O(n)
Delete O(n)
LinkedList - killer feature is O(1) Add Front
- No random access
- No fixed capacity
- Always the right size
getFirst O(1)
getLast O(n)
Add Front O(1)
Add Back O(n)
Delete O(n)
ArrayList - Wrapper around array, offers convienance API.
- Dynamic resizing
Get O(1)
Set O(1)
Insert O(n)
Delete O(n)
Stack - Killer feature is O(1) push/pop
- LIFO - Last in First Out (LIFO)
Access O(n)
Search O(n)
Push O(1)
Pop O(1)
Queue - Killer feature is O(1) add/remove
- First in First Out
Access O(n)
Search O(n)
Add O(1)
Remove O(1)
Top 10 Algorithms for the Coding Interview
https://www.youtube.com/watch?v=r1MXwyiGi_U
Binary Search
https://www.youtube.com/watch?v=P3YID7liBug
Depth First Search (DFS) / Breadth First Search (BFS)
https://www.youtube.com/watch?v=zaBhtODEL0w
Bubble Sort
https://www.youtube.com/watch?v=6Gv8vg0kcHc
Merge Sort
https://www.youtube.com/watch?v=KF2j-9iSf4Q
Quick Sort
https://www.youtube.com/watch?v=SLauY6PpjW4
Hashtables
Big O Notation
https://www.youtube.com/watch?v=v4cd1O4zkGw
Binary Tree Diameter
https://www.youtube.com/watch?v=TQI_m32_AeU
Valid Parenthesis
https://leetcode.com/problems/valid-parentheses/
Longest Palindromic Substring
https://leetcode.com/problems/longest-palindromic-substring/
Reverse Linked List
https://leetcode.com/problems/reverse-linked-list/
Remove Duplicates Linked List
https://leetcode.com/problems/remove-duplicates-from-sorted-list/
https://github.com/mission-peace/interview/wiki
https://github.com/jwasham/coding-interview-university
https://github.com/donnemartin/system-design-primer
https://www.educative.io/courses/grokking-the-system-design-interview
https://inst.eecs.berkeley.edu/~cs61b/fa19/
https://www.youtube.com/playlist?list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb