Collatz Conjecture – Maximum Steps takes to transform (1, N) to 1.

Objective: Given a number N, write an algorithm to find the maximum number of steps it takes to transform (1, N) to 1 using Collatz Conjecture.  The Collatz conjecture is a conjecture in mathematics which states that no matter what value of Positive Number N, If the below sequence is followed then the sequence will … Read more Collatz Conjecture – Maximum Steps takes to transform (1, N) to 1.

Minimum No of operations required to convert a given number to 1 – Integer Replacement Problem.

Objective: Given a number N, write an algorithm to convert that number to 1. Below are the allowed operations. If N is even, do N = N/2. If N is odd, either do N =N – 1 or do N = N + 1 Example:  N = 16 Output: 4 16 → 8 → 4 … Read more Minimum No of operations required to convert a given number to 1 – Integer Replacement Problem.

Dynamic Programming – Egg Dropping Problem

Objec­tive:  There are n number of eggs and building which has k floors. Write an algorithm to find the minimum number of drops is required to know the floor from which if the egg is dropped, it will break. Note: One trial is – dropping an egg once from the particular floor. If egg does not … Read more Dynamic Programming – Egg Dropping Problem

Dynamic programming – Printer Problem

Objective:  Given a printer which can perform only 2 operations- Printer can print consecutive identical characters in one go. It can replace consecutive characters by consecutive identical characters at any position. You are given a string input with some characters. Write an algorithm to find the minimum number of printer operations required to print the input … Read more Dynamic programming – Printer Problem

Dynamic programming – Minimum Jumps to reach to end

Objective:  Given an array of non negative integers, start from the first element and reach the last by jumping. The jump length can be at most the value at the current position in the array. Optimum result is when you reach the goal in minimum number of jumps. Example: Given array A = {2,3,1,1,4} possible ways … Read more Dynamic programming – Minimum Jumps to reach to end

Dynamic programming – Remove Boxes Problem

Objec­tive:  Given a number of boxes with different colors represented by different positive numbers. You need to remove all the boxes in several rounds, each time you can choose continuous boxes with the same color (means with same numbers, composed of k boxes, k >= 1), remove them and get k*k points. Write an algorithm to get the maximum … Read more Dynamic programming – Remove Boxes Problem

Stock Single Sell Problem – O(n) Solution

Objec­tive:  Given an array represents cost of a stock on each day. You are allowed to buy and sell the stock only once. Write an algorithm to maximize the profit in single buy and sell. Exam­ple: int[] prices = {200, 500, 1000, 700, 30, 400, 900, 400, 50}; Output: Maximum Profit: 870, buy date index: 4, … Read more Stock Single Sell Problem – O(n) Solution

Maximum difference between two elements where larger element appears after the smaller element

Objective: Given an array A[], write an algorithm to find Maximum difference between two elements where larger element appears after the smaller element or in other words find A[i] and A[j] such that A[j]-A[i] is maximum where j > i. Example: int [] A = { 2, 5, 1, 7, 3, 9, 5}; Maximum Difference … Read more Maximum difference between two elements where larger element appears after the smaller element

Find longest Snake sequence in a given matrix

Objective: Given two dimensional matrix, write an algorithm to find out the snake sequence which has the maximum length. There could be many snake sequence in the matrix, you need to return the one with the maximum length. Travel is allowed only in two directions, either go right OR go down. What is snake sequence: … Read more Find longest Snake sequence in a given matrix

Dynamic Programming – Count all paths in 2D Matrix with Obstructions in it

Objective: Given two dimensional matrix, write an algorithm to count all possible paths from top left corner to bottom-right corner. You are allowed to move only in two directions, move right OR move down. There are few obstructions as well, means few cells are blocked and you cannot travel that cell.

Many times this problem is being referred as “Robot Travel Problem“. Given a 2d matrix, how many ways a robot can travel from top left corner to bottom right corner and there are few cells in which robot cannot travel.

Read moreDynamic Programming – Count all paths in 2D Matrix with Obstructions in it

Dynamic Programming – Count all paths from top left to bottom right of a mXn matrix

Objective: Given two dimensional matrix, write an algorithm to count all possible paths from top left corner to bottom-right corner. You are allowed to move only in two directions, move right OR move down. Example: Approach: Recursion- Earlier we have seen “Print All Paths from Top left to bottom right in Two Dimensional Array“. Current … Read more Dynamic Programming – Count all paths from top left to bottom right of a mXn matrix

Dynamic Programming – Edit Distance Problem

Objective: Given two strings, s1 and s2 and edit operations (given below). Write an algorithm to find minimum number operations required to convert string s1 into s2. Allowed Operations: Insertion – Insert a new character. Deletion – Delete a character. Replace – Replace one character by another. Example: String s1 = “horizon” String  s2 = … Read more Dynamic Programming – Edit Distance Problem

Dynamic Programming – Coin In a Line Game Problem

Objective: In this game, which we will call the coins-in-a-line game, an even number, n, of coins, of various denominations from various countries, are placed in a line. Two players, who we will call Alice and Bob, take turns removing one of the coins from either end of the remaining line of coins. That is, … Read more Dynamic Programming – Coin In a Line Game Problem

Dynamic Programming – Box Stacking Problem

Objective: You are given a set of n types of rectangular 3-D boxes, where the i^th box has height h(i), width w(i) and depth d(i) (all real numbers). You want to create a stack of boxes which is as tall as possible, but you can only stack a box on top of another box if … Read more Dynamic Programming – Box Stacking Problem

Dynamic Programming – Highway Billboard Problem

Objective:  Suppose you’re managing construction of billboards on the Rocky & Bullwinkle Memorial Highway, a heavily traveled stretch of road that runs west-east for M miles. The possible sites for billboards are given by numbers x1 < x2 < · · · < xn, each in the interval [0, M], specifying their position in miles … Read more Dynamic Programming – Highway Billboard Problem