A Developer's Diary

Mar 31, 2012

Reverse the words of a string

Given a string My name is Antonio Gonsalves. You have to reverse all the letters of the words in the string so that the resultant string looks like yM eman si oinotnA sevlasnoG

int main()
{
    char str[] = "My name is Antonio Gonsalves", 
         *startPtr = str,
         *endPtr = str,
         *spacePtr;

    while(*spacePtr != '\0')
    {
        while(*endPtr != ' ' && *endPtr != '\0')
            ++endPtr;

        spacePtr = endPtr;
        endPtr = spacePtr - 1;
       
        char temp;
        while(startPtr < endPtr)
        {
            temp = *endPtr;
            *endPtr-- = *startPtr;
            *startPtr++ = temp;
        }
        
        startPtr = spacePtr + 1;
        endPtr = spacePtr + 1;
    }
    printf("%s\n", str);
    return 0;
}

$ ./a.out 
yM eman si oinotnA sevlasnoG

Difference between a char [] and char *

There is an important difference between the following two definitions:

char amessage[] = "Hello World"; /* an array */
char *pmessage  = "Hello World"; /* a pointer */

1. amessage is just an array, big enough to hold the sequence of characters and '\0'
2. amessage refers to the same memory location and cannot be changed
3. Individual characters within amessage can be changed

#include <stdio.h>
int main()
{
    char amessage[] = "Hello World from the C Program";

    amessage[0] = 'P';
    printf("%s\n", amessage);
    return 0;
}

1. pmessage is a pointer pointing to a string constant
2. The string constant "Hello World" is stored in a read only memory location and cannot be modified
3. pmessage can be changed to point to some other memory location

#include <stdio.h>
int main()
{
    char *pmessage = "Hello World from the C Program";

    pmessage[0] = 'P'; //throws segmentation fault
    printf("%s\n", pmessage);
    return 0;
}

Mar 25, 2012

Vertical Sum of a Binary Tree

The binary tree above can be represented as the following to calculate the vertical sum of the nodes

Mar 24, 2012

Remove a node from Binary Search Tree

C++
A node can be removed from a Binary Search Tree using two approaches.
1. Double Pointer Approach
2. Single Pointer Approach

Insert a node in Binary Search Tree

C++
A node can be inserted in a binary search tree using two approaches

Double pointer approach

void insert(BinaryTreeNode **node, int data)
   {
      if(*node == NULL)
      {
        *node = getNewNode(data);
      }
      
      if(data == (*node)->data)
      {
        //do  nothing
      }
      else if(data < (*node)->data)
      {
        insert(&(*node)->left, data);
      }
      else
      {
        insert(&(*node)->right, data);
      }
   }

Single pointer approach

BinaryTreeNode* insert(BinaryTreeNode *node, int data)
    {
      if(node == NULL)
      {
        node = getNewNode(data);
        return node;
      }
      
      if(data == node->data)
      {
        //do  nothing
      }
      else if(data < node->data)
      {
        node->left = insert(node->left, data);
      }
      else
      {
        node->right = insert(node->right, data);
      }

      return node;
   }