Skip to content

Instantly share code, notes, and snippets.

@hell0-world
Last active September 9, 2021 10:59
Show Gist options
  • Save hell0-world/baee34e4ee93620b81b2274d19beba21 to your computer and use it in GitHub Desktop.
Save hell0-world/baee34e4ee93620b81b2274d19beba21 to your computer and use it in GitHub Desktop.
Basic algorithms in JS
// GCD
// Euclidean algorithm
const gcd = (a,b) => {
if(!b) return a;
return gcd(b, a%b);
}
// LCM
// USING GCD
const lcm = (a,b) =>{
return (a*b)/gcd(a,b);
}
// Power Set
// Bitwise Solution
const powerSet = (arr) => {
const number = 2 ** arr.length;
const subsets = [];
for (let combIndex = 0; combIndex < number; combIndex++) {
const subset = [];
for (let elIndex = 0; elIndex < arr.length; elIndex++) {
if (combIndex & (1 << elIndex)) {
subset.push(arr[elIndex]);
}
}
subsets.push(subset);
}
return subsets;
};
// BackTracking Recursive
function btPowerSetRecursive(originalSet, allSubsets = [[]], currentSubSet = [], startAt = 0){
for (let position = startAt; position < originalSet.length; position += 1) {
currentSubSet.push(originalSet[position]);
allSubsets.push([...currentSubSet]);
btPowerSetRecursive(originalSet, allSubsets, currentSubSet, position + 1);
currentSubSet.pop();
}
return allSubsets;
}
// Binary Search
// sorted array, target to find
// O(log n)
const binarySearch = (arr, target) => {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = left + ~~((right - left) * 0.5);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1; //not found
};
// Min Heap, Priority Queue
class Heap {
constructor() {
this.heap = [];
}
getLeftChildIndex = parentIndex => parentIndex * 2 + 1;
getRightChildIndex = parentIndex => parentIndex * 2 + 2;
getParentIndex = childIndex => Math.floor((childIndex - 1) / 2);
peek = () => this.heap[0];
insert = (key, value) => {
let node = { key, value };
this.heap.push(node);
this.heapifyUp();
};
heapifyUp = () => {
let index = this.heap.length - 1;
const lastInsertedNode = this.heap[index];
while (index > 0) {
const parentIndex = this.getParentIndex(index);
if (this.heap[parentIndex].key > lastInsertedNode.key) {
this.heap[index] = this.heap[parentIndex];
index = parentIndex;
} else {
break;
}
}
this.heap[index] = lastInsertedNode;
};
remove = () => {
const count = this.heap.length;
const rootNode = this.peek();
if (count <= 0) return undefined;
else if (count === 1) this.heap = [];
else {
this.heap[0] = this.heap.pop();
this.heapifyDown();
}
return rootNode;
};
heapifyDown = () => {
let index = 0;
const count = this.heap.length;
const rootNode = this.peek();
while (this.getLeftChildIndex(index) < count) {
const leftChildIndex = this.getLeftChildIndex(index);
const rightChildIndex = this.getRightChildIndex(index);
const smallerChildIndex =
rightChildIndex < count &&
this.heap[rightChildIndex].key < this.heap[leftChildIndex].key
? rightChildIndex
: leftChildIndex;
if (this.heap[smallerChildIndex].key <= rootNode.key) {
this.heap[index] = this.heap[smallerChildIndex];
index = smallerChildIndex;
} else break;
}
this.heap[index] = rootNode;
};
}
class PriorityQueue extends Heap {
constructor() {
super();
}
enqueue = (priority, value) => this.insert(priority, value);
dequeue = () => this.remove();
isEmpty = () => this.heap.length <= 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment