optimistiks’s gists

optimistiks / exclusive-execution-time.js

Created November 19, 2023 21:47

We are given an integer number, n, representing the number of functions running in a single-threaded CPU, and an execution log, which is essentially a list of strings. Each string has the format {function id}:{"start" | "end"}:{timestamp}, indicating that the function with function id either started or stopped execution at the time identified by…

	export function exclusiveTime(n, events) {
	const result = Array(n).fill(0);
	const stack = [];

	for (const event of events) {
	const [id, action, time] = event.split(":");
	if (action === "start") {
	stack.push([id, action, time]);
	}
	if (action === "end") {

optimistiks / valid-parentheses.js

Created November 22, 2023 14:49

Given a string that may consist of opening and closing parentheses, your task is to check whether or not the string contains valid parenthesization.

	function isValid(s) {
	const stack = [];

	const open = ["(", "[", "{"];
	const closing = [")", "]", "}"];

	for (const char of s) {
	const index = closing.indexOf(char);
	if (index !== -1 && stack[stack.length - 1] === open[index]) {
	stack.pop();

optimistiks / network-delay-time.js

Created November 28, 2023 20:05

A network of n nodes labeled 1 to n is provided along with a list of travel times for directed edges represented as times[i]=(x i , y i , t i ) , where x i is the source node, y i is the target node, and t i is the delay time from the source node to the target node. Considering we have a starting node, k, we have to determine…

	function networkDelayTime(times, n, k) {
	// times[i] = (xi, yi, ti)
	// k - starting node
	// n = total nodes
	// so we need an adj list
	// a priority queue
	// a visited set
	// and a result variable

	// build an adjacency list from the times array

optimistiks / paths-in-maze.js

Last active November 30, 2023 21:51

You are given a 2D integer array, corridors, where corridors[i]=[room1,room2] indicates that there is a corridor connecting room1 and room2, allowing a person in the maze to go from room1 to room2 and vice versa. The confusion score of the maze is the number of different cycles of length 3. Return the confusion score of the maze.

	function numberOfPaths(n, corridors) {
	// n rooms
	// corridors[i]=[room1,room2] meaning corridor between room1 and room2

	// find confusion score of the maze
	// confusion score = how many different cycles of length
	// 1-2-3-1 is a cycle of length 3
	// if one or more rooms is different in another cycle, it's a different cycle

	let cycles = 0;

optimistiks / graph-valid-tree.js

Created December 2, 2023 15:51

Given n as the number of nodes and an array of the edges of a graph, find out if the graph is a valid tree. The nodes of the graph are labeled from 0 to n−1, and edges[i]=[x,y] represents an undirected edge connecting the nodes x and y of the graph. A graph is a valid tree when all the nodes are connected and there is no cycle between them.

	function validTree(n, edges) {
	// nodes from 0 to n-1
	// edges[i] = [x,y] edge between node x and node y
	// determine if graph is a valid tree (no cycles, no detached nodes)

	// this condition catches all cases when there are cycles (additional edges)
	if (edges.length !== n - 1) {
	return false;
	}

optimistiks / bus-routes.js

Created December 2, 2023 16:59

You are given an array, routes, representing bus routes where routes[i] is a bus route that the i th bus repeats forever. Every route contains one or more stations. You have also been given the source station, src, and a destination station, dest. Return the minimum number of buses someone must take to travel from src to dest, or return -1 if th…

	function minimumBuses(matrix, s, d) {
	// at first we create an adj list,
	// where keys are stops
	// and values are array of buses visiting that stop

	// then we have a queue to run bfs
	// since bfs always finds shortest path in an unweighted graph
	// we add a tuple [stop, buses] to the queue
	// where buses is the number of different buses we took to reach the stop
	// initially buses is 0 since it's a starting stop

optimistiks / flatten-binary-tree.js

Created December 5, 2023 20:51

Given the root of a binary tree, the task is to flatten the tree into a linked list using the same TreeNode class. The left child pointer of each node in the linked list should always be NULL, and the right child pointer should point to the next node in the linked list. The nodes in the linked list should be in the same order as that of the preo…

	// Definition of a binary tree node
	// class TreeNode {
	// constructor(data) {
	// this.data = data;
	// this.left = null;
	// this.right = null;
	// }
	// }

	export function flattenTree(root) {

optimistiks / diameter-binary-tree.js

Created December 7, 2023 19:14

Given a binary tree, you need to compute the length of the tree’s diameter. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

	import { TreeNode } from "./ds_v1/BinaryTree.js";
	// Definition of a binary tree node
	// class TreeNode {
	// constructor(data) {
	// this.data = data;
	// this.left = null;
	// this.right = null;
	// }
	// }

optimistiks / binary-tree-max-path.js

Created December 10, 2023 00:33

Given the root of a binary tree, return the maximum sum of any non-empty path.

	// Definition of a binary tree node
	// class TreeNode {
	// constructor(data) {
	// this.data = data;
	// this.left = null;
	// this.right = null;
	// }
	// }

	import { TreeNode } from "./ds_v1/BinaryTree.js";

optimistiks / sorted-array-to-bst.js

Created December 10, 2023 17:25

Given an array of integers, nums, sorted in ascending order, your task is to construct a height-balanced binary search tree (BST) from this array.

	// Definition of a binary tree node
	// class TreeNode {
	// constructor(data) {
	// this.data = data;
	// this.left = null;
	// this.right = null;
	// }
	// }

	import { TreeNode } from "./ds_v1/BinaryTree.js";

Max optimistiks