Categories
Algorithms Javascript

Longest Common Substring in JS

Use the following javascript code to find the longest substring (unconnected) among two strings:

const minDistance = function (text1, text2) {
	const m = text1.length,
		n = text2.length,
		dp = new Array(m + 1).fill().map((v) => new Array(n + 1).fill(0));
	for (let i = 1; i <= m; i++)
		for (let j = 1; j <= n; j++)
			if (text1[i - 1] == text2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
			else dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);

	return m + n - 2 * dp[m][n];
};
Categories
Algorithms Javascript

Dijkstra Algorithm in JS

const networkDelayTime = function (times, n, src) {
	const adjacencyList = new Map();

	for (let [start, end, cost] of times) {
		adjacencyList.set(
			start,
			(adjacencyList.get(start) || []).concat([[end, cost]])
		);
	}
	const queue = new MinPriorityQueue({
		compare: (a, b) => a[0] > b[0],
	});
	queue.enqueue([0, src]); // cost, start
	const visited = new Map();
	while (queue.size()) {
		const [cost, node] = queue.dequeue();
		if (visited.has(node)) continue;
		visited.set(node, cost);
		// if (city === dst) return cost;
		if (!adjacencyList.has(node)) continue;
		for (const [nextNode, nextCost] of adjacencyList.get(node)) {
			if (visited.has(nextNode) || visited.get(nextNode) >= cost)
				continue;
			queue.enqueue([cost + nextCost, nextNode]);
		}
	}
	return visited.size == n ? Math.max(...visited.values()) : -1;
};

T: O(N+ElogN)

S: O(N+E)

Categories
Algorithms Javascript

BST Iterative Preorder Traversal in JS

function preorder(root) {
	const stack = [];
	while (stack.length || root) {
		while (root) {
			stack.push(root);
			root = root.left;
		}
		root = stack.pop();
		console.log(root.val);
		root = root.right;
	}
};
Categories
Algorithms Javascript

Topological Sort in JS

Imagine you have a list of dependencies and prerequisites that form a graph. You can use topological sort graph algorithm in order to validate meeting all the requirements. Here is a BFS implementation of this algorithm in Javascript:

const canFinish = function (numCourses, prerequisites) {
	const rank = new Array(numCourses).fill(0),
		// rank["C" => 0, "OOP" = 1, "DS" = 1] -> how many dependencies
		dependent = new Array(numCourses).fill().map((v) => []);
		// dependent["C"] = ["OOP", "DS"];
	for (const [a, b] of prerequisites) {
		rank[a]++;
		dependent[b].push(a);
	}
	const queue = [];
	for (const i in rank) if (rank[i] == 0) queue.push(i);
	while (queue.length) {
		const node = queue.shift();
		for (const neighbour of dependent[node]) {
			rank[neighbour]--;
			if (rank[neighbour] == 0) queue.push(neighbour);
		}
	}
	return rank.every((v) => !Boolean(v));
};
Categories
Javascript

How to Implement a Graph Class in Javascript

The following code snippet shows an implementation of a Graph in JS

class Graph {
	verticies = {};

	add(vertix, adjacencies) {
		if (!this.verticies[vertix]) this.verticies[vertix] = new Set();

		for (const adjacent of adjacencies) {
			if (vertix == adjacent) continue;
			if (!this.verticies[adjacent]) this.verticies[adjacent] = new Set();
			this.verticies[vertix].add(adjacent);
			this.verticies[adjacent].add(vertix);
		}
	}
}
Categories
Algorithms Javascript

Union Find in JS

Union Find is an algorithm that can be used to find disjoint sets, and cycles in a graph. Below are two implementations of this algorithm.

  1. Un-optimized
class UnionFind {
	// Time Complexity: find: O(n), union: O(n)
	constructor(n) {
		this.n = n;
		this.root = new Array(n).fill().map((v, i) => i);
	}
	find(node) {
		if (this.root[node] == node) return node;
		return (this.root[node] = this.find(this.root[node]));
	}
	union(a, b) {
		const u = this.find(a),
			v = this.find(b);
		if (u == v) return false; // Cycle
		this.root[u] = v;
	}
	disjointSets() {
		const set = new Set();
		for (let i = 0; i < this.n; i++) set.add(this.find(i));
		return set.size;
	}
}

2. Optimized (Ranked)

class UnionFind {
	// Time Complexity: find: O(n), union: O(n)
	constructor(n) {
		this.n = n;
		this.root = new Array(n).fill().map((v, i) => i);
		this.rank = new Array(n).fill(1);
	}
	find(node) {
		if (this.root[node] == node) return node;
		return (this.root[node] = this.find(this.root[node]));
	}
	union(a, b) {
		const u = this.find(a),
			v = this.find(b);
		if (u == v) return false;
		if (this.rank[u] > this.rank[v]) {
			this.root[v] = u;
			this.rank[u] += this.rank[v];
		} else {
			this.root[u] = v;
			this.rank[v] += this.rank[u];
		}
		return true;
	}
	disjointSets() {
		const set = new Set();
		for (let i = 0; i < this.n; i++) set.add(this.find(i));
		return set.size;
	}
}

Categories
Javascript Laravel

Change DB Connection at Runtime in Laravel

\Config::set("database.connections.mysql", [
    "host" => "your-host.com",
    "driver" => "mysql",
    "database" => 'database-name',
    "username" => "username",
    "password" => "password",
]);
\DB::purge('mysql');
Categories
Coding Exercises

Rotational Cipher Solution – Meta Careers Coding Exercise

Following is my solution to Meta’s Coding Exercise: Rotation Cipher.

function rotationalCipher(input, rotationFactor) {
	let str = input.split("");
	const a_code = "a".charCodeAt(0),
		z_code = "z".charCodeAt(0),
		A_code = "A".charCodeAt(0),
		Z_code = "Z".charCodeAt(0),
		zero_code = "0".charCodeAt(0),
		nine_code = "9".charCodeAt(0);
	for (let i = 0; i < str.length; i++) {
		const char = str[i];
		const code = char.charCodeAt(0);
		if (
			(a_code <= code && code <= z_code) ||
			(A_code <= code && code <= Z_code) ||
			(zero_code <= code && code <= nine_code)
		) {
			let newCode;
			if (isNaN(char)) {
				if (char === char.toLowerCase()) {
					// Rotate lower case letters
					newCode = code - a_code + rotationFactor;
					newCode %= 26;
					newCode += a_code;
				} else {
					// Rotate upper case letters
					newCode = code - A_code + rotationFactor;
					newCode %= 26;
					newCode += A_code;
				}
			} else {
				// Rotate numbers
				newCode = code - zero_code + rotationFactor;
				newCode %= 10;
				newCode += zero_code;
			}
			str[i] = String.fromCharCode(newCode);
		}
	}
	return str.join("");
}
Categories
Javascript

4 Ways To Check If A Variable Is A Number In JS + Comparison

Comparison Table

Case/^\d+$/
.test(variable)
/^[0-9]+$/
.test(variable)
!isNaN
(variable)
typeof
variable
“123”TrueTrueTruestring
” “FalseFalseTruestring
123TrueTrueTruenumber
“1.23”FalseFalseTruestring
1.23FalseFalseTruenumber
“abc”FalseFalseFalsestring
Comparison of Different Methods to Find Out if a Variable Is a Number in JS