CareerCup

Given a N*N adjacency matrix of graph I need to find the size of maximum set of vertices that do not share any common edge between any two vertices of the graph.

Like : Say we have 3*3 matrix as

0 1 0
1 0 1
0 1 0

Then here answer is 2 as vertex 1 and vertex 3 dont have any edge in common.

I was asked this question in my interview to implement it in c++.

Given a N*M grid I want to find biggest submatrix not necessarily a square one that has all the value in it same.

Like

If N=4 and M=5 and matrix is

1 2 3 4 5
1 2 2 2 3
4 2 2 2 6
3 4 5 6 7

Then here answer will be matrix will be
2 2 2
2 2 2

So I need to find upper leftmost coordinate of this submatrix that is [2,2] and bottommost right coordinate that is [3,4].

I was to write a code for it in c++ in my interview

Given N Vertices and M Edges. Each Edge connects two vertices.

There is at most one way to move between each pair of vertices.

Each vertex is either locked or unlocked .There is a perfect path between two different vertices if both vertices are unlocked, and are connected with each other by some way.

The question is What is the number of pairs of vertices, which have a perfect path between them and also What is the number of the vertices, which have at least one perfect path passing through that vertex.

NOTE : There is at most one way to move between each pair of vertices, that is, the given graph is a forest

EXAMPLE : Say we have 6 Vertices and 5 Edges.

A=[1,1,1,1,1,0] It shows that A[i]=1 if ith vertex is unlocked otherwise 0.

Let the connected pair of vertices are : (1,2),(1,6),(1,5),(2,4),(4,3)

Here ,Answer for first question is 10 and second one is 5.

So,interviewer asked me to device an efficient algorithm for it and also code it in c++

Given a 2d array N*M made of only 1's and 0's . I need to find a maximum subarray(square or rectangle) between two rows of the given 2d array which has all ones inside it. I need to find count of ones in this maximum subarray

EXAMPLE : Let N=4 and M=5 and the array be

1 0 1 1 0

1 0 1 1 1

0 1 1 1 1

0 0 0 0 1

Now if their are Q(say here it be 2) queries each describing upper and lower row between which we need to find this subarray.

Query 1 : 1 1(means start at row 1 and end also at row 1).Then we can clearly see answer will be 2

Query 2 : 2 3(means start at row 2 and end at row 3).Then answer will be 6 here.

Now,if queries can be very large in number(say upto 10^6) .How to tackle this problem

Given a rectangular grid of N*M (1-based indexing) in which their are k monsters on k different cells.Now we need to answer Q queries in which we will be given lowest row number(L) and highest row number(H) we need to tell maximum area of rectangle between those rows that don't have a monster.(Here area of rectangle means count of cells only)

Example : Say we have a grid of 4 * 5 (mean n=4 and m=5) and monsters are located on 7(=k) cells which are (1,3) , (1,4) , (2,1) , (2,4) , (3,2) , (4,1) , (4,2) and let we have 1 query in which L=3 and H=4 then the maximum area is 6 here.

Now if the queries are very large say 10^6.Then how to tackle this problem.Is their any dynamic approach or so for doing it?

Given an array A of n numbers we can perform 3 operations on its array elements.Their are n operations in total and ith operation is to be applied on elements from ith index to last element of the array.

1.Reverse(R) : Reverse the elements from A[i..n]
2.Add(A) : Add X to each element from A[i..n]
3.Multiply(M) : Multiply Y to each element from A[i..n]

Note : In 2nd and 3rd operation all calculations done modulo Z.

I need to find final array after nth operation is done.

EXAMPLE : Say n=3 and array has 3 elements [1,1,1] and lets X=2 ,Y=3 , Z=1000 .If sequence of operation is ARM which means 1st operation is Add,2nd operation is Reverse and 3rd one is Multiply.Then resultant array after final operation will be [3,3,9].

I was needed to calculate this array in efficient manner in c++/java

Given an undirected graph with n vertices and m edges. How to check for perfect matching in the graph.(Perfect matching means each vertex has degree 1).Provide a code in c++.

Calculate number of DISTINCT palindromic substrings in a string with help of suffix array or a trie.
Like if aba is string the their are 3 distinct palindromic subsrings:{a,aba,b}

I want to calculate number of DISTINCT palindromic substrings in a string.How to do it?
Like if aba is string the their are 3 distinct palindromic subsrings:{a,aba,b}
length of string could be 10^5 range.So i dont think O(n^2) solution will work.So interviewer wanted some better algorithm.

I want to calculate number of DISTINCT palindromic substrings in a string.How to do it?
Like if aba is string the their are 3 distinct palindromic subsrings:{a,aba,b}
length of string could be 10^5 range.So i dont think O(n^2) solution will work.So the interviewer required some better algorithm.But i know only O(n^2) one.

I want to calculate number of DISTINCT palindromic substrings in a string.How to do it?
Like if aba is string the their are 3 distinct palindromic subsrings:{a,aba,b}
length of string could be 10^5 range.So i dont think O(n^2) solution will work.So plz help