Dynamic programming problem

Given a binary matrix, find out the maximum size square sub-matrix with all 1s.

For example, consider the below binary matrix.

Please suggest solution to this in comment section.

Interview problem #2 ( whether the word can be found in the matrix)

Given a 2D matrix of characters and a target word, write a function that returns whether the word can be found in the matrix by going left-to-right, or up-to-down.

For example, given the following matrix:

[['F', 'A', 'C', 'I'],
 ['O', 'B', 'Q', 'P'],
 ['A', 'N', 'O', 'B'],
 ['M', 'A', 'S', 'S']]

and the target word 'FOAM', you should return true, since it's the leftmost column. Similarly, given the target word 'MASS', you should return true, since it's the last row.

Suggest solution to this in comment section.

Solution to problem #1

#include<iostream>
using namespace std;

int count(int m, int n) {
if (m == 1 || n == 1) {
return 1;
}

else {
return count(m, n - 1) + count(m - 1, n);
}


}

int main() {
int m,n;
cin >>m>> n;
cout << count(m, n)<<endl;

}

I did this question using recursion we can also use DP(dynamic programming) in this. The time complexity of above solution is exponential.

Explanation of recursion is that we can come to (m,n-1) and take a step down or I can come to (m-1,n) and can take a right and come to (m,n). 

Interview problem #1 (possible path in a matrix)

Count all possible paths from top left to bottom right of a mXn matrix and the constraint is that you can only move right and bottom.

Test Cases:

1) m=2,n=2

output=2

2) m=3,n=3

output=6

3) m=5,n=5

output=70

please suggest solution to this problem.

A new series

Hello guys,

I am starting this new blog which is related to coding. First let me introduce myself. I am Fazal Ahmad third year undergraduate student currently pursuing major in Electrical Engineering at IIT Bombay. I am somewhat between beginner and intermediate in coding but trying to improve my coding skills. I am starting this blog maybe because I want to learn and by this I can also share my knowledge.

I am starting a new coding series in which I will post daily a coding question (mostly asked in interviews). I will try to solve and put solution (with explanation) on the blog but guys I want you also to contribute to solution (with explanation). Please give some suggestions so that I can improve my blog. 

Getline Function

#include <iostream>
#include<string>
using namespace std;

int main()
{
   string s;
   getline(cin,s);
   cout<<s;
}

String Character Shift

• Given a string $S$ of length $N$, shift each character of the string by $K$ positions to the right, where $K\le N$.

For example: Say $S$ = "hacker" and $K=2$. Here $N=6$.
Shifting each character in $S$ by $2$ positions to the right would result into $erhack$.
Note that $S\left[0\right]$ i.e. 'h' is moved by 2 positions to the $S\left[2\right]$. Also, $S\left[5\right]$ i.e. 'r', which is the last character in $S$ comes round-about back to $S\left[1\right]$ as there is no space for 'r' to go beyond the limits of string length.

Approach:

• Declare another auxillary string $shiftedS$ that is of the same size as $S$.
• Copy $i^{th}$ element of $S$ to the $(K+i{)}^{th}$ position in $shiftedS$. This means, $shiftedS[i+K]=S\left[i\right]$ where $0\le i<N$.
• Make sure that $i+K$ never exceeds $N$, because that will try to access a memory location which is not declared in $shiftedS$. There's a simple trick to ensure that - use $(i+K)modN$ .

#include <iostream>

#include<string>

using namespace std;

int main()

{

    string s,p;

    cin>>s;

    int k;

    cin>>k;

    for(int i=0;i<s.size();i++)

    {

        int index=(i+k)%s.size();

        p[index]=s[i];

        

    }

  for(int i=0;i<s.size();i++) { cout<<p[i];}