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 !!