Create all possible combinations

September 24, 2017

This was an attempt to solve SPOJ – SQRBR, but gives TLE. It explores all the options recursively, and without the use of dynamic programming. This technique can be used to generate all the combination of certain values.  Read the rest of this entry »


Mixtures – SPOJ

September 23, 2017

Given mixtures in a row. When they are mixed with each other, the result is modulus 100 of the sum. This replaces the mixing color. During mixing the process some smoke is generated (as by product), the quantity of which is the result of multiplication of two mixtures. Minimize the smoke generated when mixing two mixture. Read the rest of this entry »

Matrix Chain Multiplication (MCM)

September 23, 2017

Given the dimensions of matrices next to each other, find the best way to parenthesize (multiply the matrices) that minimized the number of multiplication. Read the rest of this entry »

Martian – SPOJ

September 19, 2017

Given a grid that contains two types of minerals B and Y. If the refinery to B are at top and Y are at left and the corresponding minerals gets collected if there is a straight path from that grid location all the way to the refinery. Maximize the total amount of mineral mined. Read the rest of this entry »

Minimum number of coins

September 18, 2017

Given some denomination of coins (you can use any coins of one type), find the minimum no. of coins that can be used to get sum S. Read the rest of this entry »

Longest common substring

September 18, 2017

Given two strings, find the longest common substring between them. Read the rest of this entry »

Longest common subsequence

September 17, 2017

Given two sequence of elements (e.g. characters) find the longest common subsequence. Read the rest of this entry »

0/1 Knapsack

September 17, 2017

Given some weights and corresponding values associated with each weight, maximize the value while keeping the weight below a given weight. Also, each weight can be picked only once. Read the rest of this entry »

Maximum length of pair chain

September 17, 2017

Given a list of pairs, find the maximum length of the pairs chain formed if and only if the second element in a pair is less than the starting element in another pair. In each pair though, the second element is always greater than the first element. Read the rest of this entry »


September 17, 2017

Given the prices of stock on particular day, find the maximum profit by determining the best time to buy and sell stock.

For an O(n^2) solution, loop through each price and compare its difference with all previous prices and find the maximum value Read the rest of this entry »