gevorgk
BAN USERBuffer overflow will cause stack demage and crush.
Returning adress of local variable can cause unexpected behaviour, because after function return the memory can be oerwritten by some ohter routine. So the correct function shall look like this
char * copy(char *p)
{
char* buf = new char[strlen(p)];
//copy algo[I skipped code here]
return buf;
}
//returns -1 if not found
int maxRepeatedElement(int arr[], int size)
{
if( size <= 0)
return -1;
int count = 0;
int elem;
for (int i = 0; i < size; ++i)
{
if (count == 0)
{
elem = arr[i];
count = 1;
}
else if (elem == arr[i])
{
++count;
}
else
{
--count;
}
}
count = 0;
for(int i = 0; i < size; ++i)
{
if (arr[i] == elem)
{
++count;
}
}
if (count > size/2)
{
return elem;
}
return -1;
}
Ok, let me exlplain better. Question says wether there a ANY 2 leaf nodes, which differ by more than 1 level.
We will find the leaf with Min depth, and leaf with max depth. If the deifference is more than 1 - it means that we have at list one such pair. If difference is less than or equal to 1 - it means than there will be no such pairs, because the difference between min and max is largest one.
Question says a very few things about the tree. It doesn't say wether the tree is sorted, wether the resulted tree have to be balanced etc. So assuming taht tree is not BST and the resulting tree shall not be balanced, the solution is just att the root of one tree as child to any leaf of another. I don't think that amazon could ask such a stupid question.
- gevorgk May 27, 2010BTW, not clear what are you doing with "1"s.
Here is the correct version
void sort012( int V[] , int sz )
{
int *p0 = V;
int *p1 = p0 + 1;
int *p2 = V + sz-1;
int *pend = p2;
while(p0 != pend && p1 < p2)
{
if( *p0 == 0 )
{
++p0;
if( p0 == p1 )
{
++p1;
}
}
else if(*p0 == 1)
{
swap(*p0, *p1);
++p1;
}
else
{
swap(*p0, *p2);
--p2;
}
}
return;
}
If they are not sorted, you definetely can't do it better tha O(nLogN)...
Another question is that did you understood the problem correctly.
What do tou mean by intersection ? Is there two distinct lists and you have to find comon elements ? Or you have two lists wich have some cmmon node at some point, and you have to find it ?
hmm, than you can do it with O(n) with no extra space.
Just maintain to pointers
char* copyFrom and char*copyTo, both initialized at the beginning of the string. Iterate both by copying from copyFrom to copyTo. If copyFrom reaches "..", move copyTo pointer back till next "\".
This will be exactly O(n) with no extra space.
1. Create two sorted arrays by inorder traversing two trees - linear time
2. Merge two sorted arrays - linear time
3. Build BST from sorted array
Last step can be done in linear time by taking root node from the middle of array, and calling taking left and right chilfren recursively from left and right sub-arrays.
So the overall complexity is O(n)
I belive that these two lists are sorted. Than we need to implement the modification of MERGE procedure on them
Node* SortedIntersection(Node *l1, Node *l2)
{
if (l1 == NULL || l2 == NULL)
{
return NULL;
}
Node* head = NULL;
if (l1->Value == l2->Value)
{
head = new Node(l1->Value);
head->Next = SortedIntersection(l1->Next, l2->Next);
}
else if(l1->Value > l2->Value)
{
Node* next = l2->Next;
delete l2;
head = SortedIntersection(l1, next);
}
else if(l1->Value < l2->Value)
{
Node* next = l1->Next;
delete l1;
head = SortedIntersection(next, l2);
}
return head;
}
Node* SortedIntersection(Node *l1, Node *l2)
{
if (l1 == NULL || l2 == NULL)
{
return NULL;
}
Node* head = NULL;
if (l1->Value == l2->Value)
{
head = new Node(l1->Value);
head->Next = SortedIntersection(l1->Next, l2->Next);
}
else if(l1->Value > l2->Value)
{
Node* next = l2->Next;
delete l2;
head = SortedIntersection(l1, next);
}
else if(l1->Value < l2->Value)
{
Node* next = l1->Next;
delete l1;
head = SortedIntersection(next, l2);
}
return head;
}
pretty obvious
void printArr(int* arr, int size)
{
for(int i = 0; i < size; ++i)
{
cout << arr[i];
}
cout << endl;
}
void fun(int n, int* out, int level)
{
if(n==0)
{
printArr(out, level);
}
if( n < 2 )
{
return;
}
out[level] = 2;
fun(n-2, out, level+1);
if( n >= 3 )
{
out[level] = 3;
fun(n-3, out, level+1);
}
}
Yes, substring can be found with O(n) by using KMP algo
- gevorgk June 03, 2010