ramblersm
BAN USERMy function logic below might seem a little complicated at first but upon going through some test cases, you should be able to get it.
eg-
initial tree:
1
/ \
2 6
/ \
3 7
/ \
4 5
final tree:
1
\
2
\
3
\
4
\
5
\
6
\
7
static *var , c=1; //these two static variables are used to keep track of the actual root node
void modtree(root)
{
if (root==null)
return;
if (c==1) //upon first call, we get the root node and store it's location for later use
{
var=root;
c=0;
}
modtree (root->left); // an inorder traversal begins
if (root!=var) //if this current node is not the root node of the original tree
{
if (root->left!=null) // cases: where current node has only a left child or both left or right ch.
{
if(root->right=null) //only a left child: bring the child to right of the current node
{ root->right=root->left;
root->left=null;
}
else //both children of current node present
{
root->left->right=root->right; //make the right child , the right child of the left child of
//current node
root->right=root->left; //make the left child the right child of the current node
root->left=null;
}
}
}
else //case when the current node is the root node; when this step is
// reached, the left and right sub-trees of the root node will be right-
// aligned
{
tmp=root->left;
while(tmp->right!=null) // reach the last child of the left sub-tree
tmp=tmp->right;
tmp->right=root->right; //attach the right subtree of the root node to the right of the last
//child of left sub-tree
root->right=root->left; //make the left sub-tree the right child of the root node; we will
//have a degenerate right-aligned linked list. this is the final step.
root->left = null;
}
modtree(root->right);
}
If sorting is done in increasing order: start with the top rightmost element and if current-value < element to search, move down, and if current-value> element to search move left. Continue this till one of the index values become negative(that is you have moved out of the array).
Similar approach will be used for decreasingly sorted array.
Just as you said, it is " similar to minimum swaps to convert string A to string B." so would we be given the string B in this case, which is "we must go to newyork now"?
1. If yes, then the decisive solution is same as conversion of string A to string B which takes some help from the Longest Common Sub-sequence dynamic prog problem.
2. If no, then I don't see if there is any decisive solution..
We are asked for a time efficient code, not a space efficient one. We can hence use another new string of same length as the given string. Then traverse the given string from right end and keep inserting the values in the new string in forward direction. Time complexity: O(n).
I don't know what they tested by asking this elementary question.
Could someone explain why it should be a binary tree?
I think it will be a general tree , because with every fork(), the previous running process should get a child process.. so 'main' process(root of our tree) should have 4 children and so on...which is the only way we get a total of 16 nodes-> 16 processes. And we cannot decide the order of 1s and 2s.. it will depend on the CPU scheduling..
Amazing and clever! haha! :D
- ramblersm April 27, 2014