## Dynamic Programming – Maximum Product Cutting Problem.

Objective: Given a rope of length n meters, write an algorithm to cut the rope in such a way that product of different lengths of rope is maximum. At least one cut has to be made. Note: Assume that the length of rope is more than 2 meters, since at least one cut has to … Read more

## All N Length Strings from Given String of Length K

Objective: Print All N Length Strings from Given String of Length K where characters can appear multiple time. Example: String k = “ALGO” N=2 Result: AA LA GA OA AL LL GL OL AG LG GG OG AO LO GO OO   Approach: This problem is quite similar to Print All N Length Strings from … Read more

## Generate Well Ordered Passwords of a Given Length K

Objective: Generate Well Ordered Passwords of a Given Length K. Well ordered means that digits should be in increasing order in every generated password. Example: K = 7 1234567 1234568 1234569 1234578 1234579 1234589 1234678 1234679 1234689 1234789 1235678 1235679 1235689 1235789 1236789 1245678 1245679 1245689 1245789 1246789 1256789 1345678 1345679 1345689 1345789 1346789 1356789 … Read more

## Print All N Length Strings from Given Number K

Objective: Given Number K, Print all the strings of N length. Example: N = 2, K = 3 [1, 1] [2, 1] [3, 1] [1, 2] [2, 2] [3, 2] [1, 3] [2, 3] [3, 3] Approach: This problem is quite similar to Print All Subsets of a given set and Print All Combinations of … Read more

## Dynamic Programming – Maximum size square sub-matrix with all 1s

Objective: Given a matrix of 0’s and 1’s (binary matrix). Find out Maximum size square sub-matrix with all 1’s. Example: Approach: Base Cases: If only one row is given then cells with 1’s will be the Maximum size square sub-matrix with size = 1. If only one column is given then cells with 1’s will … Read more

## Dynamic Programming – Longest Increasing Subsequence

Objective: The longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence in a given array such that all elements of the subsequence are sorted in increasing order. OR Given a array A[1,2,……,n] , calculate B[1,2….m] with B[i]

## Backtracking – Search a Word In a Matrix

Objective : Given a 2D matrix of characters. Check whether the word exist in the matrix or not. If it exists then print its path. All movements are allowed (right, left, up, down and diagonally). Example: Approach: We will show the path as increment counter   Create a solution matrix of the same structure as … Read more

## Find the Second Largest Element in an Array

Objective: Given an array of integers. find the second largest element in the array. Example: int[] A = { 1, 2, 10, 20, 40, 32, 44, 51, 6 }; Second largest Element : 44 Approach: Keep track of largest element and when ever you change the value of largest element, store its current value to … Read more

## Dynamic Programming – Minimum Coin Change Problem

Objective: Given a amount ‘A’ and n coins,   v1<v2<v3<………..<vn . Write a program to find out minimum numbers of coins required to make the change for the amount ‘A’. Example: Amount: 5 Coins [] = 1, 2, 3. No of ways to make the change are : { 1,1,1,1,1} , {1,1,1,2}, {2,2,1},{1,1,3} and {3,2}. So … Read more

## Find the Deepest Left Node in a Binary Tree.

Objective: – Given a binary tree, Find the deepest left node in it. Approach: This approach is very similar to “Find the Deepest Node in a Binary Tree” with little modification. Take two global variable as “deepestlevel” and ” deepLeftNode“. starting with level=0, Do the inorder traversal and whenever you go down one level ( … Read more

## Find the Deepest Node in a Binary Tree.

Objective: – Given a binary tree, write an algorithm to Find the deepest node in it.

Approach:

• Take two global variable as “deepestlevel” and “value“.
• starting with level=0, Do the inorder traversal and whenever you go down one level ( root.left OR root.right), increase the level by 1.
• Keep checking if deepestlevel < level, if yes then update the “deepestlevel ” and “value “.
• At the end return “value“, which will the deepest node value.
• See the code for better explanation.

## Find numbers which are palindrome in both their decimal and octal Representations

Objective: Given a range of integers, find all the numbers which are palindrome when they are represented in Decimal Value( base 10) and in Octal value(base 8).

Example :

```Number : 373 (Decimal) and digits are palindrome.

Convert it into Octal which is 565 and that's also palindrome.
```

Approach:

## Find All the Well Ordered Permutations of a Given String.

Objective: Write an algorithm to Print All the Well Ordered Permutations of a Given String.

What is Well Ordered String: When all the alphabets in a string occur in the increasing order irrespective of Lower Case or Upper case.

http://www.careercup.com/question?id=6206517812396032

Example :

```"Sumit" - Not Well Ordered . 'u' occurred after 'S'.

"Now" - Well Ordered. N<o<W.

Input: Interview
Output:
[e, e, I, i, n, r, t, v, w]
[e, e, i, I, n, r, t, v, w]
[e, e, i, I, n, r, t, v, w]
[e, e, I, i, n, r, t, v, w]

```

## Construct a Special Triangle from a Given Array

Objective: Given an array of integers such that first level will print all the elements in the array and from then at each level number of elements will be one less than the previous level and elements at the level will be the Sum of consecutive elements in the previous level. Print it in a reverse level. See Example.

Example: