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];}

    

Common divisor

#include <iostream>

using namespace std;

int main()

{

   int a,b,c[50],d[50],count=0;

   cin>>a>>b;

   for(int i=0;i<50;i++){

       if(a%(i+1)==0){

           c[i]=i+1;

       }

       

   }

    for(int i=0;i<50;i++){

       if(b%(i+1)==0){

           d[i]=i+1;

       }

       

   }

   for(int i=0;i<50;i++){

       if(c[i]==d[i]){

           cout<<c[i]<<endl;

       

   }}

  

}

Palindrome

#include<iostream>
#include<string>
using namespace std;
int main(){
string s;
cin>>s;
int b=0;
for(int i=0;i<s.size();i++){if(s[i]!=s[s.size()-i-1])

{b=1;
break;}
}
if(b==0){
    cout<<"yes";
}
else cout<<"N0";
    }
    

Graph Theory

Graph Theory

Adjacency matrix

An adjacency matrix is a VxV binary matrix A. Element $A_{i,j}$ is 1 if there is an edge from vertex i to vertex j else $A_{i,j}$ is 0.

Note: A binary matrix is a matrix in which the cells can have only one of two possible values - either a 0 or 1.

The adjacency matrix can also be modified for the weighted graph in which instead of storing 0 or 1 in $A_{i,j}$, the weight or cost of the edge will be stored.

In an undirected graph, if $A_{i,j}$ = 1, then $A_{j,i}$ = 1. In a directed graph, if $A_{i,j}$ = 1, then $A_{j,i}$ may or may not be 1.

Adjacency matrix provides constant time access (O(1) ) to determine if there is an edge between two nodes. Space complexity of the adjacency matrix is O($V^2$).

The adjacency matrix of the following graph is:

i/j: 1 2 3 4
1 : 0 1 0 0
2 : 0 0 0 1
3 : 1 0 0 1
4 : 0 1 0 0

code for adjacency matrix

#include<iostream>
using namespace std;
int main(){

    int x,y,node,edge;

    cin>>node>>edge;

    int a[10][10]={0};

    for(int i=0;i<edge;i++){

        cin>>x>>y;

        a[x][y]=1;
        
    }
  
}

TEST YOUR UNDERSTANDING

Edge Existence

You have been given an undirected graph consisting of $N$ nodes and $M$ edges. This graph can consist of self-loops as well as multiple edges. In addition , you have also been given $Q$ queries. For each query , you shall be given 2 integers $A$ and $B$. You just need to find if there exists an edge between node $A$ and node $B$. If yes, print "YES" (without quotes) else , print "NO"(without quotes).
Input Format:
The first line consist of 2 integers $N$ and $M$ denoting the number of nodes and edges respectively. Each of the next $M$ lines consist of 2 integers $A$ and $B$ denoting an undirected edge between node $A$ and $B$. The next line contains a single integer $Q$ denoting the number of queries. The next Line contains 2 integers $A$ and $B$ denoting the details of the query.
Output Format
Print Q lines, the answer to each query on a new line.
Constraints:
$1\le N\le {10}^3$
$1\le M\le {10}^3$
$1\le A,B\le N$
$1\le Q\le {10}^3$

#include<iostream>
using namespace std;
int main(){

    int x,y,node,edge;

    cin>>node>>edge;

    int a[10][10]={0};

    for(int i=0;i<edge;i++){

        cin>>x>>y;

        a[x][y]=1;
        
    }
  int r,p,q;
  cin>>r;
  for(int i=0;i<r;i++){
      cin>>p>>q;
      if(a[p][q]==1){
          cout<<"YES"<<endl;
          
      }
      else cout<<"NO"<<endl;
      
  }

}