# 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

You are here: Home

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

Trapping Rain Water or Water collected between towers : Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

Example:

Input – {1,5,2,3,1,7,2}

Output – 9 [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

In a Binary Search Tree (BST), all keys in left subtree of a key must be smaller and all keys in right subtree must be greater. So a Binary Search Tree by definition has distinct keys and duplicates in binary search tree are not allowed.

How to allow duplicates where every insertion inserts one more key with a value and every deletion deletes one occurrence?

A **Simple Solution** is to allow same keys with count. For example consider insertion of keys 3, 6, 7, 8, 8, 8, 10, 12, 12 in an empty Binary Search Tree [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

Find weather two given trees are isomorphic to each other or not.

Lets understand What is isomorphic strings

AAB and XXY are IsoMorphic to each other, consider A replaces/morphs as X and B as Y, then both strings are isomorphic.

ABC and XXY are not IsoMorphic.

[Read more…]

Last Updated on by Dhaval Dave

Hi Folks, Today I am going to show and explain Security bug of Naukri.com from Mails, Being a Backend Coder and with knowledge of SQL injection and security breach issues, I came to know about Bug in Naukri.com’s security that without login,you can access your or your Friend’s profile, if he has sent you Mail of Naukri.com’s Job Opening Mail.

This issue I found out because, I have forwarded mail to few of my colleague as I was not looking out for job change.

One of my colleague got the job opening mail which I have forwarded to him, to update his profile he has clicked on “Update now”, And profile which was opened was mine, without seeing that, he has updated his CV into my Profile.

And due to that I have started getting Calls of HRs that weather I am looking for job change or not. When I refused to some HRs, One of HR said that why I have updated profile, if I am not looking out and even some HRs claimed that CV in my naukri profile is of some other person from my company.

So I understood that there should be fussy about the mails which I am forwarding to my friends/colleagues to help them getting job. After investigation of mail template of Naukri.com and “Update Now” Button’s url I came to know that this security glitch or security breach is present.

You help a colleague/friend and if your colleague/friend can access your profile, along with email/phone he can see your Salary information which is highly confidential.

Stay Safe.

*PS : I have showed this step and performed this steps for spreading awareness and not to malign Naukri.com, I highly respect Sanjeev Bikhchandani (CEO of Naukri) I sincerely request Naukri.com to act upon their security breach. And If they find this search useful, they can reward me ;)

Last Updated on by Dhaval Dave

Given n ranges in the form of Start Number and End Number in Two Array L and R such that

L[i]-R[i] is one range given. Our task is to find the maximum occurred smallest (first) integer in all the ranges. Means If more than one integer occurs max times, print the smallest one.

In other you can find similar code in

**Time Complexity**: O(n + MAX) and **Space Complexity : **O(Max)

We have tried to reduce complexity to O(n+m), space complexity : O(m) where m is largest integer in L or R

means m is largest range number.

- 1
- 2
- 3
- …
- 15
- Next Page »