Programming Inteview Question

Then if  holds, the entire rows  and column  are set to .

For examples if the following is used as input matrix

4 9 14 19 24
3 8 13 18 23
2 7 12 17 22
1 6 11 16 21
0 5 10 15 20

using  the following  equality predicate (==3) (i.e. returns true if the passed parameter is 3) and  the resulting matrix is:

-1 9 14 19 24
-1 -1 -1 -1 -1
-1 7 12 17 22
-1 6 11 16 21
-1 5 10 15 20

Hint use template for make the procedure as general as possible.

Programming Inteview Question Solution

The proposed solution is simple but effective.  It uses two boolean vectors for tracking the rows and columns which have been already set to the value .

Then predicate is tested for each element of a valid row and column, and if it holds the corrensponding row and column are set to  using a helper function.

The following is the C++ templated code. Note that the predicate is a template parameter.

template<class T, unsigned int M, unsigned int N, class Predicate >
void setRowColumn(T matrix[M][N], const T& v , Predicate p){
bool rows[M] = {0};
bool cols[N] = {0};
for(uint i = 0 ; i < M ; i++){
if(!rows[i])
for (uint j = 0; j < N; ++j) {
if(!cols[j] && p(matrix[i][j])){
rows[i] = cols[j]=1;
setTo<int, M, N>(matrix, i,j,v);
break;
}
}
}
}

//-- Helper function which sets the entires row and column to value v
//-- one value is set twice. Which one? how could that be avoided?
template<class T, unsigned int M, unsigned int N>
void setTo(T matrix[M][N], uint row, uint col, const T& v){
for (int i = 0; i < M; ++i)
matrix[i][col] = v;

for (int i = 0; i < N; ++i)
matrix[row][i] = v;
}

Be the first to leave a comment. Don’t be shy.