bansal.cool
BAN USERwhats brillant in this?? he is counting no. of nodes.
even atre that he is calling getRank, which can go be n worst case (n). this s for every emlment so complexoty s o(n^2).
once you have no. of nodes you can just do inorder traversal till n/2.
in for loop, in else case , I guess it should be
if ( i < n-1 ){
root= root->next[s[i+1]-'a'];
}
in while loop , i should be incremented.
let me know, if i am not correct.
in for loop, in else case , I guess it should be
if ( i < n-1 ){
root= root->next[s[i+1]-'a'];
}
in while loop , i should be incremented.
let me know, if i am not correct.
in for loop, in else case , I guess it should be
if ( i < n-1 ){
root->root->next[s[i+1]-'a'];
}
in while loop , i should be incremented.
let me know, if i am not correct.
2*LOG(N) IN WORST Case
A^n = a^N/2 *A^N/2 (N EVEN)
A^N = A^N/2* A^N/2*A (N IS ODD)
1) t(N) = T(N/2) +1 FOR EVEN
2) T(N) = T(N/2) +2 FOR ODD
for worst case we need to consider the 2nd case.
assuming number is power is like somwthing like 2^n -1 then after divison
power will always be odd.
so, t(n) = 2 + t(n/2)
t(n/2) = 2+ t(n/4)
t(n/4) = 2+ t(n/8)
t(n)= 2+ 2 +2 +..
--------------------
(log(n) steps)
t(n) = 2log(n)
bool isPathExists(Node *root,int N)
{
if(root==NULL)
return(N==0);
else
return isPathExists(root->left,N-root->data)||isPathExists(root->right,N-root->data);
}
1
\
3
call this with isPathExists(root, 1) and it will return true. but there is no such path actually.
bool isPathExists(Node *root, int N)
{
return tree(root, 0, N);
}
bool tree(Node *root , int sum, int N)
{
if ( root->left == NULL && root->right ==NULL)
{
if ((sum+root->value) == N)
return true;
else
return false;
}
sum = sum + root->value;
if (tree(root->left, sum, N) == true)
return true;
else if (tree(root->right, sum, N) == true)
return true;
else
return false;
}
correct solution can be this:
void convert2matrix(node *root, node *parent){
if(root != NULL)
{
if(parent != NULL)
{
memcpy(matrix[root->data], matrix[parent->data], n*sizeof(int));
matrix[root->data][parent->data] = 1;
}
convert2matrix(root->left, root);
convert2matrix(root->right, root);
}
}
basically, copy the parent data . and just set matrix[root][parent] = 1;
you fogrot to have Null check in step-2.
Amazone always looks for boundary conditions too.
what if node->random is null ???
node->random->next can not be done.
rt ???
basically replace W in mayank's solution with N.:)
- bansal.cool July 24, 2010