Avinash
BAN USERFlawless code ... Enjoy!!
Time O(n) .... Space O(1)
Below code also takes care of multiple space characters between two words...
void removeWords(char * str, char ch)
{
if(!str)
return;
int i = 0, j = 0;
while(str[j])
{
if(str[j] == ch)
{
while(str[j] && str[j] != ' ')
j++;
while(str[j] && str[j] == ' ')
j++;
}
else
{
while(str[j] && str[j] != ' ')
str[i++] = str[j++];
while(str[j] && str[j] == ' ')
str[i++] = str[j++];
}
}
str[i] = '\0';
}

Avinash
September 19, 2012 Flawless Code...Enjoy!!!
Time O(n) ... Space (1)
Note: For simplicity I have not made these functions generic. After a little tweaking below code can sort list with 0 1 2 3 also.
Here we go:
void append(node* &head, node* &tail, node* n)
{
if(!head)
head = n;
else
tail>next = n;
tail = n;
}
void join(node*& a, node*& alast, node* b, node* blast)
{
if(!a)
{
a = b;
alast = blast;
}
else if(b)
{
alast>next = b;
alast = blast;
}
}
int sort123(node* &head)
{
if(!head)
return 1;
node* start[3] = {NULL,NULL,NULL};
node* end[3] = {NULL,NULL,NULL};
for(node* n = head; n; n = n>next)
{
int index = n>data;
if(index < 0  index > 2)
return 1;
append(start[index],end[index],n);
}
head = start[0];
node* tail = end[0];
join(head,tail,start[1],end[1]);
join(head,tail,start[2],end[2]);
tail>next = NULL;
return 0;
}

Avinash
September 13, 2012 First of all, thanks for pointing out the Time complexity... Below goes the code with O(n) ...
Secondly, there is nothing to laugh about NULL check. What if caller passes a NULL pointer ( acceptable in C++ )?
O(n) code...
void putZerosInFront(int arr[], int len)
{
if(!arr  len < 1)
return;
int i = len1;
for(int j = i1; j >=0; j)
{
if(arr[i] == 0)
{
if(arr[j] != 0)
{
swap(arr[i],arr[j]);
i;
}
}
else
{
i;
}
}
}

Avinash
September 12, 2012 Flawless code... Enjoy!!!
Time O(n) ... Space(1)

Keep two pointers, one at lower end another at higher end ... similar when doing it for sorted array.

I am using stack for simplicity of the algorithm, but you can use Morris traversal to achieve Space(1)... If you are not able to figure out to do it with Morris traversal, then let me know. I can provide the code for that too... but that would be a bit complex to understand... so better right your own :) ....
Here we go..... CHEERS!!!
void findPair(node* root, int sum, int &a, int &b)
{
a = 1;
b = 1;
// Base case '0' or '1' node in tree.
if((!root)  (!root>left && !root>right))
return;
node* n1 = root, *n2 = root;
stack<node*> p,q;
while(true)
{
if(n1)
{
p.push(n1);
n1 = n1>left;
}
else if(n2)
{
q.push(n2);
n2 = n2>right;
}
else if(!p.empty() && !q.empty())
{
n1 = p.top();
n2 = q.top();
// tree is already traversed
if(n1>data > n2>data)
return;
int cur_sum = n1>data + n2>data;
if(cur_sum == sum)
{
// found desired numbers
a = n1>data;
b = n2>data;
return;
}
else if(cur_sum < sum)
{
// move in forward direction
p.pop();
n1 = n1>right;
n2 = NULL;
}
else
{
// move in backward direction
q.pop();
n2 = n2>left;
n1 = NULL;
}
}
else
return;
}
}

Avinash
September 11, 2012 Open Chat in New Window
Using a constant hash table...Here you go...
 Avinash September 20, 2012