camSun
BAN USERalthough it works for ur example...i agree it would work for all cases.
a O(nlogn) solution would be to divide the array into 2 euqal halfs and recurse on those half and also check if i lie in the first part and j lies in the second part.
the running time owudl be T(n) = 2T(n/2) + n
therefore O(nlogn)
could anyone think of O(n) solution?
int romanTOinteger(const char *s)
{
int value = 0;
while (s!=NULL)
{
switch(*s)
{
case 'X':
value+=10;
break;
case 'V':
value+=5;
break;
case 'I':
if (*(s+1) == 'X')
{value+=9;
s++;
}
else if (*(s+1) == 'V')
{value+=4;
s++;
}
else
value+=1;
break;
}
s++;
}
return value;
}
- camSun May 02, 2011i think normal recursive inorder traversal will do with slight modification...before printing the left child, we must put a parenthesis and after printing the right child we must put a closing parenthesis.
run time is O(n)
for non recursive inorder...do morris tree traversal
void generatecomb(int left, int right)
{
If (left==0 & right==0)
{
Printf(ā\nā);
Return;
}
Else if (left==0 & right!= 0)
{
Printf(ā)ā);
Generatecomb(left, right-1);
}
Else if (left!=0 & right!=0)
{
if (left == right)
{printf("(");
generatecomb( left - 1, right);
}
else if (left < right)
{printf("(");
generatecomb(left-1, right);
printf(")");
generatecomb(left, right-1);
}
}
1)let a curr pointer points to the first node on level i..
and let temp2,temp1 pointers point to the first node on level i+1...
2)temp2->next points to the next child of a node from level i. Assuming temp2,temp1 are pointing to the left child of curr (which is in level i). Now temp2->next will point to the right child of current. temp2->next = curr->right; temp2 = temp2->next;
3) curr pointers increments as curr = curr->next until the last node of level i whose next pointer is NULL. After that curr points to temp1 which is used to bookkepp the first node at level i+1
(remember, the next pointers of nodes in level i are already pointing to their cousins/siblings.)
did i make myself clear??
it can be done without using queues.
Here is my solution
void makepointers (node* root)
{
node *curr, *temp1, *temp2;
curr = root;
curr->next = NULL;
int a = 0;
while (curr->left != NULL && curr->right != NULL)
{
a = 0;
while (curr)
{
if (curr->left !=NULL)
{
if (a == 0)
{
temp1 = temp2 = curr->left;
temp2->next = NULL;
a = 1;
}
else
{
temp2->next = curr->left;
temp2 = temp2->next;
}
if (curr->right!= NULL)
{
temp2->next = curr->right;
temp2 = temp2->next;
}
}
else if (curr->left == NULL)
{
if (curr->right!=NULL)
{
if (a == 0)
{
a = 1;
temp1 = temp2 = curr->right;
temp2->next = NULL;
}
else
{
temp2->next = cur->right;
temp2 = temp2->next;
}
}
}
curr = curr->next;
}
temp2->next = NULL;
curr = temp1;
}
}
diff b/w c++ and java
garbage collection
code once run anywhere
no use of pointers..no problem of dangling pointers...no c++ kind of memory leaks
no problems of multiple inheritance
no dynamic memory allcoation problems
large number of standard packages
diff b/w overriding and overloading
overriding: base and derived class have same function signature
overloading: difference functions with same name and return type but with different no. and or types of arguments
void printpath(struct node* root, int* path, int length)
{
if (root == NULL)
{printarray(path, length);
return;
}
if (root->left == NULL and root->right==NULL)
{
printarray(path,length);
return;
}
path[length] = root->value;
printpath(root->left, path, length+1);
printpath(root->right, path, length+1);
return;
}
first case: 1 byte so that no two objects have the same address in the memory
second case: since it has a virtual function, the compiler will add a virtual table and a virtual pointer...but since each class has one virtual pointer per class and not per object, the size of the object should still be 1 bytes...
any suggestions?
your time complexity is O(nlogn) as at each node you look is the elements are present in the left subtree or the right subtree....
- camSun May 16, 2011