Depth-First Search (DFS) vs Breadth-First Search (BFS)
This post will cover the difference between the Depth–first search (DFS) and Breadth–first search (BFS) algorithm used to traverse/search tree or graph data structure.
Tag: Algorithm
Maximum Overlapping Intervals Problem
Consider an event where a log register is maintained containing the guest’s arrival and departure times. Given an array of arrival and departure times from entries in the log register, find the point when there were maximum guests present in the event.
Young Tableau | Insert, Search, Extract-Min, Delete, Replace
An M × N Young tableau is an M × N matrix such that the entries of each row are sorted from left to right and the entries of each column are sorted from top to bottom. Some entries of a Young tableau may be infinity, which indicates an empty entry.
Weighted Interval Scheduling Problem
Given a list of jobs where each job has a start and finish time, and has profit associated with it, find a maximum profit subset of non-overlapping jobs.
Box Stacking Problem
Given a set of rectangular 3D boxes (cuboids), create a stack of boxes as tall as possible and return the maximum height of the stacked boxes.
Unbounded Binary Search
Given a monotonically increasing function f(x) on the non-negative integers, find the value of x, where f(x) becomes positive for the first time. In other words, find a positive integer x such that f(x-1), f(x-2), … are negative and f(x+1), f(x+2), … are positive.
Longest Common Prefix (LCP) Problem
Write an efficient algorithm to find the longest common prefix (LCP) between a given set of strings.
Pots of Gold Game Problem using Dynamic Programming
There are two players, A & B, in the Pots of the gold game, and pots of gold arranged in a line, each containing some gold coins. The players can see how many coins are there in each gold pot, and each player gets alternating turns in which the player can pick a pot from one of the ends of the line.
Kahn’s Topological Sort Algorithm
Given a directed acyclic graph (DAG), print it in Topological order using Kahn’s topological sort algorithm. If the DAG has more than one topological ordering, print any of them.
Maximum Length Snake Sequence
Given a square matrix, print the maximum length snake sequence in it. A snake sequence is defined as a sequence of numbers where each new number, which can only be located to the right or down of the current number, is either plus or minus one.
K–Partition Problem | Printing all partitions
In the k–partition problem, we need to partition an array of positive integers into k disjoint subsets that all have an equal sum, and they completely cover the set.
3–Partition Problem
Given a set S of positive integers, determine if it can be partitioned into three disjoint subsets that all have the same sum, and they cover S.