CareerCup

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).

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

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.

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.

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.

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

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

"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

Given an n-by-n matrix of 0's and 1's where all 1's in each row come before all 0's, find the most efficient way to return the row with the maximum number of 0's.

In a nxn matrix, data provided like below. We need to find the groups of 1s with the adjustent column and row.
eg)
0 0 0 0
1 1 1 1
0 0 0 0

group of 1 is 1

1 0 0 0
0 0 0 1
1 1 0 0

group of 1s is 3

Any thought how to get the set of groups.

Given a binary matrix of N X N of integers , you need to return only unique rows of binary arrays
eg:
0 1 0 0 1
1 0 1 1 0
0 1 0 0 1
1 1 1 0 0
ans:
0 1 0 0 1
1 0 1 1 0
1 1 1 0 0

given a number n... print a spiral matrix in O(1) space example if n=5 the op should be:

25 24 23 22 21
10 09 08 07 20
11 02 01 06 19
12 03 04 05 18
13 14 15 16 17

The question may appear trivial but its not...u hav to print in O(1) space

Initially you have a 2x2 matrix, say zoom1:
a b
c d
zooming it results in a 4x4 matrix (zoom2) as follows:
aa ab ba bb
ad ac bd bc
da db ca cb
dd dc cd cc
zooming it again will result in an 8x8 matrix and so on..
The question is, given a sequence say abaaccda... we need to find out the sequence coming just left to it. For e.g. if the given sequence is "bd", the sequence coming just left to it is "ac". For "cb" it's "ca" etc. [Amazon Hyderabad]

Flood fill algorithm.

given a matrix pxq
You start from top left and have to reach the bottom right. Can only traverse right or bottom
How many ways are there to reach at the bottom right?

Print a matrix spirally

Given a matrix of characters M and an input string S, find if S occurs in M in horizontal or vertical direction.

Third round:
you are given a M x N matrix with 0's and 1's
find the matrix with largest number of 1,


1. find the largest square matrix with 1's
2. Find the largest rectangular matrix with 1's

You are given a two dimensional array (say 5*5) in which all the rows as well as the columns are sorted. Describe an efficient algorithm to discover if an element is present or not.

Write a progam to rotate a matrix by 90 degrees.

Write a code to calculate kth power of a matrix of size nxn. You can assume that matrix multiplication is O(n^3).

Suppose you have an NxN matrix of positive and negative integers. Write some code that finds the sub-matrix with the maximum sum of its elements