# Programming Problems 2

October 1, 2009 5 Comments

**1.Print Siblings**

Problem is to find print all the nodes at the same levels of a binary tree.Inputs given are root pointer and the pointer to the node (let it be A)whose level elements need to be printed

**2. Pairwise Sum **

If pairwise sums of ‘n’ numbers are given in non-decreasing order identify the individual numbers. If the sum is corrupted print -1

Example:

i/p:

4

4 5 7 10 12 13

o/p:

1 3 4 9

**3. Maximum Sum Sub-matrix**

Given a integer matrix of size m*n. We need to find a sub matrix with the largest sum.

**4. Sort the Stack **

Given a stack S, write a C program to sort the stack (in the ascending order).

**5. Tree Sum **

Given a tree and a sum, write an algorithm to return TRUE if there is a path from the root node down to a leaf such that adding all values of the nodes along the path equals the given sum.

**6. IsRotation in 1 statement **

Given a string s1 and a string s2, write 1 statement to say whether s2 is a rotation of s1?

i.e. printf( (<code_here>?”YES\n”:”NO\n”);

**7. Tricky Merge **

Given a array of size M+N in which first M numbers are sorted and last N spaces are vacant. Another array of size N which is sorted. Now merge these two arrays without using any extra space so that the array of M+N size is sorted. Optimize it to hav complexity M+N.

1. Without manipulating the node structure, i will have to think upon it.

I appreciate the variety of questions …. 🙂

Solution for Problem#2:

Basic checks can be performed to check for validity: Number of pairwise sums is n*(n-1)/2

The validity of the solution is also governed by the solution itself.

Lets assume that there are 4 numbers: a,b,c,d

Then, the possible pairwise sums are (4 * 3/2 = 6):

a + b

a + c

a + d

b + c

b + d

c + d

Adding all the pairwise sums yields nothing but the total of the pairwise sums:

(a+b) + (a + c) + (a + d) + (b + c) + (b + d) + (c+d) = 3 * (a+b+c+d) = (n-1) * ( total of individual numbers) = total of pairwise sums

Now 3 (a + b + c + d) = 4 + 5 + 7 + 10 + 12 + 13

Therefore, a + b + c + d = 51/3 = 17

Now:

(a + b) = 17 – (c+d)

(a + c) = 17 – (b + d)

(a + d) = 17 – (b + c)

and so on

So basically for each pairwise sum –> check that 17 – (pairwise sum) also exists and this is solution.

if we have a,b,c,d,e,…

then

a+b= sum -(c+d+e+…..)

so then??????????//

what is the solution for problem 4 and 5?

It is not necessary that the sum will also appear in the orderly manner

a + b

a + c

a + d

b + c

b + d

c + d

like this !!