md data structure algorithm notes
-
- Click button choose
.md
file.
- Click button choose
- break into subarrays
- sort the first 2nd, 3rd, then 4th values,
- takes one value (element) & inserts it into a sorted array
// index.js
for(i from 1 to arr.length){
j=i-1
while(j>=0 and arr[j+1] < arr[j]) {
tmp=arr[j+1]
arr[j+1]=arr[j]
arr[j]=temp
j-=1
} // O(n2)
- recursive algorithm where we break it into 2 steps
- divide & conquer
// index.js
int[] mergeSort(int[]arr, int s, int e){
if (e-s+1<=1)
return arr;
m=(s+e)/2;
mergeSort(arr,s,m);
mergeSort(arr,m+1,e);
merge(arr,s,e);
return arr;
}
- partition the array with the pivot value (usually the right most value at the end)
- similar to Merge Sort
- everything less than or equal to the pivot will be on the Left partition of the array
-
- everything greater than or equal to the pivot will be on the Right partition of the array
// index.js
int[] quickSort(int[]arr, int s, int e){
if (e-s+1<=1)
return arr;
// Partion: elements smaller than pivot on left side
for i from s to e {
if(arr[i]<pivot) {
tmp=arr[left]
arr[left]=arr[i]
arr[i]=temp
left+=1
}
// Move pivot in-between left & right sides
arr[e]=arr[left]
arr[left]=pivot
quickSort(arr,s,left-1);
quickSort(arr,s,left+1, e);
return arr;
}
- Can only do if the array is in some sort of sorted order 1.3.3.4.5.6.7.8
- 3 options: target is on left, right, side
- Parent/Child Sibling Nodes Root Leaf-Nodes
// suedocode
function binarySearch(arr, target){
L,R = 0.len(arr) - 1
while L <= R {
mid = (L + R) //2
if target > arr[mid]
L = mid + 1
else if target < arr[mid]
R = mid - 1
else
return mid
}
}
- Can only do if the array is in some sort of sorted order 1.3.3.4.5.6.7.8
- options: target is on left, right, side
- Parent/Child Sibling Nodes Root Leaf-Nodes 4. 4. SubTree: everything in the Left SubTree has to be less than the root value and
- SubTree: Every singl node in the Right SubTree has to be greater than the root value
- Has a Sorted Property similiar like ones for arrays
// suedocode python
def search(root, target):
if not root:
return False
if target > root.val:
return search(root.right, target)
elif target < root.val:
return search(root.left, target
else:
return True
- Right Leaf node < Root
- Left Leaf node > Root
// index.js
def search(root, target):
if not root:
return False
if target > root.val:
return search(root.right, target)
elif target < root.val:
return search(root.left, target)
else:
retrun True
- Find the minimuim of the Tree
- Case 1: 0 or 1 child
- Case 2: 2 children
// index.js
def minValueNode(root):
curr = root
while curr and curr.left:
curr = curr.left
return curr
def remove(root, val):
if not root:
return None
if val > root.val:
root.right = remove(root.right, val)
elif val < root.val:
root.left = remove(root.left, val)
else:
if not root.left:
return root.right
elif not root.right:
return root.left
else:
minNode = minValueNode(root.right)
root.val = minNode.val
root.right = remove(root.right, minNode.val
return root
}
- Can only do if the array is in some sort of sorted order 1.3.3.4.5.6.7.8
- 3 options: target is on left, right, side
- O(log n) where n is the range of numbers
# binary search on some range of values
def binarySearch(low, high){
while low <= high:
mid = (low + high) //2
if isCorrect(mid) > 0:
high = mid - 1
elif if isCorrect(mid) < 0:
low = mid + 1
else:
return mid
return - 1
# Return 1 if n is too big, -1 if too small, 0 if correct
def isCorrect(n):
if n > 10:
return 1
elif n < 10:
return -1
else:
return 0
- Right Leaf node < Root
- Left Leaf node > Root
- Go down Left then down the Right nodes like an array
def inorder(root):
if not root:
return
inorder(root.left)
print(root.val)
inorder(root.right)
def preorder(root):
if not root:
return
print(root.val)
preorder(root.left)
preorder(root.right)
def postorder(root):
if not root:
return
postorder(root.left)
postorder(root.right)
print(root.val)
- Go level by level top to bottom and search at the closest nodes (getting to the breadth insead of debth)
- Use a deque (deck) which means double ended queue (FIFO)
- O(n)
from collections import deque
def bfs(root):
queue = deque()
if root:
queue.append(root)
level = 0
while len(queue) > 0;
print("level: ", level):
for i in range(len(queue)):
curr = queue.popleft()
print(curr.val)
if curr.left:
queue.append(curr.left)
if curr.right:
queue.append(curr.right)
level += 1
1.[1, 3, 5] each one of them are stored in the RAM in terms of bytes, which gets converted to bits 2. commonly occupy 4 bytes (32 bits) in memory. 3. An address and a value gets associated with an integer upon storing it in RAM 4. RAM can access any integer at any address in a continuous Random Access Memory O(1) 5. Random Access Memory = continuous block of data, Byte = 8 bits,
// index.js
function array(){
}
- insert continuous O(1)
- order of the value does matter
- shift the 6, then the 5, add 4 before the 6&5
- r/w i-th element O(1)
- Insert/Remove End O(1)
- Insert Middle O(n)
- Remove Middle O(n)
- R/W/Remove = O(1) constant time
- of Fixed Size
// index.js
function array(){
}
- ListNode - val - next
- An object (ListNode) that encapsulates two things: Value, Next (pointer)
- [] ---> [] ---> []
curr = ListNode1
while(curr != null)
curr = curr.next
tail.next = ListNode3
tail = ListNode3
// or: tail = tail.next O(1)
// moves tails to the end
head.next = head.next.next
// deleting a node: O(n) if have to search for the element
// deletes the 3rd node
// moves head to the 3rd
- ListNode - prev - val - next
- 1st and last node is set to null
- Doubly LL has edges pointing to and from
- [] ---> <--- [] ---> <--- []
tail.next = ListNode4
ListNode4.prev = tail
tail = tail.next
// adding a new node (ListNode4) and setting the tail to ListNode4 moving it from ListNode3
- One-Branch, n factorial
// index.js
n! = n * (n-1) * (n-2)* ...*1
5! = 5 * 4 * 3 * 2 * 1
5! = 5*4!
n! - n *(n-1)!
// index.js
int factorial(int n){
if(n<=1){ //base case
return 1;
}
return n*factorial(n-1)
}
- fibonacci Number: F(n)=F(n-1)+F(n-2)
- F(0)=0, F(1)=1 //base case
- O(1)
// index.js
int fib(int n) {
if(n<=1) { // base case
return n;
}
return fib(n-1)+fib(n-2)
}
- FIFO - Fist In First Out
- Enque, Deque
- ex. shopping line
// index.js
int fib(int n) {
if(n<=1) { // base case
return n;
}
return fib(n-1)+fib(n-2)
}
- LIFO - Last In First Out
- Push, Pop, Peek/Top = O(1)
- ex. candy roll, set of stacked dishes
- stack is an array horizontal or vertifal
// index.js
int (int n) {
}