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
Laravel

PhpSpreadsheet Issue With Vertical Tabs (0x0B)

This article is about fixing the following error:

Failed to load path_to_project/storage/framework/laravel-excel/laravel-excel-eTdm3TlUf1neh8QbolfXmodtigO50x3x.html as a DOM Document

Recently I caught a bug where PHP excel parser (PhpSpreadsheet) was failing when parsing some rows fetched from the database. With a series of trial and error tests, I found the row that was causing the failure.

So, I copied the sentence in Sublime Text and saw that there was a hex character (0x0b) in the sentence. This character is known as a “Vertical Space” and is visually invisible in most editors. I couldn’t see this character in Mysql Workbench so I copied the whole row in Sublime text and saw the hex representation of this character. Below are some other representations of this character:

  • 0x0b
  • “\v”

To fix the issue, I ran the following SQL query to find all sentences containing this character and then removed them from the database:

SELECT text FROM messages WHERE text LIKE CONCAT('%',0x0b,'%');

It’s a good practice to filter your inputs and make sure you’re not storing unwanted characters like these in the database, they might bite you one day!

Categories
Laravel

How to Get All Redis Cache Keys in Laravel

TL;DR:

Cache::getRedis()->keys("*")

If you’ve set up your Laravel application with Redis and you want to see all the keys registered in your Redis, simply open Laravel Tinker using the following command:

php artisan tinker

And then run the following code snippet to get all the keys available in your redis:

Cache::getRedis()->keys("*")
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("");
}