Cutting the Rod Problem. Part_1: Recursion and Memoization
Given pieces of rod sizes. Find the max value we can get by cutting a rod of length n and selling the pieces.
Find minimum cost to travel to the destination railways station
There are N stations on a railway track. You are at the first station and you want to go to the final railway station. You can either go directly or take breaks in between. Given the cost of travel for each pair of stations, find the minimum cost of travel.
Number of ways to arrange tiles on a board
Given a board of size 2*n and tiles of dimension 1*2 each. In how many ways can we arrange the tiles so that entire board is covered. We can only place the tiles either horizontally or vertically without breaking them. For example, if the board is of length 3 (n=3), then tiles can be placed […]
Dynamic Programming concept
The basic idea of DP is applicable to problems that can be thought in terms of recursion. For example, consider problem of computing n’th fibonacci term:
How to prepare for Dynamic Programming Questions
The most difficult problems in Coding competitions and interviews of companies like Google, Microsoft etc. are from Dynamic Programming. DP as an approach to problem solving is discussed in almost all algorithm books. But, in most of the books, DP, as a concept is lost behind the difficult problems. For example, in one of the best […]
Minimum edit distance of two strings
Given two strings of size m and n respectively, find the minimum number of operations required to transform one string into another. The following thee operations are allowed Insert(pos, ch) – Insert a character at a position in the string. Delete(position) – Delete a character from a position in the string. Replace(position, character) – Replace […]
Check if array can be divided in two parts with equal sum
Given an array of integers, write a function that returns true if it can be divided in two parts having equal sum. For example: If Input array is {10, 20 , 30 , 5 , 40 , 50 , 40 , 15} Output: true Divide the array in two parts {0, 20, 30, 5, 40} […]
Compute x^n (x to the power n)
Write a C function to compute xn which uses minimum number of multiplications. unsigned int power(double x, unsigned int n)
Kadane's Algorithm to find maximum subarray sum
Given an array of n integers (both +ve and -ve). Find the contiguous sub-array whose sum is maximum (More than 1 sub-array may have same sum). For Example: Array Maximum Sub-Array sum ———————– ———————– —- {5, 7, 12, 0, -8, 6} {5, 7, 12} 24 {6, -2, -3, 4, -1, 10 } {6, -2, -3, […]
