Skiing on Mountains Matrix : “John Snow” likes Skiing on Mountains a lot.That’s not very surprising, since skiing is really great. The problem with skiing is one have to slide downwards to gain speed. Also when reached the bottom most point one has to wait for ski-lift to get to higher altitude.

“John Snow” seeks your help to know the longest run possible with the given peaks, As (“John Snow knows nothing” ), That altitude of different peaks is given by a grid of numbers. Look at this example Skiing on Mountains Matrix Path: [Read more…]

## The greedy coins game Dynamic Programming

The greedy coins game Dynamic Programming Solution :

Question statement There is a row of 2n coins on the table; each coin can have any positive integer value. Two players alternate turns.

On a player’s turn he/she must take one of the two coins on either END of the row of remaining coins, so with each turn the row gets shorter by one.

After all the coins have been taken, the player with the higher total value is the winner.

Decide Strategy and Determine the maximum possible amount of money we can definitely win if we move first. [Read more…]

## Minimum insertions to form a palindrome

Given a string, find the minimum number of characters to be inserted to form Palindrome string out of given string

Before we go further, let us understand with few examples:

ab: Number of insertions required is 1. **b**ab

aa: Number of insertions required is 0. aa

[Read more…]

## ‘N’ Story Building, with 1,2,3 steps how many ways can a person reach top of building.

A building has n steps. A person can take 1,2 or 3 steps. In how many ways can a person reach top of building.

In order to build logic, lets think from first step

If N=1 and Steps=1. There is only 1 way to reach with 1 step.

F(1)=1

If N=2 and Steps=1. There 1 way to reach with 1+1 step.

F(2)=1

if N=2 and Steps=1,2 . There are 2 ways to reach, with 1+1 & 0+2 steps.

F(2)=2

if N=3 and Steps=1,2 . There are 3 ways to reach, with 1+1+1 , 1+2 & 2+1 steps.

F(3)=3.

## Count number of ways to reach a given score in a game

Input: n = 20

Output: 4

There are following 4 ways to reach 20

(10, 10)

(5, 5, 10)

(5, 5, 5, 5)

(3, 3, 3, 3, 3, 5)This problem is a variation of coin change problem

[Read more…]

## Count Possible Decodings of a given Digit Sequence

1 2 3 = A B C

1 23 = A X

12 3 = L C

[Read more…]

## Find the smallest window in a string containing all characters of another string

Given two strings string1 and string2, find the smallest substring in string1 containing all characters of string2 efficiently.For Example:

Input string1: “this is a test string”

Input string2: “tist”

Output string: “t stri”

## Word Break Problem

This is a famous Google interview question, also being asked by many other companies now a days.Consider the following dictionary

{ i, like, go, hired, gohired, site, sweet,fruit, man, go, mango}

Input: ilike

Output: Yes

The string can be segmented as “i like”.

Input: ilikemango

Output: Yes

The string can be segmented as “i like mango” or “i like man go”. [Read more…]

## Longest Increasing Subsequence

## Given Set of words or A String find whether chain is possible from these words or not

**Chain :**A chain can be formed between 2 strings if last character of the 1st string matches with the first character of the second string.

**Example : cat ,eng,**

**galactic**

**, tree**

Brute Force Approach : With each word from input string and try to create chain.

**Input : English, Yellow , Maths , Chemistry , Water , Horse**

**Example 1)****English, Yellow , Maths , Chamistry , Water , Horse**

__Example 2)__**cat ,engg,**

**galactic**

**, tree**

**:**

__Example 3)__**Apple, elephant, truck**.

**Example3)**but as “ark” contains both starting and ending character which doesn’t meet. This Words cant create chain.

**Code**: