Programming Problems 2

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.

Advertisements

About Avi Dullu
Jaako rakhe saiyan, maar sake na koi!

5 Responses to Programming Problems 2

  1. Amar says:

    1. Without manipulating the node structure, i will have to think upon it.
    I appreciate the variety of questions …. 🙂

  2. Roger says:

    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.

  3. anton says:

    what is the solution for problem 4 and 5?

  4. Sandipan says:

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: