Programming Interview Question - Set Row and Column if - C/C++

Programming Inteview Question

Question: write an algorithm that take as input a matrix of type T  and size M, a value of type T, (v) and a unary predicate P.

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.

programminQuestionRowColumn

Example of input and result matrices


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.

Join the Discussion

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>