Check if a number is a perfect square
Given a positive number, check if it is a perfect square without using any built-in library function. A perfect square is a number that is the square of an integer.
Tag: Algorithm
Longest Alternating Subarray Problem
The Longest Alternating Subarray is a problem of finding a subarray with alternating positive and negative elements, and in which the subarray is as long as possible.
Weighted Interval Scheduling – Dynamic Programming Solution
Given a list of jobs where each job has a start and finish time, and a profit associated with it, find a maximum profit subset of non-overlapping jobs.
Activity Selection Problem using Dynamic Programming
Given a set of activities and the starting & finishing time of each activity, find the maximum number of activities that can be performed by a single person assuming that a person can only work on a single activity at a time.
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.
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.