## Tower of Babylon Solution – SPOJ.com

Problem statement: Given n different types of blocks. Each one of them may be duplicated as many times as you like. Each type has a height y, a width x and a depth z. The blocks are to be stacked one upon each other so that the resulting tower is as high as possible. Of course […]

## Matrix-chain multiplication

We are given a sequence (chain) (M1, M2, M3…Mn) of n matrices to be multiplied and we need to find the most efficient way to multiply these matrices together. Now, if the chain of matrices is M1*M2*M3*M4, then it could be evaluated in various distinct ways without affecting the final product: (M1(M2(M3*M4))) […]

## Longest Common Subsequence Solution

The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to given two sequences. LCS problem is used to determine how similar the two DNA strands are. For instance Example 1: Input: text1 = “abcde”, text2 = “ace” Output: 3 Explanation: The longest common subsequence is […]

## Longest Increasing Subsequence Solution (LIS) – LeetCode Solution [Medium]

Given an integer array arr, return the length of the longest strictly increasing subsequence. Strictly increasing sequence is a sequence such that all elements of the sequence are sorted in increasing order. NOTE: In mathematics, a subsequence of a given sequence is a sequence that can be derived from the given sequence […]

## Find the minimum distance to travel through a road having hills [Interview Question]

Problem Statement: Alansh has to travel through a road having hills of different heights. Also each hill has a cave to pass through it, to avoid travelling extra distance of a hill. Alansh wants to travel through this road by taking at most K caves, so that he has to travel […]

## Edit Distance – LeetCode Solution [Hard]

Problem statement: Given two strings word1 and word2 (in lowercase alphabets), return the minimum number of operations required to convert word1 to word2. You could only perform three following operations on a word: Insert a character Delete a character Replace a character Example 1: Input: word1 = “horse”, word2 = “ros” Output: 3 Explanation: horse -> rorse (replace […]

## Decode Ways Solution LeetCode

A message containing letters from A-Z can be encoded into numbers using the following mapping: ‘A’ -> “1” ‘B’ -> “2” … ‘Z’ -> “26” To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, “11106” can be mapped […]

## Greedy approach vs Dynamic Programming

Greedy approach and Dynamic programming both are used for solving optimisation problems. However often we need to use DP since optimal solution cannot be guaranteed by a greedy algorithm. Consider Knapsack problem We could solve it by brute-force, by generating all possibilities of choosing a subset of n items and selecting […]

## Knapsack problem (Finding selected items)

In the last post, we learned about Knapsack problem and also found an efficient solution to the problem using Dynamic programming. A little recap Let given weights & values of n items to be put in a knapsack of capacity W ie. We’ve 2 integer arrays value[0..n-1] and weight[0…n-1]. The objective is to find out […]

## Knapsack Problem (Dynamic Programming)

Problem statement Let given weights & values of n items to be put in a knapsack of capacity W ie. We’ve 2 integer arrays value[0..n-1] and weight[0…n-1]. The objective is to find out the maximum value subset of value[] array such that sum of weight of subset is smaller or equal […]