CareerCup

I agree with mike. Hash table + doubly link link will do all. Plus bit modification that we dont have to traverse whole DLL to get unique users as retrieval should be as fast as possible.
Here is my approach

1) At each node, there will be total unique visitors till that time since start of server
2) At time of user addition, check if user exists in hash map, and if exist then update its time to current time. and based on difference between lasttimeaccess of user and current time, node's counter will be updated.
3) At time of retrieval, count will be : (count at head - count in last 11th min node).

Update of list will be at time of addition and at time of retrieval.
Update can be done on 1 min timer also.

time_list
{
	time_t *nodeTimel
	int totalCount;
	time_list *next;
	time_list *prev;
}
map<userid, time_list*> users;
addUser (userid)
{
	node = users[userid];
	cur = time(NULL)
	oldest = node->nodeTime;
	if ( (cur - last) > (10*60) )
	{
		node = incrementUserCount(cur);
	}
	users[userid] = node;
}
time_t *head = NULL, * rear=NULL;
time_list * incrementUserCount (updatetime)
{
	if (!head)
	{
		head = new time_list;
		head->count = 1;
		head->next = NULL;
		head->prev = NULL;
		rear = head;
	}
	else
	{
		if (head->node_time == updatetime)
		{
			head->count += 1;
		}
		else
		{
			//Assuming always newest time entry will come
			node = time_list; 
			node->count = 0; 
			node->next = NULL;
			node->prev = NULL;

			//Keeping cumulative sum since start
			node->count += head->count;
			head->next = node;
			node->prev = head;
			head = node;

			//check if to remove old entries
			//keeping window of 11 minute entries
			while ( (updatetime - rear->node_time) > ( 11 *60 ) )
			{
				//removing rear node;
				temp = rear;
				rear=rear->next;
				remove (temp);
			}
		}
	}
	return head;
}

//it may possible there was no logging many windows
int getTotalCount ()
{
	cur = time(NULL);
	//getting last 11th min node
	lasttime = cur - 11*60;
	while (rear->node_time < lasttime)
	{
		temp = rear;
		rear=rear->next;
		remove (temp)
	}

	if (rear->time < lasttime)
	{
		return (head->count - rear->count)
	}
	else
	{
		return head->count;
	}

}

Yes, max repeat characters should be N-(N/M+1) = (N)* (M / (M+1))
So if repeated characters are greater than N * M / (M+1), then there will be no solution.

For second part in which similar digits remains in the end, we can continue like circular array.
I mean end part of array for similar digits can be replaced with digits in initial part of array.

output should be like:
1,2,1,1,3,1,4,4,5,4

Can you please explain output. Do we need to remove excess integers from output or we have to reposition them ??
As what 4 is doing in the end of output?

your solution will return half result, only returning K distance nodes below given node.
Other half (and bigger problem) include K distance nodes above to given node.

See me solution below for reference.

1) Each node will receive some values from left subtree and from right subtree.
2) That node will change its value with : selfvalue + sum of value received from right subtree
3) That node will return new pair of values to its parent: < sum of left subtree value, node's new value >
I can explain algo with an example:

left assume following BST:
		41
	40			50
39			45		55

node 40 will return <39, 40>
node 50 will return <45, (50+55)> -- <45, 105>
node 41 will receive left pair<39, 40> and right pair <45, 105>
node 41 will change -- 41 + right pair --> 41 + 45 + 105 -->191
node 41 will return <sumofleftpairvalue + newsumeofcurrentnode> -- <(39+40), 192> -- <79,192>

this will continue

sudo code:

pair<int, int> updateBst (tree *root)
{
	if (!root)	return <0,0>
	if (leafnode) return <0, root->key>

	leftpair = updateBst (root->left)
	rightpair = updateBst (root->right)

	root->key += rightpair.first + rightpair.second;
	return < (leftpair.first+leftpair.second) , root->key>
}

take var=1. then multiply var with 5 each time as long as number is less than given number.
Take remainder of number and again apply same above step.

int remainder (int a)
{
        int mask = 1;
        while ( (mask * 5) <= a )
        {
                mask *= 5;
        }
        return (a - mask);
}

void remainderOfFive (int a)
{
        int rem = a;
        while (rem >= 5)
        {
                rem = remainder (rem);
        }
        if (rem == 0)
                cout << a << " is Multiple of 5" << endl;
        else
                cout << a << " Not Multiple of 5" << endl;
}

As a optimisation, distance from left subtree leaf node can be used in case arbitrary node is found in right subtree.
If remaining distance from arbitrary node is greater than size of left subtree, then left subtree need not to be traversed.

This problem can be divided into two parts:

1) All nodes K distance away from arbitrary node in arbitrary node's subtree.
2) All nodes K distance away from arbitrary node above to this arbitrary node.

First part is quite easy.

void kdistanceNodes (tree *root, int K)
{
	if (root)
	{
		if (K == 0)
		{
			print << root->key;
		}
		kdistanceNodes (root->left, K-1);
		kdistanceNodes (root->right, K-1);
	}
}

when arbitrary node is found
1) process all K distance node in its subtree
for second part,
2) if arbitrary node is not found, at every node, keep distance from leaf node in left subtree and from leaf node in right subtree
3) if arbitrary node is found, at every node, keep distance from arbitrary node from either of subtree and then search for remaining other subtree (K - distance from arbitrary node)

pair<bool, int> printKNodes (tree *root, int depth, int node, int K)
{
	if (!root) return make_pair(false, 0);
	if (K < 0) return make_pair(false, 0);

	/*If Node found, then print all nodes at K distance in subtree*/
	if (node == root->key)
	{
		if (K == 0) {print node, return <true, 1>}
		kdistanceNodes (root->left, K-1)
		kdistanceNodes (root->right, K-1)
		return <true, 1>
	}
	else
	{
		pair<bool, int> left = printKNodes (root->left, depth+1, node, K)
		/*If node is found in left subtree and current node is still <=K nodes away from arbitrary node */
		if (left.first == true && left.second <= K)
		{
			if (K - left.second == 0)
			{
				print root->key
			}
			else if ( (K - left.second) > 0)
			{
				/*remaining distance from arbitrary node to right subtree via this root*/
				kdistanceNodes (root->right, (K - left.second - 1) )
			}
			return <true, left.second+1> //pair
		}
		pair<bool, int> right = printKNodes (root->right, depth+1, node, K)
		/*If node is found in right subtree and current node is still <=K nodes away from arbitrary node */
		if (right.first == true && right.second <= K)
		{
			if (K - right.second == 0)
			{
				print root->key
			}
			else if ( (K - right.second) > 0)
			{
				/*remaining distance from arbitrary node to left subtree via this root*/
				kdistanceNodes (root->left, (K - right.second - 1) )
			}
			return <true, right.second+1> //pair
		}
		/*If arbitrary node has not been found return total depth from leaf node*/
		int biggerSubtree = (left.second > right.second) ? left.second : right.second;
		return <false, biggerSubtree+1>
	}
}

Copied from reply section in this post itself

We can do within queue with little modification in your algo..
1) mark end of every queue with a marker...
2) process data of one queue in one iteration and keep data from 2nd queue just as it is in queue
3) Q2 sorted data will go into Q1 in one iteration
4) Repeat above with queue reversal
5) Now, Q1 sorted data will go into Q2
6) swap Queue's data

QueueSort (queue Q1, queue Q2)
{
	Q1 end marker: q1_end
	Q2 end marker: q2_end

	Q2.enqueue (q2_end);

	//Push all data from Q1 to Q2
	while ( !Q1.empty() )
	{
		Q2.enqueue (Q1.dequeue() );
	}
	//put end marker for Q1's data
	Q2.enqueue (q1_end);

	//sort Q2's data into Q1
	while (1)
	{
		small = e = Q2.dequeue ();
		//process till Q2's end marker is not reached
		while (e != q2endmarker() )
		{
			//remember smallest element and keep enqueuing rest of Q2 element in Q2 itself
			e = Q2.dequeue();
			if (e < small)
			{
				Q2.enqueue (small)
				small = e
			}
			else
				Q2.enqueue (e)
		}
		//again mark queue end
		Q2.enqueue (q2_end)

		//put smallest Q2's element in Q1
		Q1.enqueue (small)

		//Simply Dequeue and enqueue back Q1's all element into Q2
		e = Q2.dequeue()
		while (e != q1endmarker()) )
		{
			Q2.enqueue (e)
			e = Q2.dequeue ()
		}
		//again mark queue end
		Q2.enqueue (q1_end)
	}
	remove q1_end and q2_end from Q2
}
//after this function, Q2 is sorted in Q1

Function (Queue Q1, Queue Q2)
{
	QueueSort (Q1, Q2);
	QueueSort (Q2, Q1);
	//Swap elements of both queue's. Function not implemented
	swapQueue (Q1, Q2);
}

this will sort data of 2 queues into single queue.
I guess question says to sort queues data in that queue itself...

We can do within queue with little modification in your algo..
1) mark end of every queue with a marker...
2) process data of one queue in one iteration and keep data from 2nd queue just as it is in queue
3) Q2 sorted data will go into Q1 in one iteration
4) Repeat above with queue reversal
5) Now, Q1 sorted data will go into Q2
6) swap Queue's data

Algo below

@i059069:
You are using: Queue1, Queue2 and tempQueue ??
There is no tempQueue in question !!!

create and array of structure of Months of size 30.
parse the table, according to product & month update corresponding entry

after complete parsing, print the result for all non-zero entries from 1st product to 30th product.

Make sure to keep entry in lexicographic order

first largest height tree will mask tree of similar height or smaller height.

Iterate array
1) 1st tree will always be visible. Print it. Make it largest height
2) Find next largest height in the input. Print it. Now make it largest height
repeat step 1 & 2 until array ends

Modification of binary search

int checkKey (int s, int e, int mid, int a[], int key)
{
        if (a[s] == key)
                return s;
        if (a[e] == key)
                return e;
        if (a[mid] == key)
                return mid;
        return -1;
}

int find (int a[], int s, int e, int k)
{
        if (s > e)
                return -1;
        int mid = s + (e -s)/2;
        int i = checkKey (s, e, mid, a, k);
        if (i != -1)
                return i;

        if (s == e || mid == s)
                return -1;

        if (k > a[mid])
                s = mid+1;
        else
                e = mid-1;
        return find (a,s,e,k);
}

Algo
Post order traversal

1) if null node, return (0, true)
2) if leaf node, then return (level, true)
3) call each subtree with level+1;
4) at any node, if level return by either subtree is non-zero and not equal , then return false.
5) at any node, if either subtree level is zero, return (non-zero level, true)

pair<int, bool> leafLevel (tree *root, int level)
{
	if (!root)
	{
		return make_pair(0, true);
	}
	if (leaf_node)
	{
		return make_pair(level, true);
	}
	pair<int, bool> leftT, rightT;
	leftT = leafLevel (root->left, level+1);
	if (leftT.second == false)
		return make_pair (-1, false);

	rightT = leafLevel (root->right, level+1);
	if (rightT.second == false)
		return make_pair (-1, false);

	if (leftT.first == 0 || rightT.first == 0)
	{
		int level = (leftT.first != 0) ? (leftT.first):(rightT.first);
		return make_pair (level, true);
	}
	if (leftT.first == rightT.first)
	{
		return make_pair (level, true);
	}
	else
	{
		return make_pair (-1, false);
	}
}

@bob: why using another data structure.
It is just parsing string.
Whenever '(' comes, increment count and after incrementing check for max.
When ')' decrement count.

Assumption: we do not need to check all open and close brackets ...

tree* searchLeftmostnodeInRightSubtree (tree* root)
{
        while (root->left)
        {
                root = root->left;
        }
        return root;
}

tree* inorderSuccessor (tree *root, int key)
{
        if (root)
        {
                if (root->key == key)
                {
                        /*inorder successor will be in right subtree of node if right subtree exist*/
                        if (root->right)
                        {
                                tree *subtree = searchLeftmostnodeInRightSubtree(root->right);
                                return subtree;
                        }
                        /*If right subtree of this node doesnot exist, then parent node for which leftsubtree consist this node*/
                        else
                        {
                                return root;
                        }
                }
                tree *left = inorderSuccessor (root->left, key);
                if (left)
                {
                        /*if immediate child is key*/
                        if (left->key == key)
                        {
                                return root;
                        }
                        /*tree is returning correct value*/
                        return left;
                }
                tree *right = inorderSuccessor (root->right, key);
                return right;
        }
        return NULL;
}

Code according to above algorithm

typedef struct doubly_link_list dll;

struct doubly_link_list
{
        char key;
        dll *prev;
        dll *next;
};

class DLL
{
        dll *head;
        dll *tail;

        public:
        DLL ()
        {
                head = tail = NULL;
        }

        dll *append (char c)
        {
                dll *node = new dll;
                memset (node, 0, sizeof(dll));
                node->key = c;
                node->next = NULL;
                node->prev = NULL;

                if (!head)
                {
                        head = tail = node;
                }
                else
                {
                        tail->next = node;
                        node->prev = tail;
                        tail = node;
                }
                return tail;
        }
        void remove (dll *node)
        {
                if (!node)
                {
                        cout << "Bluffff" << endl;
                        return;
                }

                if (head == node)
                {
                        head = head->next;
                }
                else
                {
                        node->prev->next = node->next;
                        if (node->next)
                        {
                                node->next->prev = node->prev;
                        }
                }
                delete node;
        }

        dll *top()
        {
                return head;
        }
};

void first_non_repeating_char (char input[], size_t size)
{
        DLL d_list;
        vector< pair<bool, dll*> >hash;
        hash.reserve(256);

        pair<bool, dll*> vectorInit(false, NULL);
        hash.insert(hash.begin(), 256, vectorInit);

        for (int i = 0; i < size; i++)
        {
                if (hash[ input[i] ].first == false )
                {
                        hash[ input[i] ].first = true;
                        hash[ input[i] ].second = d_list.append(input[i]);
                }
                else
                {
                        if (hash[ input[i] ].second)
                        {
                                d_list.remove (hash[ input[i] ].second);
                                hash[ input[i] ].second = NULL;
                        }
                }
        }

        dll *result = d_list.top();
        if (result)
        {
                cout << "First Non_repeating character in array:" << input << " is: " << result->key << endl << endl;
        }
        else
        {
                cout << "No Non_repeating character in array: " << input << endl << endl;
        }
}

this code can be trimmed more but with loss of clarity:

void modify_subtree (tree *root, tree *new_ptr_addr)
{
        tree *right = root->r_child;
        root->r_child = root->l_child;
        new_ptr_addr->r_child = right;
}

tree *convert_to_preorder(tree *root)
{
        if (root)
        {
                tree *left = convert_to_preorder(root->l_child);
                tree *right = convert_to_preorder(root->r_child);
                if (left)
                {
                        modify_subtree (root, left);
                }
                if (right)
                {
                        return right;
                }
        }
        return root;
}

void modify_subtree (tree *root, tree **new_ptr_addr)
{
        tree *right = root->r_child;
        root->r_child = root->l_child;
        *new_ptr_addr = right;
}

tree **convert_to_preorder(tree *root)
{
        if (root)
        {
                tree **left = convert_to_preorder(root->l_child);
                tree **right = convert_to_preorder(root->r_child);

                if (!left && !right)
                {
                        return &(root->r_child);
                }

                if (left)
                {
                        modify_subtree (root, left);
                }

                if (right)
                {
                        return right;
                }

                else
                {
                        return &(root->r_child);
                }
        }
        return NULL;
}

idea is like:
for leaf node, address of right child is returned
for non-leaf node, if left subtree exist then it has returned a address that address should not point to right of this node & node's right should point to node's left.
if for non-leaf node, left subtree doesnot exist, do nothing/
for non-leaf node, if right subtree exist then this right subtree must have returned a address that address should be returned 
for non-leaf node, if right subtree does not exist, then address of right child should be returned

@ Anonymous:
in input of : <2,3> <4,1> <1,5> <2,6> <3,-12>
on first iteration you will not get sum of 4, you will get sum 1 as you are not taking <2,3> in summation.
Similarily, when encountered with <1,5> u will miss this pair while calculating <2,6>

@justhack4fun688: So question is like: Given a graph G, is it possible to get a perfect matching out of this Graph?
Did I get the question right?

void perfectmatch (vector<int> V, vector< pair<int,int> > E)
{
        vector<int>::iterator vit;
        map<int, bool> vmap;
        for (vit=V.begin(); vit!=V.end(); vit++)
        {
                vmap[*vit] = false;
        }

        vector< pair<int,int> >::iterator pairit;
        for (pairit=E.begin(); pairit!=E.end(); pairit++)
        {
                int first = pairit->first;
                int second = pairit->second;

                cout << "pair: " << first << " " << second << endl;

                if (vmap[first] == false)
                {
                        vmap[first] = true;
                }
                else
                {
                        cout << "Not A Perfect Match: Culprit Edge " << pairit->first << "," << pairit->second << endl;
                        vmap.clear();
                        return;
                }

                if (vmap[second] == false)
                {
                        vmap[second] = true;
                }
                else
                {
                        cout << "Not A Perfect Match: Culprit Edge " << pairit->first << "," << pairit->second << endl;
                        vmap.clear();
                        return;
                }
        }
        map<int, bool>::iterator mapit;
        for (mapit=vmap.begin(); mapit!=vmap.end(); mapit++)
        {
                if (mapit->second == false)
                {
                        cout << "Not A Perfect Match: Culprit Vetex:" << mapit->first << endl;
                        return;
                }
        }
        cout << "Perfect Match" << endl;
}

@justhack4fun688
If you say that degree of node is 1, it means that there will be only 1 edge on that node, but in your example, there will be 3 edges on each node.
By your given definition of perfect matching, there should be 1 edge only.

glebstepanov1992 is right. But @glebstepanov1992: graph is not given in form of adjacency matrix and we dont need to create a adjacency matrix.

perfectMatch(vector<int>V, vector< pair<int,int> E>)
1) create map<int, bool>
2) For each vector element, add entry into map and make is false.
3) for each edge, check if incident node of edge are marked false in map if yes then mark them true. If any of them is marked true, then there is no perfect match.
4) If all edges pass successfully, then we will check map, if there is any node which is false, if yes then again there is no perfect match. As this node has 0 incident edge.
5) If we reach here there is a perfect match

If given list is:

(1, 2), (1, 3)
(2, 4), (2, 5)
(3, 6), (3, 7)

Given list can be converted into adjacency list:

1 --> 2, 3
2 --> 4, 5
3 --> 6, 7
4 -->
5 -->
6 -->
7 -->

On this list, we can run DFS / BFS to find we there is any revisit on a node. If a node is revisited then there is a loop else no loop.

@zahidbuet106
thanks buddy,,,, I understood activity selection problem and then this one. :)

@zahidbuet106
why do we need to sort it based on second element only. We can do sorting based on first element also and follow rest of your approach. Whats wrong in that ??

1) Find the depth of the node, say h
    2) Now, take a pointer nodePtr. Start doing DFS upto that level. Initialize nodePtr will NULL.
    3) We get a node, Nh at level h, store it into nodePtr
    4) get another node on level h, but this is not given node, then store this new node in nodePtr.
    5) While repeating step 4, we will come to a point where we have a node N which is stored in nodePtr and just next node in the DFS on that hight h is given node, print this nodePtr node. This is left node of given node.
    6) in next iteration, we will get right node of given node.

int minIndex (int *arr, int size)
{
        int low = 0;
        int mid = (size/2);
        int high = size-1;

        while (low<high)
        {
                if (arr[mid] > arr[mid+1])
                        return mid+1;
                if (arr[mid-1] > arr[mid])
                        return mid;
                if (arr[low] < arr[high])
                        return low;
                if (arr[low] < arr[mid])
                {
                        low = mid+1;
                }
                else if (arr[low] > arr[mid])
                {
                        high = mid-1;
                }
                mid = low + (high-low)/2;
        }
}

This seems the best :)

Pre process dictionary:
      While inserting each word, sort the word & add it to trie according to this sorted word. & store the actual word.
      When anagram for a word is to be find, just sort the word & lookup into trie. You will find list of words there.
      Complexity will be O(nlogn) in worst case which will be of sorting word to be searched but as the words can't be too long, this should not be the issue.

int a[4][5] = {
                        {1,  2,  3,  4, 5},
                        {14,  15,  16,  17, 6},
                        {13,  20,  19,  18, 7},
                        {12,  11,  10,  9, 8},
                        };

void print_spiral (int r, int c)
{
        int i = 0;
        int j = -1;
        int right_max = c;
        int down_max = r;

        int left_min = -1;
        int up_min = 0;

        int total_count = r * c;

        while (total_count > 0)
        {
                i = up_min;
                j++;
                while (j < right_max && total_count > 0)
                {
                        printf ("%d \n", a[i][j]);
                        j++;
                        total_count--;
                }
                right_max--;

                j = right_max;
                i++;
                while (i < down_max && total_count > 0)
                {
                        printf ("%d \n", a[i][j]);
                        i++;
                        total_count--;
                }
                down_max--;

                i = down_max;
                j--;
                while (j > left_min && total_count > 0)
                {
                        printf ("%d \n", a[i][j]);
                        j--;
                        total_count--;
                }
                left_min++;

                j = left_min;
                i--;
                while (i > up_min && total_count > 0)
                {
                        printf ("%d \n", a[i][j]);
                        i--;
                        total_count--;
                }
                up_min++;
        }
}
int main ()
{
        print_spiral(4, 5);
}

This can be done but with recursion.
I hope doing it recursion will count it as one iteration :)
I have used _ in place of space( ) for clarity.
Point me out for any wrong assumptions.

#include "stdio.h"
#include "string.h"

void swap (char *a, char*b)
{
        char t;
        t = *a;
        *a = *b;
        *b = t;
}

void moveSpace (char *str, char **lastSpace)
{
        if (*str == '\0')
        {
                return;
        }

        moveSpace(str+1, lastSpace);
        if (*lastSpace != NULL)
        {
                if (*str != '_')
                {
                        swap (str, *lastSpace);
                        (*lastSpace)--;
                }
        }

        if (*lastSpace == NULL)
        {
                if (*str == '_')
                        *lastSpace = str;
        }
}

void printResult (char *tar, const char *src)
{
        char *last = NULL;
        strcpy (tar, src);
        printf ("Original String: \"%s\"\n", tar);
        moveSpace (tar, &last);
        printf ("New String: \"%s\"\n\n", tar);
}

int main ()
{
        char str[20] = {0};

        printResult (str, "abc_dce__fg__");
        printResult (str, "abc_dce_fg");
}

Problem statement says that query can be for last second, last minute or last hour. We have to maintain list for each window.

My Solution:
--> Maintain a list of seconds, minutes, hour of size 60, 60 & 1 respectively.

Now, basically we have to run two operations:
1) Update all three array when user logs in.
2) Update all three array after each second. (All three array need not to be updated per second)

So array will be like:
second[60] = {0,0,0,0...0}
minute[60] = {0,0,0,0...0}
hour[24] = {0}

Now 1st operation: (Simple)
Whenever any user logs in, increment each arrays' 0th index. 0th index will always point to the last second, minute, hour.

Now 2nd operation:
Keep updating newest & keep outdating oldest index values. This can be done by timeout operation. Timeout value is 1 sec:

1) At each second:
    i) 60th node of array is removed & 0th node is added to second's array. (Not for initial 60 second when only insertion operation required) 
    ii) value of 60th node of second array is subtracted from 0th node of minutes array.(Not for initial 60 second)
2) At each 60th second, a new node with value of current node is inserted at the start of minute array. Now, minute array has 2 node
    i)  1st node will have value of 0th minute. (initial value of this node is same as old 0th node)
    ii) 2nd node will have value of 1st minute.
3) At each 60th min,
     i ) 60th node of minute array is removed & 0th node is inserted
     ii) hour index will be subtracted with 60th minute index value.

In above solution, I have taken array but all operation has been described as link link operation (insert & remove) for sake of simplicity.
So either we can take array of link list or these operation can be done like rotating array. We need to keep start & end index for each array.

@prashanthreddy: question clearly states that characters will be of english alphabet, so we can assume, you wont get special characters.

@sgarg: this solution should be extended to resolve this issue.

1) We prepare a new ordering list of alphabets based on 1st character of new dictionary. Also will keep count for number of characters found.
2) If number of characters are less than 25, then we should continue the same process for second alphabet. This time for only those string which has same matching first character.
3) During step 2, we may found new characters which must be in between of existing list, so list should be updated accordingly.
4) If after 2 & 3 steps, we still lacks required number of characters, then same 2 & 3 steps should be repeated but this time for 3 character of strings whose 1st two characters are same.

Repeatedly doing this until we get all characters.

simply we can also keep on summing all odd numbers till we get desired num. If sum ends up with given number then it is perfectly square number otherwise if sum exceeds given number, number is not perfectly square and will return false.

all Square numbers are:
1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289

If we see the difference among these numbers, following figure we get:
3, 5, 7, 9, 11, 13, 15, 17, 19, 21

So, you see, every consecutive square number is Arithmetic progression. So if we can add number of this series to get desired result.
Complexity will be O(sqrt(n))
As in case of square root of 25, we need 5 iteration of addition.

bool perfectSqr (int value)
{
        int odd = 1;
        int a = 0;
        while (a < value)
        {
                a += odd;
                if (a == value)
                        return true;
                odd += 2;
        }
        return false;
}

@whateva
u don't need to go upto leaf node in case your sum from root to current is greater than or equal to K. From this node, u can return with guarantee that your aim is achieved after this subtree.

@aka:
thanks for pointing out.
I forgot to add null check for root in recursion :(
updated the code with changes

I have run it for the following test cases:

int a[] = {-1,-2,1,3,11,-10,-3,1,-9,2,11,13,-11,25};
      int a[] = {10,11,-15,-20,2,3,-7,15,30,-1,10,-1,30};
      int a[] = {-20,-30,-40,-2,-9,-13};
      int a[] = {-20,-30,-40,-1,0,-9,-13};
      int a[] = {3,4,-3,1,-2,1,-1,-1,-1,-1,-1};
      int a[] = {3,4,-3,1,-2,25,-1,-1,-1,-1,-1};

Update me for other tricky cases :)

Divided algo in few parts:
part 1:
1) get minimum negative value
2) get first positive sum of array
3) get start & end index of first positive sum
this will be current running sum
part 2:

1) get sum of all negative values
 2) get sum of all positive values
 3) compare current_sum with curr_sum + positive_sum + negative_sum
    if max_sum < (curr_sum + positive_sum + negative_sum)
        update max_sum
    else
        update curr_sum
    if max_sum < positive sum
        update max_sum with positive sum
4) also keep on updating indexes

I have written code, due to keep track of index, code has become little messy
please update me with compact code, if u have

void maxSubSeq (int *a, int n)
{
        int max = -1;
        int i = 0;
        int max_e_i = 0;
        int cur_s_i = 0;
        int cur_e_i = 0;
        int pos = 0;
        int neg = 0;
        int cur = -1;
        int max_s_i = -1;
        int l_n_v = -10000;
        int next_p_index = 0;
        int neg_i = 0;

        while (i < n)
        {
                if (a[i] < 0 && a[i] > l_n_v && cur < 0)
                {
                        l_n_v = a[i];
                        neg_i = i;
                        i++;
                        continue;
                }

                if (cur > 0 && a[i] < 0)
                        break;
                if (a[i] >= 0)
                {
                        cur = 0;
                        while (i < n && a[i] >= 0)
                        {
                                if (max_s_i < 0)
                                        max_s_i = i;
                                cur += a[i];
                                i++;
                        }
                        break;
                }
                i++;
        }
        if (cur >= 0)
        {
                max = cur;
                max_e_i = i-1;
        }

        while (i < n)
        {
                neg = 0;
                pos = 0;

                while (i < n && a[i] < 0)
                {
                        neg += a[i];
                        i++;
                }
                if (i < n)
                        next_p_index = i;

                while (i < n && a[i] > 0)
                {
                        pos += a[i];
                        i++;
                }

                if ((cur + neg + pos) > max)
                {
                        cur = max = cur+neg+pos;
                        cur_e_i = max_e_i = i-1;
                }
                else
                {
                        cur = cur+pos+neg;
                        cur_e_i = i-1;
                }
                if (max < pos)
                {
                        cur = max = pos;
                        cur_s_i = max_s_i = next_p_index;
                }
        }

        if (max == -1)
        {
                printf ("no Positive sum. Least negative value is: %d at index: %d\n", l_n_v, neg_i);
        }
        else
        {
                printf ("Max sum is: %d\n", max);
                printf ("Max SubSequence is: \n", max);
                for (i = max_s_i; i <= max_e_i; i++)
                        printf ("%d ", a[i]);
                printf ("\n");
        }
}

1) it wont work for all negatives in array
2) it wont work if max subarray will include negatives as you have not taken negative values into consideration. (example given above by parthi, {-6,2,-1,2,11} ). Here max should be 14, your code will return 13

Both iterative & recursive version :

int node_ceiling_iterative (tree *root, int value)
{
        if (!root)
        {
                return -1;
        }
        int result = -1;

        while (root)
        {
                if (value < root->key)
                {
                        result = root->key;
                        root = root->l_child;
                }
                else if (value > root->key)
                {
                        root = root->r_child;
                }
                else
                {
                        result = root->key;
                        break;
                }
        }
        return result;
}

void node_ceiling (tree *root, int value, int *result)
{
        if (!root)
        {
                return;
        }

        if (root->key > value)
        {
                *result = root->key;
                node_ceiling (root->l_child, value, result);
        }
        else if (root->key < value)
        {
                node_ceiling (root->r_child, value, result);
        }
        else
        {
                *result = root->key;
                return;
        }
}

time complexity will be O(n) as in worst case we will have to visit all nodes of the tree.
Space complexity will be O(log n) which is required for recursion.

Algo:
At any node, check if either of its children or both of its children has return true (got keys)
i) if both elements are found, then this current node is common ancestor. return current node
ii) if either of children has return true and this current node is another key then return this current node
iii) if either of children has return true & this current node is not another key, return NULL but update found pointer with true.

Function is called :
found = 0;
tree* node = commonAncestor (root, &found, f, s)

tree *commonAncestor (tree *root, int *found, int f, int s)
{
        if (!root)
                return NULL;

        if (root->key == f && root->key == s)
        {
                *found = 1;
                return root;
        }

        if (root->key == f || root->key == s)
        {
                *found = 1;
        }

        int left = 0;
        int right = 0;

        tree *ret = common (root->left, &left, f, s);
        if (ret != NULL)
                return ret;

        ret = common (root->right, &right, f, s);
        if (ret != NULL)
                return ret;

        if (left == 1 && right == 1)
        {
                *found = 1;
                return root;
        }

        else if (left == 1 || right == 1)
        {
                if (*found == 1)
                        return root;
                *found = 1;
                return NULL;
        }
        return NULL;
}

Modify version of your code which will take care of border cases also

void printParameter (tree *root, bool left, bool right)
{
        if (root)
        {
                if (left && !(!root->l_child && !root->r_child))
                        printf ("%d ", root->key);

                printParameter (root->l_child, left, false);

                if (!root->l_child && !root->r_child)
                {
                        printf ("%d ", root->key);
                        return;
                }

                printParameter (root->r_child, false, right);

                /*For satisfying condition that root should not be printed twice*/ 
                if (right && !left)
                        printf ("%d ", root->key);
        }
}

psuedocode:
1) preorder of left subtree only (including root but excluding leafs)
2) leafs of left subtree
3) leafs of right subtree
4) postorder of right subtree only (excluding leafs)

Code:

void specialPreorder (tree *root)
{
        if (root)
        {
                if (! root->l_child && ! root->r_child)
                {
                        return;
                }
                printf ("%d ", root->key);
                specialPreorder (root->l_child);
        }
}

void leaf (tree *root)
{
        if (root)
        {
                if (! root->l_child && ! root->r_child)
                {
                        printf ("%d ", root->key);
                        return;
                }
                leaf (root->l_child);
                leaf (root->r_child);
        }
}

void specialPostorder (tree *root)
{
        if (root)
        {
                if (! root->l_child && ! root->r_child)
                {
                        return;
                }
                specialPostorder (root->r_child);
                printf ("%d ", root->key);
        }
}

void perimeter (tree *root)
{
        if (!root)
                return;

        printf ("\n");
        specialPreorder (root);
        leaf(root->l_child);
        leaf(root->r_child);
        specialPostorder (root->r_child);
        printf ("\n");
}

1) pass sum of root to its children
2) compare at each level wether we have got desired sum
  {
    i) if yes, return true from that node
    ii) else check if node is leaf node
      {
       a) if its a leaf node & sum is not desired one return false
     }
   pass sum upto this node to left subtree
   if left subtree return false
      remove left subtree node
   pass sum upto this node to right subtree
   if right subtree return false
      remove right subtree node
   if either of subtree has return tree
      return true
   else
     return false

Code:

bool prunTree (tree *root, int sum, int K)
{
        if (!root)
            return false;
        if (root->key + sum >= K)
        {
                return true;
        }
        if (!root->left && !root->right && ((root->key + sum) < K))
        {
                return false;
        }

        bool l_ret = prunTree (root->left, (root->key + sum),  K);
        if (l_ret == false)
        {
                if (root->left)
                        free (root->left);
                root->left = NULL;
        }

        bool r_ret = prunTree (root->right, (root->key + sum),  K);
        if (r_ret == false)
        {
                if (root->right)
                       free (root->right);
                root->right = NULL;
        }

        if (l_ret == true || r_ret == true)
                return true;
        else
                return false;
}

void pruning (tree **root, int K)
{
        if (!*root)
                return;

        if ((*root)->key >= K)
                return;

        bool ret = prunTree (*root, 0, K);
        if (ret == false)
        {
                free (*root);
                *root = NULL;
        }
}