Given an array of integers.....
Imagine it as a pyramid as below:

a[]={1,2,3,4,5,6,7,8,9,10}
1
2 3
4 5 6
7 8 9 10
find a path from level 1 to last level such that the sum is maximum.... The path is such that its children should be reachable.
Ex:
1,2,5,9 is a path
1,2,6,10 is not a path since 6 is not reachable from 2.
The array is not sorted and numbers are random.

int sumPath(int[] a, int i){
int length = a.length();
int n = child(i);
if(n+1 < length)
return a[i] + max(sumPath(n), sumPath(n+1));
else if(n < length)
return a[i] + sumPath(n);
else
return a[i];
}

int child(int i){
// function returns #out for a given #in
//example (in,out) pairs: //(0,1), (1,3) (2,4), (3,6), (4,7), (5,8), (6,10), (7,11) etc.
return (1 + sqrt((double)(8*i + 1))) / 2;
}

It works just like a tree, heap in particular, where nodes are stored in a, say a zero based array and its children are accessed by 2i+1 and 2i+2. in case of a pyramid, inner nodes have two parents. so the function to determine children is slightly different.

And sumpath is just like any recursion tree algo, say to find maxdepth at a node.

Q. No. :

2

Question :

A n-tree where each node contains any no of nodes. Print the nodes in level order and each level must contain a line with a gap

Take two queues Q1, Q2
//each time in any queues only the nodes belong to one level will be present
//hence print all the queue nodes and print new line
enque root into Q1

while Q1!=empty
print node->data and enque the childs of all nodes in Q2

print("\n");
now process Q2,
while Q2!=empty
print node->data;
enque childs of each node in Q1.

print("\n");

if(Q1.empty() and Q2.empty())
break;//we have processes whole tree.

Q. No. :

3

Question :

Write a program to arrange numbers from 1 to 16 such that the sum of two consecutive numbers is a perfect square

Solution must end or begin with 16 since there is only one number in the rest of the list that sums to a perfect square with 16 so it can't be between two of the other numbers.

So you can start with 16 in one list of numbers and the remaining numbers 1-15 in another list and solve it recursively. The following code works and comes up with the solution

class SolutionFinder
{
public static void find(final LinkedList remaining, final LinkedList found)
{
if (remaining.size() == 0) // We made it through the whole list, this is a solution
{
for (final Integer curr : found)
{
System.out.printf("%d ", curr);
}
}
else
{
for (int i = 0; i < remaining.size(); i++)
{
final Integer next = remaining.get(i);
if (Arrays.asList(4, 9, 16, 25).contains(found.get(found.size() - 1) + next))
{
found.add(remaining.remove(i));
find(remaining, found);
remaining.add(i, found.remove(found.size() - 1));
}
}
}
}

public static void main(final String[] args)
{
final LinkedList remaining = new LinkedList();
final LinkedList found = new LinkedList();
for (int i = 1; i <= 15; i++)
{
remaining.add(i);
}
found.add(16);
find(remaining, found);
}
}

Q. No. :

4

Question :

If you have a N steps staircase and you are standing at 1 step now you have options to step up to 2step or you can skip one step and go to 3rd step... so at ith step you have a option to go to i+1 step or i+2 step. So how many ways you can climb the stairs?

The algorithm outlined below solves the longest increasing subsequence problem efficiently, using only arrays and binary searching. For the first time this algorithm was developed by M. L. Fredman in 1975. It processes the sequence elements in order, maintaining the longest increasing subsequence found so far. Denote the sequence values as X[1], X[2], etc. Then, after processing X[i], the algorithm will have stored values in two arrays:

M[j] — stores the position k of the smallest value X[k] such that k ≤ i (note we have k ≤ j ≤ i here) and there is an increasing subsequence of length j ending at X[k]
P[k] — stores the position of the predecessor of X[k] in the longest increasing subsequence ending at X[k].

In addition the algorithm stores a variable L representing the length of the longest increasing subsequence found so far.

Note that, at any point in the algorithm, the sequence

X[M[1]], X[M[2]], ..., X[M[L]]

is nondecreasing. For, if there is an increasing subsequence of length i ending at X[M[i]], then there is also a subsequence of length i-1 ending at a smaller value: namely the one ending at P[M[i]]. Thus, we may do binary searches in this sequence in logarithmic time.

The algorithm, then, proceeds as follows.

L = 0
for i = 1, 2, ... n:
binary search for the largest positive j ≤ L such that X[M[j]] < X[i] (or set j = 0 if no such value exists)
P[i] = M[j]
if j == L or X[i] < X[M[j+1]]:
M[j+1] = i
L = max(L, j+1)

The result of this is the length of the longest sequence in L. The actual longest sequence can be found by backtracking through the P array: the last item of the longest sequence is in X[M[L]], the second-to-last item is in X[P[M[L]]], etc. Thus, the sequence has the form

..., X[P[P[M[L]]]], X[P[M[L]]], X[M[L]].

Because the algorithm performs a single binary search per sequence element, its total time is O(n log n).

Q. No. :

6

Question :

Given a binary tree, find a path (from root to a leaf) which gives maximum value by adding values of nodes.

use hashtable where key is the unique link and its value is the count. so if you get a new in bound check if it already exits if does then increment the value by one else add it to the hashtable with count 1

Q. No. :

8

Question :

You have millions of documents numbered 1,2,3,4,5 ......
You also have a mapping from a word to the list of documents that contains it

Find all the 'pair of words' that occur together in one and only document

It can be done in O(m+n)/O(Max(m,n)) time complexity and O(m*n bits).
We can calculate a BitMap for the given work by setting all the bits corresponding to each file(number). This BitMap will take O(m) space. The BitMap of both words can be compared in o(1) time (any weird insane comparison). The space requirement can be further scaled down by using base + offset value for any BitMap(can be done based on the range of the file index)

Q. No. :

9

Question :

Given n number of points in space and a point P, find 3 nearest point to p.

On first look, this problem appears to be quite simple. Indeed, the solution is possible through a very simple approach: Find the largest of the set, eliminate it and again find the largest of the remainder of the elements.

#include

#define MAXELT 10001

void main()
{
int i=-1,n=0,largest,slargest;
char t[10];
void largest_and_second_largest(int[],int,int&,int&);
int list[MAXELT];

do { //read the list of numbers
if (i!=-1)
list[i++]=n;
else
i++;
printf("\nEnter the numbers ");
gets(t);
if (sscanf(t,"%d",&n)<1)
break;
} while (1);

printf("The largest of the list is %d and the second largest is %d.",largest,slargest);
}

//pre: there must be atleast two numbers in the list
void largest_and_second_largest(int list[],int n,int &largest,int &slargest)
{
int largeindex=0,i;
largest=list[0];
for (i=1;i
if (list[i]>largest) {
largest=list[i];
largeindex=i; //to eliminate the largest later
}
//we have found the largest, stored in largest and its
//index stored in largeindex. Now find the second largest
//ignoring the largest.
if (largeindex==0)
slargest=list[1];
else
slargest=list[0];
for (i=0;i
if (list[i]>slargest && i!=largeindex)
slargest=list[i];
//we have found the second largest
}

Q. No. :

11

Question :

For a given matrix NxN having 0 or 1’s only. You have to find the count of rows and columns where atleast one 1 occurs.

1) Initialize row_count = 0
2) For each row.
a) Do OR of all elements in the row.
b) If OR is 1 then increment the row_count

Similarly, we can count columns with at least one 1.

Time Complexity: O(n^2)
Extra Space: O(1)

Time complexity can be reduced for average case performance of O(n). Worst case will be O(n**2)

Hint: Check all the rows, but need not check all the columns.

Q. No. :

12

Question :

You are provided with a max heap of 'n' elements with a number 'x' and 'k'...You have to find whether 'k' elements in heap are greater than 'x' or not??
Time Complexity should be O(k)

Use a DFS kind of approach. Terminate the recursion at a node when the value is less than or equal to 'x'. Keep incrementing the counter during the procedure. As soon as you encounter the value of counter as 'k' return true, else, when the DFS is complete and still counter<'k' return false.

Answer 1.
Total ways of placing 3 squares on the 8 x 8 grid is 64c3
Total ways in which all 3 squares are diagonal to each other are:
1st and 2nd diagonal rejected becoz in this there are less than 3 squares.
In the remaining diagonals the possible ways are 3c3, 4c3, 5c3, 6c3, 7c3, 8c3
All the ways are repeated again except 8c3.
Similar set of ways are their when we start from lower left corner.
So total number of ways are 2*( 2*(3c3+4c3+5c3+6c3+7c3) + 8c3) = 392
Hence the probability = 392/64c3.

Answer 2.
Total ways of placing squares such that they are adjacent and diagonal to each other are:
From the diagonal with 3 places = 1
......................... with 4 places = 2
.............................. with 5 places = 3
Hence total ways are 2*( 2*( 1 + 2 + 3 + 4 +5) + 6 ) = 72
Hence the probability would be = 72/64c3

Q. No. :

15

Question :

Given a binary tree and a node, print all the ancestors of that node.

The mutex is similar to the principles of the binary semaphore with one significant difference: the principle of ownership. Ownership is the simple concept that when a task locks (acquires) a mutex only it can unlock (release) it

Q. No. :

17

Question :

ind the two nodes in Binary Tree which have longest distance between them.

/*The second parameter is to store the height of tree.
Initially, we need to pass a pointer to a location with value
as 0. So, function should be used as follows:

int height = 0;
struct node *root = SomeFunctionToMakeTree();
int diameter = diameterOpt(root, &height); */
int diameterOpt(struct node *root, int* height)
{
/* lh --> Height of left subtree
rh --> Height of right subtree */
int lh = 0, rh = 0;

/* ldiameter --> diameter of left subtree
rdiameter --> Diameter of right subtree */
int ldiameter = 0, rdiameter = 0;

if(root == NULL)
{
*height = 0;
return 0; /* diameter is also 0 */
}

/* Get the heights of left and right subtrees in lh and rh
And store the returned values in ldiameter and ldiameter */
ldiameter = diameterOpt(root->left, &lh);
rdiameter = diameterOpt(root->right,&rh);

/* Height of current node is max of heights of left and
right subtrees plus 1*/
*height = max(lh, rh) + 1;

All the numbers are positive to start with.Now, For each A[i], Check the sign of A[A[i]]. Make A[A[i]] negative if it's positive. Report a repetition if it's negative.Finally all those entries i,for which A[i] is negative are present and those i for which A[i] is positive are absent.

Q. No. :

19

Question :

Given a set of 1 Trillion integers on hard disk, find the smallest 1 million of them. You can fit at most 1 million integers in memory at a time. State the fastest solution you can think of

Here k=1 million
1) Build a Min Heap MH of the first k elements (arr[0] to arr[k-1]) of the given array. O(k)
2) For each element, after the kth element (arr[k] to arr[n-1]), compare it with root of MH.
a) If the element is greater than the root then make it root and call heapify for MH
b) Else ignore it.
O((n-k)*logk)
3) Finally, MH has k largest elements and root of the MH is the kth largest element.

Time Complexity: O(k + (n-k)Logk) without sorted output. If sorted output is needed then O(k + (n-k)Logk + kLogk)

Q. No. :

20

Question :

Given a graph's shortest path algorithm, how can you make use of it to find the second shortest path?

Let s be the source and d be the destination node in the graph G.
1) Find the shortest path between s and d using the given shortest path algo.
Let the shortest path be s ->v1->v2->v3->...vn->d.
2) For each link in set (s->v1, v1->v2, v2-v3, ..... vn->d):
a) break the link in G and get the shortest path of the remaining graph.
b) Add the broken link back.
3) Return the minimum of all shortest paths calculated in step 2.