## Matrix Interview Questions

- 0of 0 votes
Given the N*N matrix, find the given number in the matrix. All rows are sorted. And each row first element is less than the previous row last index.

input :

[1,3,5,7,9]

[11,13,15,16,20]

[21,22,23,24,25]

[30,32,35,40,45]

Given Num : 23

What is the best Optimal solution ? I have used BST but the interviewer asked to use any other which could do better in the above scenario.

- 0of 0 votes
Given a Matrix A,

The rules for movement are as follows :

1. Can only move Right or Down from any element

2. Can only move within the row and column of element we start from intially.

3. You can only visit or cross an element if its value is lesser than the value of element you start from.

Find total number of elements one can visit, If one starts from an element A(i,j) where i-> row and j-> column.

Note : You have to print this output for each matrix element.

Input : Matrix

1 2 3

2 3 1

3 1 2

Output:

1 1 3

1 3 1

3 1 1

- 0of 0 votes
Q 2. You are given a chess game board of size NxN. You have find out positions(i,j), where you can place N queens so that, none of the queens can kill each other without making their first move.

- 0of 0 votes
You are given an island which contains cliffs of various heights. A water droplet is placed on one of the cliffs. The water droplet always flows from higher height to lower height. Write a program that can calculate the lowest height cliff in the island that the water droplet can reach in the most efficient way you can think of. Example: if the droplet is placed on a cliff of height 5 and it is surrounded by cliffs of heights 6,3,2,2; it can flow to either of the cliffs of height 3,2,2 and then further flow from there.

- 0of 0 votes
Given an mXn Sorted matrix and a value X. Every row is sorted and first number of every row is greater than last number of previous row Find the value X in most efficient way.

- 0of 0 votes
Print elements of a matrix in spiral form.

- 1of 1 vote
You have a matrix that is sorted as such: For each value, every index to its right and below it must be larger than the current space's value. Likewise, all entries to its left and above it must be smaller than the current value. How would you go about searching this matrix for a specific number, given its sorted nature?

- 0of 0 votes
Given a 2D array of digits, try to find the occurrence of a given 2D pattern of digits. For example, consider the following 2D matrix:

7283455864

6731158619

8988242643

3839505324

9509505813

3843845384

6473530293

7053106601

0834282956

4607924137

Assume we need to look for the following 2D pattern:

950

384

353

- 0of 0 votes
Allocate a 2-D array of size m*n using malloc(). The array should be accessible as a[i][j].

- 0of 0 votes
You are tasked with defining and implementing a function. as input, you are given an n x m matrix. x may appear any number of times in a matrix. your function should modify thebmatrix such that any row and column where x originally appears are completely over written with x

For example:

- - - - -

- - - - -

- - - x -

x - - - -

- - - - -

Expected output:

x - - x -

x - - x -

x x x x x

x x x x x

x - - x -

- 0of 0 votes
Write a function to print unique rows of a matrix.

I am thinking of a 0(n) solution for this (if possible).

I am storing the rows of the matrix in a set of vectors and then printing those rows. Please tell me how to do this and the correct time complexity for that. I am not very good with STL.

- -2of 2 votes
Round 4

Question 5 : Question 5 : Do you know A/B testing ?, when we tell you some result of an experiment, how do you know the results are accurate ?, actually this question was about the statistics, he asked me many questions to check my statistics knowledge ?

- 1of 1 vote
The Mingo game:

The game of Mingo involves a 100 X 100 board with unique positive whole numbers in the range from 1 to 1,000,000 randomly distributed in the cells. Unique numbers are "called" one at a time and the goal is to have a "Mingo", which is an entire row or column of cells with numbers that have been called; one might also form a diagonal from corner to corner with numbers that have been called. Write a function that takes as parameters a square array of 100 X 100 positive whole numbers and list of "called" numbers. Your function will report whether a "Mingo" occurs, and after how many called numbers the first Mingo occurs. You may assume valid input.

- 0of 0 votes
Write a utility function that takes the starting position (P0) and length (L0) of one line segment plus the start position (P1) and length (L1) of a second line segment and returns the configurations where both segments end at the same point. Both starting points can be anywhere in three dimensional space.

- 0of 0 votes
A 2D matrix is given to you. Now user will give 2 positions (x1,y1) and (x2,y2),

which is basically the upper left and lower right coordinate of a rectangle formed within the matrix.

You have to print sum of all the elements within the area of rectangle in O(1) running time.

Now you can do any pre computation with the matrix.

But when it is done you should answer all your queries in constant time.

Example : consider this 2D matrix

1 3 5 1 8

8 3 5 3 7

6 3 9 6 0

Now consider 2 points given by user (0, 2) and (2, 4).

Your solution should print: 44.

i.e., the enclosed area is

5 1 8

5 3 7

9 6 0

- 0of 0 votes
Given is a matrix arr[n][n], find a submatrix sub[m][m] such summation of all the elements in submatrix is maximum.

Given condition,

1. m <= n

2. m >= 2

3. consider positive, negavive and zero integers in arr[n][n]

4. User provide n.

- 2of 4 votes
Search in a row wise and column wise sorted matrix

- 1of 1 vote
`In given array find zero and replace the entire row and column with zeros E.g Input: 1 2 3 4 5 6 7 8 9 10 0 11 12 13 14 15 Output: 1 2 0 4 5 6 0 8 0 0 0 0 12 13 0 15`

- 0of 0 votes
Write a code to read and write a matrix in below given way.

Note : no. indicates the sequence here.

I/P

1 2 3

4 5 6

7 8 9

O/P

1 6 7

2 5 8

3 4 9

- 1of 1 vote
Given an n x n matrix A(i,j) of integers, find maximum value A(c,d) - A(a,b) over all choices of indexes such that both c > a and d > b.

Required complexity: O(n^2)

- 1of 1 vote
String [] [] matrix = {{"A","N", "L", "Y", "S"},{"I", "S", "D", "E", "S"},{"I", "G", "N", "D", "E"}};

// 2. Given a word "DES"

// 3. Write a program to find the occurences of this word "DES". Letters must be next to each other in the matric.

// 4. "Next" means: left, right, up, down, left down, right down, upper left, upper right

// 5.. For example: S at (1,1): A, N, L, D, N, G, I, I are next to S at (1,1)

Required output

// // D - [1, 2], E - [1, 3], S- [1, 4]

// D - [1, 2], E - [1, 3], S- [0, 4]

// D - [2, 3], E - [2, 4], S - [1, 4]

// D - [2, 3], E - [1, 3], S - [0, 4]

// D - [2, 3], E - [1, 3], S - [1, 4]

- 2of 2 votes
Given an NxM (N rows and M columns) integer matrix with non-negative values (0..MAX_INT inclusive). What is the maximum sum from going top left (0, 0) to bottom right (N-1, M-1) ? The condition is that when you're at point (p, q), you can only move to either right (p, q+1) or down (p+1, q).

Expected time complexity O(N*M)

Expected space complexity O(N+M)

From the space complexity it looks like there is a DP solution, but I couldn't figure it out.

- 0of 0 votes
There is a binary tree of size N. All nodes are numbered between 1-N(inclusive). There is a N*N integer matrix Arr[N][N], all elements are initialized to zero. So for all the nodes A and B, put Arr[A][B] = 1 if A is an ancestor of B (NOT just the immediate ancestor).

- 0of 0 votes
We are given a matrix of MxN elements with each element either being 0 or 1.Find the shortest path between a given source cell to a destination cell.

An element value of 0 means we cannot create a path out of that cell

- -1of 1 vote
Consider there are n matrices. For eg, A, B, C and D are four matrices. Find the groupings of matrices during their product, the operations involved in your choice of grouping is minimal.

For eg, you can group like (AB)CD or (ABC)D or A(BC)D or A(BCD) .... But among these options in which grouping the operations of matrix multiplication will be minimal. Remember in matrix multiplication , multiplication and sum of elements are involved.

- 0of 0 votes
Given a matrix of 0's and 1's find the number of groups of 1's in the matrix.

A group of 1's can be formed if a 1 is present either vertically or horizontally to the adjacent 1 and not diagonally.

1 0 0 0

1 1 0 0

0 0 1 1

0 0 1 1

The above matrix has two groups of 1's while the one shown here has only one group

1 1 0 0

1 1 1 0

1 1 0 0

No restrictions on space complexity was given but the interviewer did mention that the time complexity should be efficient and that it should work for extremely large matrix's as well.

- 0of 0 votes
given m x n matrix print all the possible paths top to down.

Example

1 2 3

4 5 6

7 8 9

path for root(0,0) 1

1-4-7

1-4-8

1-5-7

1-5-8

1-5-9

similarly path for 2(0,1)

2-4-7

2-4-8

2-5-7

2-5-8

2-5-9

2-6-8

2-6-9

note- root 1 can go to middle down or right down since there is no left index available. if root element has left middle and right it can go to all those paths like 2 or 5.

follow up : provide the path which has maximum path sum.

code in java.

- 0of 0 votes
Given a m * n matrix and value k. Find k * k matrix within the given matrix whose sum is maximum.

- 0of 0 votes
Search a number in a large square but sorted matrix. Since the matrix can be very large, keep algorithmic efficiency in mind.

- 0of 0 votes
"Min(Max elements rows) not less than Max(Min of columns)"

can you tell me whether above statement ist true or false..

if it true, then tell me solutoin.

if it false, then tell me example