user221
BAN USERIdle Mind ...
My solution: timeO(N.LOG.N) && space  O(N)  its a recursive solution...
Excuse me for confusing shorthand names...
// void main function  entry  sort the given array in descending order & recurse...
void main_fn(){
a< sort_descending(A) //O(N.LogN)
k=10 // given sum
for(i=0 till (a.size)1)
print_correct_combination(a,i,[ ], k)
}
//helper function prints the right combination... time, space = O(N)
void print_correct_combination(Array a, int i, list out, int k){
if( k <=0  a[i] > k) return;
if(a[i[ <= k){
out.append(a[i];
k=a[i];
if(k==0) { print out; return; }
}
if (i==(a.size)1) return;
for(int index = i+1 till (a.size)1)
print_correct_combination(a, index, out, k)
}
output 
{7,3}
{7,2,1}
{5,3,2}

user221
August 24, 2013 Yes. The tree won't be unique. But, we can find one of the combinations , but if we use a queue in the levelorderlist we can get the same order as input.. (as below)  excuse me for any typo...
My Solution : n = O(2^h) space and time i.e., total nodes in the given tree..
Basically, represent the given LeveOrderTraversal as a Map<orderlevel, Queue> as follows  use two variables to iterate through the map levels (leaflevel && otherlevels  default starting at 0  representing the root) && use a stack to push the current root after each iteration...
Given levelorder:
*other>[0]a (ex..calling it as a,b,c for clarity..you can call as 1,1,.. leaf level as 0)
[1] b,c (ex..say each of these is a queue  we can get same order)
[2] d,e,f,g
*leaf> [3] h,i,j
Given: Input stream: 0111011101
Functions:
//caller function
while(int x: input) incomingnode(x);
// Function being called...
global vars: other=0, leaf=Map.mapIndex
void incomingnode(int node){
// first node being pushed is a leaf node
if(node==0 && stack.isEmpty()) stack.push(Map[leaf].dequeue())
else{
elem< Map[leaf].dequeue()
root<stack.pop()
bool done<insertleafatrightlevel(order,root, elem)
stack.push(root)
}
// if first incoming node is a nonleafnode  increase level by default
if(node==1 && stack.isEmpty) stack.push(Map[other++].dequeue())
else{
elem<Map[other].dequeue()
bool done < insertotheratrightlevel(order,root, elem)
if(Map[other].isQueueEmpty()) other++
}
}
helper functions:
// ILARL  short form for insertleafatrightlevel
bool ILARL(int order, node root, node elem){
if(root==null) return false
if (root.level+1 != order)
return(ILARL(order,root.left,elem)  ILARL(order, root.right, elem))
if(root.left==null) { root.left=elem; return true}
if(root.right==null) {root.right=elem; return true}
return false
}
//short name: IOARL  insertotheratrightlevel
bool IOARL (int order, node root, node elem){
if(root==null) return false
if(root.level+1 != order)
return(IOARL(order,root.left, elem)  IOARL(order,root.right,elem))
if(root.left == null) {root.left=elem; return true}
if(root.left.level==leaf){
elem.left=root.left
root.left=elem
return true
}
if(root.right==null) {root.right=elem; return true}
if(root.right.level==leaf){
elem.left=root.right
root.right=elem
return true
}
return false
}

user221
August 19, 2013 @rahuls496  I am still trying to get the question  could you pls answer the following questions 
so if i understand you correctly  we know the level of each node 
ex. if its a tree rooted at A, whose children are BC so forth  we know the following info (is this what you mean by tree level order traversal ?)
A  level 0
BC  level 1
DEF  level 2
and then we know that a leaf node is marked 0 and others are marked 1.
But, do we know which kind of traversal (ex. inorder, pre / post order ... if it is applicable..) .. pls let us know...
My Algorithm: Time O(N)  Idea: totally use 4 pointers to forsee the next 2 positive nos, and next 2 neg nos.. we can save those 4 values in temp variables  curr_pos, next_pos, curr_neg, next_neg (i.e, marked by 4 pointers  cur_pos_ptr, next_pos_ptr, cur_neg_ptr, next_neg_ptr respectively).. pls let me know your thoughts on this...
Then we can simply overwrite the original array (as these pointers will always be at an advanced index location.. so no extra space..
Full algo
// Set up the pos & neg pointers the first time (Ex. start from 1 index loc, and figure out these...)
index=0
cur_pos_ptr=next_pos_ptr=cur_neg_ptr=next_neg_ptr=index1
while(++cur_pos_ptr <0); curr_pos_num=a[cur_pos_ptr];
next_pos_ptr=cur_pos_ptr;
while(++nex_pos_ptr <0); nex_pos_num=a[nex_pos_ptr];
//Similarly find the (cur_neg_ptr & nex_neg_ptr)  and hence, the 2 next nos..just a reverse of the above logic.. use > instead of < ...
#EOA = End of array
Excuse me for confusing variable names...
Step 2:
while(cur_pos_ptr != EOA && cur_neg_ptr != EOA){
a[index++]=cur_pos_num;
cur_pos_ptr=nex_pos_ptr; cur_pos_num=next_pos_num;
while(++nex_pos_ptr <0);
if(nex_pos_ptr ! = EOA) next_pos_num = a[nex_pos_ptr]
a[index++] = cur_neg_num;
cur_neg_ptr=nex_neg_ptr; cur_neg_num=nex_neg_num;
while(++nex_neg_ptr);
if(nex_neg_ptr ! = EOA) nex_neg_num = a[nex_neg_ptr];
}
if(cur_pos_ptr == EOA)
while(cur_neg_ptr ! = EOA) a[index++] = a[cur_neg_ptr++];
return;
if(cur_neg_ptr == EOA)
while(cur_pos_ptr ! = EOA) a[index++] = a[cur_pos_ptr++];
return;

user221
August 12, 2013 My algorithm: Time  O (N LOG N) & Space O(N) .. please let me know your comments... it seems to work for all cases, let me know if I am missing something...
Approach:
(1) Sort the input in descending order of size  O(N LOG N)
(2) Use a stack based approach  O(N) : (find below)
Given:
A[] = {1,2,3,4,5}
b[]= {3,1,1,1,0}
Step 1: Sort A (and hence B) > A[] = {5,4,3,2,1} B= {0,1,1,1,3} // Here, this is still O(N.LOG N)
Step 2: Stack based algorithm (Say have 2 stacks: S1>stack.new, S2>stack.new)
for index in a:
if (s1.isEmpty())
s1.push(a[index])
continue
while(s1.size > b[index])
s2.push(s1.pop())
s1.push(a[index])
while(! s2.isEmpty()) s1.push(s2.pop())

user221
August 05, 2013 Open Chat in New Window
 user221 August 25, 2013