saraks.kumar
BAN USERRecursively calculate the number of changes to be made.
If it is an AND node and the value required is 1, sum the changes to be made in the left and right subtree
If it is an AND node and the value required is 0, return the minimum of the left subtree to return 0 or the right subtree to return 0.
If it is OR node and the value required is 0, return the sum of changes to make the left and right subtree 0.
If it is OR node and the value required is 1, return the minimum of changes to make the left or right subtree 1.
and so on. Hope it makes sense to someone :)
Even a[3][3] = {1, 4, 5
2, 6, 8
3, 7, 10} is an example of that array for which the above algorithm wouldn't work.
XOR of a1 to an = XOR of b1 to bn doesn't mean a1..an = b1..bn. Fails for
int arr1[] = {1, 1, 2, 2, 3, 3, 4, 4};
int arr2[] = {3, 4, 4};
XOR of a1 to an = XOR of b1 to bn doesn't mean a1..an = b1..bn. FAils for
int arr1[] = {1, 1, 2, 2, 3, 3, 4, 4};
int arr2[] = {3, 4, 4};
I mean't big-O
- saraks.kumar November 07, 2009Yes I left the sibling by mistake and assumed that all the siblings are initialized as NULL to start with(which I should've mentioned). I think your solution is right, as we have to use the parent's siblings to get the next level sibling instead of left or right child of the parent node. Thanks for correcting.
- saraks.kumar November 06, 2009If both have the same length, the nodes are compared starting from node 1 and so on. Since (x+1)th nodes in both lists are equal, they will be compared and kept track from that point onwards. Not sure why would that not work.
- saraks.kumar November 06, 2009The following modification will prevent the free being called twice. But this method will only work when there is a loop in the list.
void delete(Node* curr)
{
Node* next - curr-->next;
if(!next)
{
return;
}
curr->next = NULL;
delete(next);
free(curr);
}
Is there a o(n) method to find where the loop occurs in a linked list?
- saraks.kumar November 06, 2009We sever the connection and keep proceeding onto the subsequent nodes, freeing the nodes after their children are freed.
void delete(Node* curr)
{
Node* next - curr-->next;
curr->next = NULL;
delete(next);
free(curr);
}
It is a real number, hence we can safely discard the hash option.
- saraks.kumar November 01, 2009Is an incomplete tree(red-black tree) be considered balanced as well, say the difference between maximum and minimum height can be max 1? I wrote the following code for such a scenario, aka checking the correctness of red-black tree
void next(Node* curr, int currHeight, int* maxHeight, int* minHeight)
{
if(curr == NULL)
{
if(curr >= *maxHeight)
{
*maxHeight = curr;
}
else if(curr > *minHeight)
{
*minHeight = curr;
}
if(!minHeight && ((*maxHeight - *minHeight) > 1))
{
printf("Unbalanced tree");
}
}
if(curr->left)
next(curr->left, currHeight+1,maxHeight, minHeight);
if(curr->right)
next(curr->right, currHeight+1, *maxHeight, *minHeight);
}
void setNext(Node* curr, Node* prev)
{
if(curr->left)
{
if(curr->right)
{
curr->left = curr->right;
}
else
{
if(prev && prev->right)
{
if(prev->right->left)
{
curr->right->next=prev->right->left;
}
else
{
curr->right->next = prev->right->right;
}
}
}
setNext(curr->left, curr);
}
if(curr->right)
{
if(prev && prev->right)
{
if(prev->right->left)
{
curr->right->next=prev->right->left;
}
else
{
curr->right->next = prev->right->right;
}
}
setNext(curr->right, curr);
}
}
Initial call will be setNext(head, NULL);
The tree is considered to be unbalanced tree and the logic used is every node's right child's next pointer will be point to the parent's right child's left node. If next sibling is not present we look for the subsequent sibling. Hope it makes any sense.
Form a binary tree with the first array and search for the elements of the second array?
- saraks.kumar October 11, 2009The first element is always 0
- saraks.kumar October 09, 2009For 70 71 72 76 2 19 22, we get the sequence
0 1 1 4 -74 17 -3
The sequence for which the sum is max here is 17, which corresponds to 2-19.
Max subsequence sum => http://wordaligned.org/articles/the-maximum-subsequence-problem
Find the different between the i+1 th number and number and get the maximum subsequence sum for this array. The bounds which give the maximum sum should be the buy and sell price.
- saraks.kumar October 03, 2009
Keys is to find the most efficient way to do it. This is a variation of the edit distance problem with the cars looking ABCD_ in the case of P1 and say BDAC_ in the case of P2.
- saraks.kumar January 29, 2010