# Maximum size of square sub matrix with all 1

Consider a binary matrix as shown in the figure below. You need to find the maximum size of square sub matrix with all 1’s.

Interview Questions and Discussion in Google, Microsoft, Amazon, Walmart

Last Updated on by Abhey Rana Leave a Comment

Consider a binary matrix as shown in the figure below. You need to find the maximum size of square sub matrix with all 1’s.

Last Updated on by Abhey Rana Leave a Comment

Given two strings x and y, What is the cheapest possible way to convert x into y where following operations are allowed to perform –

- Substitute a character c of x with c’.
- Insert a character in x.
- Delete a character from x.

Each of these operations may have a cost associated with them. For example we may have a 26*26 matrix which can have a cost of substituting one character with another character. In a similar manner we may have a 26*2 matrix which can have cost of inserting and deleting a character.

Last Updated on by Dhaval Dave

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…]

Last Updated on by Dhaval Dave

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…]

Last Updated on by Dhaval Dave

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…]

Last Updated on by Dhaval Dave

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.

Last Updated on by Dhaval Dave

Consider a game where a player can score 3 or 5 or 10 points in a move. Given a total score n, find number of ways to reach the given score.Examples:

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…]

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…]

Last Updated on by Dhaval Dave

Find number of ways a string can be decoded into, if A=1, B=2, C=3 … Z=25 and encoding number is 123 ways decoding can be done is

1 2 3 = A B C

1 23 = A X

12 3 = L C

[Read more…]

1 2 3 = A B C

1 23 = A X

12 3 = L C

[Read more…]

Last Updated on by Dhaval Dave

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”

Last Updated on by Dhaval Dave

Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words. See following examples for more details.

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…]

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…]