Question:
Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0.
Solution:

#include <iostream>
#include <string.h>

using namespace std;


void transform(int **data, int M,int N){
 int *prev = new int[N];
 for(int i=0;i<N;++i)
  prev[i]=1;
 for(int i=0;i<M;++i){
  bool setrow = false;
  for(int j=0;j<N;++j){

   bool setcol=false;
   if( prev[j] == 1 && data[i][j] == 0  ){
    prev[j] = 0;
    setrow = true;
    setcol = true;

   } else if (prev[j]==0 && data[i][j]  ){
    data[i][j] = 0;
   }

   if (setcol){
    for(int k=i;k>=0;--k){
     data[k][j]=0;
    }
   }
  }
  if (setrow){
   for(int k=0;k<N;++k){
    data[i][k] = 0;
   }
  }
 }
 delete []prev;
}

void print(int **data, int M, int N){
 for(int i=0;i<M;++i){
  for(int j=0;j<N;++j){
   cout<<data[i][j]<<" ";
  }
  cout<<endl;
 }
}

int main() {
 int **data;
 data = new int* [4];
 for(int i=0;i<4;++i){
  data[i] = new int[5];
 }
 for(int i=0;i<4;++i)
  for(int j=0;j<5;++j)
   data[i][j]=1;

 data[0][3] = 0;
 data[1][2] = 0;
 data[2][3] = 0;

 print(data,4,5);
 transform(data,4,5);
 cout<<"------------------"<<endl;
 print(data,4,5);
        //release memory
       for(int i=0;i<5;++i){
           delete[] data[i];
       }
       delete[] data;
 return 0;
}

Coding Question: rotate a NxN matrix by 90 degrees in-place

Question:
Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?

Solution:

#include <iostream>
using namespace std;

void rotate90(int **array, int N){
    for(int i=0;i<N/2;++i){
        for(int j=i;j<N-1-i;++j){
	    int t1=array[j][N-1-i];
	    array[j][N-1-i] = array[i][j];

            int t2=array[N-1-i][N-1-j];
            array[N-1-i][N-1-j] = t1;

            t1 = array[N-1-j][i];
            array[N-1-j][i] = t2;

            array[i][j] = t1;
       }
    }
}

int main() {
    int **matrix;
    matrix = new int*[5];
    for(int i=0;i<5;++i)
        matrix[i] = new int[5];

    int count=0;
    for(int i=0;i<5;++i)
        for(int j=0;j<5;++j){
        matrix[i][j] = count++;
		}

    for(int i=0;i<5;++i){
       for(int j=0;j<5;++j){
           cout<<matrix[i][j]<<" ";
       }
       cout<<endl;
    }
    cout<<"----------------"<<endl;
    rotate90(matrix,5);
    for(int i=0;i<5;++i){
        for(int j=0;j<5;++j){
            cout<<matrix[i][j]<<" ";
        }
        cout<<endl;
    }
    //release memory
    for(int i=0;i<5;++i){
       delete[] matrix[i];
    }
    delete[] matrix;
    cout << "" << endl; // prints 
    return 0;
}

Decode a string

Q: We are given a char array like “a1b2c3″ we have to convert this array to array like this “abbccc” .This has to be done in place as we are given that array has just enough space to hold the expanded array. Here's an algorithm to solve this:

#include <iostream>

string decode(string estr){
    int patlen = estr.length();
    int reqdlen=0;
    for(int i=0;i<patlen;++i){
        if( isDigit(estr[i]) ){
            reqdlen+=estr[i]-'0';
        }
    }
 
    string ans;
    ans.resize(reqdlen);
    cout<<ans.length()<<endl;
    //case 1: if patlen >= reqdlen
    //e.g. a1 a1b2
    if( patlen  >= reqdlen ){
        int idx=0;
        char lastchar;
        for(int i=0;i<patlen;++i){
            if( isChar(estr[i]) ){
                lastchar = estr[i];
                ans[idx] = estr[i];
            }else if( estr[i] == '2' ){
              //a1b3 will never come
              //cout<    ans[idx] = lastchar;
              idx++;
            }
        }
    }else if( patlen < reqdlen ){
        //shrink the pattern by moving all chars with
        //count 1
        int idx =0;
        char lastchar;
        int newlen=0;
        for(int i=0;i<patlen;++i){
            if( isChar[estr[i]] ){
              ans[idx++] = estr[i];
            }else if( estr[i] != '1' ){
               idx++;
            }
        }

        newlen = idx;
        //now start filling from the back
        int lastdigit;
        idx=reqdlen-1;
        for(int i=newlen-1;i>=0;--i){
          if( isDigit(estr[i]))
            lastdigit=estr[i]-'0';
          else{
            for(int j=0;j<lastdigit;++j){
               ans[idx--]=estr[i];
            }
            lastdigit=1;
          }
        }
    }
 return ans;
}

int main() {
 cout<<decode("a1b1c1")<<endl;
 cout<<decode("a2b1c2")<<endl;
 cout<<decode("a2b2c2")<<endl;
 cout<<decode("a1b1c5")<<endl;
 cout<<decode("a9b1c5")<<endl;

 return 0;
}