Microsoft and Google Interview Questions

The following questions were asked in Microsoft and Google interviews.

1) You are given with two arrays A and B.
A has integers unsorted.
B has the same length as A and its values are in the set {-1,0,1}
You have to return an array C with the following processing on A.
If B has 0 then C must have A
If B has -1 then A must be in C within the sub-array C[0] - C[i-1] i.e. Left sub array
If B has 1 then A must be in C within the sub array C[i+1] - C[length(A)] i.e. right sub array.
If no such solution exists then print "no solution"

2) consider a binary tree, Policemen is to be placed such that for each edge of the tree, there is a policemen on at least one side of each edge.
Tell the minimum no. of policemen and their location. (time-O(N)).

3) You are given an expression like (a+ ((b+c)))..... Here extra braces are provided on b+c... i mean like (b+c) is ok... bt ((b+c)) is not as it contains redundant braces. So for a given expression you have to find whether expression contains redundant braces or not.....
(a+(b+c) )is ok and (a+((b+c)) contains redundant one. can we solve by counting number of operands ,number operators and number of braces. Using stack can we solve this problem?

4) Prove that number of prime numbers is infinite. I.e. there is no an upper limit after which prime number doesn't exist. Prove that.


5) See the below matrix.
a b c d
e f g h
i j k l
m n o p

here we define a term contiguous.
(a,b) are contiguous.
(a,e) are contiguous.
(a,f) are contiguous.
Butt (a,j) are not contiguous.

You are given an N X N matrix/array with distinct values.
You are also given m values. Now u have to detect in above provided array that whether these m values r contiguous or not.

Like in above matrix.
abcd are contiguous.....
bfjn are contiguous.....
bfkh are contiguous.....
cfjg are contiguous.....
dlpk are not contiguous.....
I.e. m values are contiguous if u can reach all m values.

 

(Source: Orkut)