Algorithms notes
- Implement binary search in js without recursion
- implement quick sort in py and js
- implement merge sort in js
for queues, you dequeue from 0 and enqueue at -1
- binary search
- time
- worst case: O(log n)
- average case: O(log n)
- best case: O(1)
- space
- O(1)
- works only on sorted arrays
- divide in two
- if even length, default to the left side, so you get the worst case performance?
- obviously the worst case is not O(n * log n) because we can just look through the whole array and that is just n
- For binary search to get the worst case on even length arrays always use the left side.
- So 1 2 3 4
- Compare to 2, not 3
- time
- bubble sort
- bubble up the biggest number to the end on each iteration
- time
- worst case: O(n^2) comparisons, O(n^2) swaps
- average case: O(n^2), O(n^2)
- best case: O(n), O(1)
- space
- O(1)
- merge sort
- divide and conquer
- if you have odd number of arrays, put the odd one at the beginning
- time
- worst case: O(n * log n)
- best case: O(n * log n),
- average case: O (n * log n)
- space
- O(n * log N)
- merge sort is stable, so it won't reorder elements that are equal
js tips
- array slice vs array splice
- array splice removes/replaces elements at index
- array.splice(start, deleteCount, ...items)
- modifies in place
- returns deleted elements
- [1,2,3].splice(1) => [2,3]
- array slice returns a shallow copy of an array with elements from begin to end
- array.slice(begin, end)
- end is not inclusive
- e.g [1, 2, 3, 4].slice(1, 3) => [2, 3]
- array splice removes/replaces elements at index
- array equality
- [2, 3] !== [2, 3]
- not the same reference
- need to deep compare
- rest
- rest puts rest of arguments into an array
- spread expands an array or object into multiple elements
- currying
- takes a function with multiple args and turns into multiple functions that individually take some of the args
- apply vs call
- apply calls function with this + arguments as an array
- call calls function with this + argument list
- charAt
- charAt(i) character at index in string
- array.shift() vs array.pop()
- array.shift removes the element at the front of the array and returns that element. it updates the array in place. it undoes a unshift, which puts an element at the beginning of a list.
- array.pop removes the element at the end of the array and returns that element. it updates the array in place. its undoes a push, which puts an element on the end of the list.
- array.concat vs append to an array in place
- array.concat returns a new array
- array.push.apply(array, list)
- new Array(5).map((_,i) => i)
- returns [empty x 5]
- instead of the expected [0,12,3,4]
- to fix
- new Array(5).fill().map((_,i) => i)
css tips
- ul + p selects a p that comes immediately after a ul. ul and p must be siblings.
- ul ~ p selects all the p's that come after ul.
trees
- tree must be completely connected
- no cycles in tree
- level = # of rows from top, starts at 1
- height = # of edges between a node and the furthest leaf on the tree
- depth = # of edges from a node to the root, inverse of height
- traversal
- bfs
- dfs
- can do all of these with recursion, just change order of ops
- pre-order
- start at the top, and descend to the left most child
- check nodes off as you go
- root, left, right
- in-order
- go left to right visually
- go to the left most child, check it, then check its parent
- left, root, right
- post-order
- go to left most child, then its sibling, then its parent
- left, right, root
- binary trees
- parents have at most two children
- search: O(n)
- delete: O(n)
- insert: O(log n)
- delete node from binary tree
- if you delete a leaf, simply delete it
- if you delete a node with one child, simply promote the child
- if a node has two children, promote the one with no children
- if a node has two children with children, search until you find a leaf and then promote it to the parent position, since theres no order requirement
- insert node
- just need to find a node that has 1 spot for a child
- in the worst case we have to traverse to the full height of the tree
- what is the height of a binary tree?
- log n
- 2^level = number of nodes in a tree on that level
- row 1 = 1
- 2 = 2
- 3 = 4
- 4 = 8
- Here is a helpful tip to quickly prove the correctness of your binary search algorithm during an interview. We just need to test an input of size 2. Check if it reduces the search space to a single element (which must be the answer) for both of the scenarios above. If not, your algorithm will never terminate.
- depth
- function depth(node) { - if (!node) { - return 0; - } - - return Math.max(depth(node.left), depth(node.right)) + 1; - }
- mid - mid = left + (right - left) / 2 - to avoid overflow
graphs
- node degree
- how many other nodes a node is connected to
- adjacency list
- list of lists where the index corresponds to the id of a node
- each sublist contains the adjacent ids
- [ [1] [ 1 2 3] ... ]
- good for answering node degree
- adjacency matrix
- 2d array of which nodes are adjacent to eachother
- [ [ 1 0 0 1] [ 0 0 1 0] ... ]
case studies
- shortest path
- unweighted graph: bfs
- weighted graph: djikstras algorithm
- worst case: O( |v|^2 )
- we have to visit every vertex and we have to search through the queue every time we visit the vertex
- with an optimized prority queue: O( |E| + |V| * log(|V}) )
- algorithm
- make a list of the vertices
- assign weight infinity to all the verticies
- assign weight of 0 to the starting vertex
- start at the start node and assign the weight of edges to the adjacent vertices
- choose the next min weight vertex
- assign weight cost to its adjacent vertices, and record in the array if its less than the existing value. be sure to stack the cost to get to the starting vertex
- repeat
- called greedy because of the min priority queue, it chooses the cheapest choice at the current time
- worst case: O( |v|^2 )
- knapsack problem
- might be tempted to put in the biggest items first, but that isn't always the right answer
- one solution is to brute force and try every combination
- this is O(2^n) exponential, aka not polynomial
- algorithm
- my mistake: maximize value for the largest weight possible
- better choice: maximize value for the smallest weight possible. then keep adding them together until we reach the max weight.
- can solve with dynamic programming / lookup table
- with dynamic programming the main question is what are the subproblems?
- we can shrink the original problem in two ways
- we can solve with a smaller set of items to put in the knapsack
- or we can solve with a smaller knapsack weight
- we can shrink the original problem in two ways
- algorithm: with repetition
- K(w) = maximum achievable value with a capacity of w
K(w) = K(w - w_i) + v_i- make an array with length W, set everything to 0
-
def binary_search(input_array, value):
total_index = 0
while True:
index = len(input_array) / 2
if input_array[index] == value:
return index + total_index
if len(input_array) <= 1:
return -1
if input_array[index] < value:
total_index += index+1
input_array = input_array[index+1:]
else:
input_array = input_array[:index]
return -1
def binary_search(input_array, value):
low = 0
high = len(input_array) - 1
while low <= high: # 4 <= 3
mid = ((high - low) / 2) + low # 4-4/2 + 4 4
if input_array[mid] == value: # 15 == 13?
return mid
if input_array[mid] < value: # 15 < 13?
low = mid + 1
else:
high = mid - 1 # high = 3
return -1
test_list = [1,3,9,11,15,19,29]
function binarySearch(inputArr, value, size) {
const mid = Math.floor(inputArr.length / 2);
if (inputArr[mid] === value) {
return mid + size;
}
if (inputArr.length === 1) {
return -1;
}
if (value > inputArr[mid]) {
return binarySearch(inputArr.slice(mid + 1), value, size + mid);
}
return binarySearch(inputArr.slice(0, mid), value, size);
}
function bubbleSort(arr) {
var swaps;
while (true) {
swaps = 0;
for (var i = 0; i < arr.length - 1; i++) {
var cur = arr[i];
var next = arr[i+1];
if (cur > next) {
arr[i] = next;
arr[i+1] = cur;
swaps += 1;
}
}
if (swaps === 0) {
return arr;
}
}
}
def get_fib(position):
if position == 0 or position == 1:
return position
return get_fib(position - 1) + get_fib(position - 2)
function curry(func, ...argv) {
let prevArgs = argv;
function innerCurry(...args) {
prevArgs.push(...args)
if (prevArgs.length === func.length) {
return func(...prevArgs);
}
return innerCurry;
}
return innerCurry;
}
function add1(a) {
return a + 1;
}
function add(a, b, c, d) {
return a + b + c + d;
}
function concat(a, b, c) {
return `${a} ${b} ${c}`;
}
function hi() {
return 'hi';
}
console.log(curry(add)(1)(4, 2)(3))
console.log(curry(concat)('a', null)()(null))
console.log(curry(hi)())
// knapsack problem with repetition
function budgetShopping(n, bundleQuantities, bundleCosts) {
var K = new Array(n + 1).fill(0);
for (var i = 1; i < K.length; i++) {
for (var j = 0; j < bundleQuantities.length; j++) {
const quant = bundleQuantities[j];
const cost = bundleCosts[j];
if (cost <= i) {
K[i] = Math.max( K[i], K[i-cost] + quant);
}
}
}
return K[n];
}
console.log(budgetShopping(50, [20, 11, 2], [11, 8, 3]))
function knapsackWithoutRepetition(W, weights, values) {
const N = values.length;
const K = [];
for (var w = 0; w < W + 1; w++) {
K[w] = new Array(N+1);
K[w][0] = 0;
}
K[0].fill(0);
for (var n = 1; n < N + 1; n++) {
for (var w = 1; w < W + 1; w++) {
if (weights[n-1] <= w) {
K[w][n] = Math.max(
K[w][n-1],
K[w - weights[n-1]][n-1] + values[n-1],
);
}
else {
K[w][n] = K[w][n-1];
}
}
}
return K[W][N];
}
console.log(knapsackWithoutRepetition(10, [6, 3, 4, 2], [30, 14, 16, 9]))