[TypeScript] Debounce function in vanilla TypeScript

Debouncing is a technique to execute a function only once during a configured period while specific trigger conditions are true. This can be used to improve performance and user experience.

The idea is to track the last time the desired function was invoked, and update such timer on each subsequent invocation, resetting the timer to the new time. If no other call is made within the configured delay after the last time of invocation, the function will finally be triggered at the end of the period.

[Java] Prim algorithm to find Minimum Spanning Tree in a graph

The minimum spanning tree (MST) is a subset of all edges in a weighted, undirected, connected graph such that the resulting graph is still connected and the sum of all edge weights is minimal.

If we are not given a list of edges, but only a list of vertices and a formula to calculate the edge weight given two graph nodes, we can run a preprocessing step to generate ALL possible edges between ALL graph nodes and calculate their weight in O(V^2).

Then, starting from a random node, we greedily choose one reachable vertex which has minimal distance from the current node. We continue exploring until all graph nodes have been touched.

There might be multiple valid MSTs for a given graph, this algorithm will return one of them.

We use a queue sorted by weight to determine which edge (and therefore node) to visit next, this ensures that if a node is reachable via multiple edges, we always pick the smallest weight for it. Since the graph is fully connected, we are ensured eventually we will have picked ONE edge between each node in the graph, and the sum of weight of all the chosen edges is minimal.

This runs using O(E) space since we might add all edges to the queue and O(E log(E)) time since for each edge we add to the queue we pay the O(log(E)) cost of insert and remove operation.

If the graph was NOT connected, this will NOT return the MST, only the MST for the connected component where the chosen start node resides. We could adapt the algorithm to verify whether there are extra nodes not yet visited, and repeat the processing for each until we have created a MST for each connected component in the graph.

In case the graph is not conencted, an alternatve can also be Kruskal's algorithm.

You can find my implementation of primMinimumSpanningTree on my Gist along with some tests in PrimMSTJTests.

[Java] Graph union find algorithm

For an undirected graph, we can compute the disjointed sets that represent all connected nodes in the subgraph where each node resides.

For each set, we elect a representative, all nodes reachable in a set will have the same representative. The resulting view will be a tree where the representative sits at the root and all connected nodes are its children.

Example applications include: quickly verify whether 2 nodes in a graph have a path to each other (they must belong to same set) or calculating the minimum number of edges to add to a graph to make it fully connected (or the opposite).

It is based on 2 operations:

find(Vertex x)

which will return for a given node, the representative of its subset. We recurse up the tree where this node resides until the representative is found. We optimize the operation for future searches by including path compression, where once a representative is found, all nodes along the same path are updated to track it. This makes it so that the find operation runs in O(inverse Ackermann(V)), which is considered O(1) but more realistically is O(log(log(...(V))) or how many times we need to apply log(x) to its result starting with V until the output is less than 1. It is an extremely slowly increasing sequence.

union(Vertex x, Vertex y)

which will connect the subtree where node x resides to the subtree of node y, unless they are already part of the same subtree. To improve efficiency we track in O(V) extra space the rank of each subtree (its depth) and when merging two subtrees, we connect the one with minimum depth to the other, so the overall height of the resulting tree is kept as flat as possible.

It uses O(V) extra space, to track for each node who is the representative of its subset and O(V) to track the rank of the subtree rooted at each node.

It runs in O(V Ackermann(V)) time since we run 2 find operation for each edge (pair of nodes) we unite and use the union by rank with path compression method.

You can check my implementation of unionFind on my Gist along with some tests in UnionFindJTests.