new2011
BAN USER- 0of 0 votes
AnswersYou have given 2 array. You need to find whether they will create the same BST or not.
- new2011
For example:
Array1:10 5 20 15 30
Array2:10 20 15 30 5
Result: True
Array1:10 5 20 15 30
Array2:10 15 20 30 5
Result: False| Report Duplicate | Flag | PURGE
Vizury Software Engineer / Developer Algorithm
<pre lang="" line="1" title="CodeMonkey88220" class="run-this">1. Find the Maximum root to leaf node path while keeping the leaf node O(n).
2. Print the root to leaf node path using this leaf node. O(n)
It works for negative numbers also.
void findMaxSumLeaf(Node *root, Node ** leaf, int curSum, int *sum){
if(root == NULL)
return;
curSum = curSum + root->data;
if(root->left == NULL && root->right == NULL){
if(curSum > *sum){
*sum = curSum;
*leaf= root;
}
}
findMaxSumLeaf(root->left, leaf, curSum, sum);
findMaxSumLeaf(root->right, leaf, curSum, sum);
}
void printRootToLeafHelper(Node* node, Node * leaf) {
int path[1000];
printRootToLeaf(node, leaf, path, 0);
}
void printRootToLeaf(Node* node, Node * leaf, int path[], int pathLen) {
if (node==NULL) return;
path[pathLen++] = node->data;
if (node == leaf && node->left==NULL && node->right==NULL)
printArray(path, pathLen);
else {
printRootToLeaf(node->left, leaf, path, pathLen);
printRootToLeaf(node->right, leaf, path, pathLen);
}
}
void printArray(int arr[], int len) {
int i;
for (i=0; i<len; i++)
printf("%d ", arr[i]);
}
</pre><pre title="CodeMonkey88220" input="yes">
</pre>
Note the first value whether it is even or odd.
Scan the list.
While scanning, if the item is of the first element type, then put this element to next to the that item, otherwise skip it.
Complexity: O(n)
No other data structure used.
Only one type of (lets say evens) elements will be shuffled.
public void seperateEvenOddNumber(List root){
if(root == null){
return;
}
List n1, n2;
n1 = n2 = root;
int val = root.value;
int firstValueType = val%2;
root = root.next;
while(root != null){
val = root.value;
if(val % 2 == firstValueType){
if(n1.next == root){ //If its adjacent, just move.
n1 = n2 = root;
root = root.next;
}
else{ // Shuffle & update the pointers
n2.next = root.next;
root.next = n1.next;
n1.next = root;
n1 = root;
root = n2.next;
}
}
else{
n2 = root;
root = root.next;
}
}
}
For example: 2->4->5->8->10->11
2->4->5->8->10->11
2->4->5->8->10->11
2->4->8->5->10->11
2->4->8->10->5->11
2->4->8->10->5->11
@Ashish, I think you are trying to say n & (n-1)
- new2011 June 14, 20118 = 1000
7 = 0111
& = 0000
Means if a number's all bits are 1, then doing the AND operation with previous number (number - 1) will result in zero.