Approach to solve subarray problems in a single pass and constant space. The number of subarrays of an array with at least one element is N*(N + 1)/2. So if we have a problem where we need to check all subarrays for max, min, etc, we can use Kadane’s Algorithm…

Kruskal’s Algorithm | Prim’s Algorithm The Minimum Spanning Tree (MST) of an undirected graph is a Tree such that the sum of all edge weights of the tree is minimum. There are two ways to implement MST namely Kruskal’s & Prim’s Algorithms. Kruskal’s Algorithm Steps Sort all the edges of the graph from…

BFS and DFS implementation — The topological sort of a DAG is the partial linear ordering of its nodes such that if that graph has an edge directed from u to v, u should be placed in the ordering before v. Partial ordering is very useful in many situations. Scheduling problems, dependency resolutions. Some useful…

A Union-Find/Disjoint set data structure is used to maintain a set of elements partitioned into a number of mutually non-overlapping subsets. Disjoint Set —A disjoint set is a group of sets where no item can be in more than one set. In other words, if we take any two sets…

INNER | LEFT| RIGHT | FULL | CROSS | SEMI | ANTI JOIN is one of the most common operations/transformations in Spark. Spark SQL supports all the fundamental types of joins. In this blog, we will go through the type of joins and their value proposition. Sample table 1 +----------------+---------+----------+ |…

Central logging & monitoring solution in AWS cloud — Observability Track the overall correctness of any system. In simpler words Observability services help you with following Collect & analyze data from apps Understand their state Be alerted/notified Troubleshoot A good observability service should allow us to ingest/collect, store, search analyze, correlate, and visualize logs and traces. …

Travel back in time to see the table state as it was at that time. I want to go back in time. Not to change anything, but to feel something again. — Mercer Snowflake Time Travel is an interesting tool that allows us to access historical data (data that has…

Discrete & repeated selection of item — Unlike the 0/1 Knapsack problem, in an unbounded Knapsack, we are allowed to use an unlimited number of instances of an item. Given a knapsack weight A and a set of items with a certain value B[i] and weight C[i], we need to calculate the maximum amount that could fit…

Putting discrete items in bags to maximize profit — The Knapsack problem is a combinatorics optimization problem. To solve this kind of problem we can follow the following: General strategy: Find base case Find recurrence relation Reuse computed values Write the bottom-up iterative solution Given the weights, w, and profits p of ’N’ items, need to find a subset of these…