Are you a maniac of programming?

1.Given a sorted array A, how will you find out elements in that array (a,b,c) such that the sum of the squares of a and b is the square of c? You need to do it in O(n^2)
2.Asked in 1st and 2nd interview at campus placement at IIIT Gwalior.

8 x 8 char array is provided with random letters. You have to tell if a given string occurs.

eg

String to find = "computer"

Array[] = {
b b b b b b b b
b b b c b b b b
b b o b b b b b
b b b m p b t b
b b b u b u b e
b b b t b b b r
b b b e b b b b
b b b r b b b b
}

ans:possible

3.There are n petrol bunks arranged in circle. Each bunk is separated from the rest by a certain distance. You choose some mode of travel which needs 1litre of petrol to cover 1km distance. You can't infinitely draw any amount of petrol from each bunk as each bunk has some limited petrol only. But you know that the sum of litres of petrol in all the bunks is equal to the distance to be covered.ie let P1, P2, ... Pn be n bunks arranged circularly. d1 is distance between p1 and p2, d2 is distance between p2 and p3. dn is distance between pn and p1.Now find out the bunk from where the travel can be started such that your mode of travel never runs out of fuel. DO it in linear time...

4.Propose a tree based data structure to identify a node with nth rank with maximum efficiency .

5. How will you find the first k smallest elements in a given unsorted array in O(n) at the worst case?

6.A 2D array is such that each row in it is in ascending order and each column is in ascending order. How will you search for an element in this array? (O(n) is enough)

7.A tree is represented in a matrix form such that A[i,j] = 1 if j is the ancestor of i. Otherwise A[i,j] = 0. Given this construct a normal binary search tree.