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, right1);
}
Else if (left!=0 & right!=0)
{
if (left == right)
{printf("(");
generatecomb( left  1, right);
}
else if (left < right)
{printf("(");
generatecomb(left1, right);
printf(")");
generatecomb(left, right1);
}
}
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;
}
}

camSun
April 19, 2011 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?
Open Chat in New Window
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