Problem Statement
Given a huge grid G with M rows and N columns and a pattern P with m rows and n columns. The task at hand is to perform a pattern search in grid, and print YES if the pattern grid P exists in the grid G otherwise print NO
[caption id="attachment_3611" align="aligncenter" width="960"] Pattern Search in Grid[/caption]
Its a simple string search but requires special attention to the boundary cases. Here is a list of them
We only need to test the grid G for M-m rows, because anything below row R-r cannot accommodate the pattern of size r.
We only need to test the gr...

Read More
# Matrices

questions containing matrix operations.

## Ring wise Matrix Rotation

Introduction
Matrices have always been of interest in the field of encryption, specifically matrix rotations which leads to a symmetric as well as asymmetric cryptography. To learn more about regular matrix rotation please check my recent posts on the subject. This however is a fancy Ring wise Matrix Rotation and is no where related to the regular rotation of matrices.
Problem Statement
You are given a M*N grid with the restriction that the minimum of M and N is an even number. Rotate each of the rings by a distance K. We can choose the direction of rotation to be either clockwise or anti-c...

Read More
## Matrix Transformation to make rows and columns zero

Introduction
Another interview question about matrices. Matrices have been of great interest in programming and Linear Algebra and a matter of study for most of the programmers. The problem statement follows:
"Given a matrix A of size M * N where M is the number of rows and N is the number of columns and each of its cell A[i][j] is populated with either zero or one. Transform the matrix such that if there exists a cell A[i][j] = 0 then the row i and column j is zero in the resultant matrix".
You must not use extra space and try to solve it in lowest possible running time.
Understanding...

Read More
## Matrix Rotation and Matrix Transpose

Problem Definition – Matrix Rotation (by 90, 180, 270 degrees)
This is a very famous interview question and has been asked numerous times. We are trying to solve the problem of matrix rotations where the inputs are as follows:
A matrix of dimension M * N
A number from the set (90, 180, ,270) by which we need to rotate the matrix.
For simplicity we will consider a matrix to be a 2 dimensional array of integers.
What does it mean to rotate a matrix?
This can only be explained by nice diagrams. Just for a formal definition, I would say that matrix rotation is a structural re-arrangeme...

Read More