user221
BAN USERIdle Mind ...
My solution: time--O(N.LOG.N) && space -- O(N) -- its a recursive solution...
Excuse me for confusing short-hand 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}
Yes. The tree won't be unique. But, we can find one of the combinations , but if we use a queue in the level-order-list-- 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 Leve-Order-Traversal as a Map<order-level, Queue> as follows -- use two variables to iterate through the map -levels (leaf-level && other-levels -- default starting at 0 -- representing the root) && use a stack to push the current root after each iteration...
Given level-order:
*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) incoming-node(x);
// Function being called...
global vars: other=0, leaf=Map.mapIndex
void incoming-node(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<--insert-leaf-at-right-level(order,root, elem)
stack.push(root)
}
// if first incoming node is a non-leaf-node -- increase level by default
if(node==1 && stack.isEmpty) stack.push(Map[other++].dequeue())
else{
elem<--Map[other].dequeue()
bool done <-- insert-other-at-right-level(order,root, elem)
if(Map[other].isQueueEmpty()) other++
}
}
helper functions:
// ILARL -- short form for insert-leaf-at-right-level
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 -- insert-other-at-right-level
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
}
@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=index-1
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;
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 25, 2013