Tower of Hanoi Problem

The Problem

There are 3 pegs source ,auxillary and target. n disks of different sizes are given which can slide onto any peg . In the beginning all of the disks are in the source peg in the order of size with largest disk at the bottom and smallest disk at the top. We have to move all the disks from source peg to target peg such that in the end the target peg will have all the disks in the same order of size.

Rules:
1. Only one disk can be moved from one peg to another peg at a time
2. A larger disk cannot be placed on top of the smaller disk

C++ Program

#include <iostream>
#include <cstdlib>

static int moveCounter = 0;
void towerOfHanoi(int ndisk, char source, char auxillary, char target)
{
  if(ndisk == 1)
  {
    std::cout << "Move [" << ndisk << "]   [" << source << "] to [" <<
      target << "]" << std::endl;
    ++moveCounter;
    return;
  }

  //place ndisk - 1 disks from source to auxillary peg
  towerOfHanoi(ndisk - 1, source, target, auxillary);
  
  //place ndisk to target peg
  std::cout << "Move [" << ndisk << "]   [" << source << "] to [" <<
      target << "]" << std::endl;
  ++moveCounter;

  //place ndisk - 1 disks from auxillary to target peg
  towerOfHanoi(ndisk - 1, auxillary, source, target);
}

int main(int args, char *argv[])
{
  if(argv[1] == NULL)
  {
    std::cout << "ERROR: Insufficient Arguments\n";
    std::cout << "Usage: ./a.out number_of_disks\n";
    exit(-1);
  }
  int disks = atoi(argv[1]);
  
  char peg1 = 'A', peg2 = 'B', peg3 = 'C';
  towerOfHanoi(disks, peg1, peg2, peg3);
  std::cout << "Total Moves = " << moveCounter << std::endl;
}

Read more ...

Check if the linked list is a palindrome

The following code checks if the given singly linked list is a palindrome using recursion. 
Time Complexity: O(n) 
Space Complexity: O(n)

C++ Program

bool isPalindrome() const
    {
      Node* node = isPalindrome(head, head);
      if(node)
        return true;
      return false;
    }

    Node* isPalindrome(Node *left, Node *right) const
    {
      if(right == NULL)
      {
        return left;
      }

      left = isPalindrome(left, right->link);
      if(left)
      {
        bool palindrome = left->ch == right->ch ? true : false;
        if(palindrome)
        {
          left = left->link ? left->link : left;
          return left;
        }
      }
      return NULL;
    }

Java Program

public boolean isPalindrome()
  {
    Node node = isPalindrome(head, head);
    if(node == null)
      return false;
    return true;
  }

  private Node isPalindrome(Node left, Node right)
  {
    if(right == null)
    {
      return left;
    }
  
    left = isPalindrome(left, right.link);
    if(left != null)
    {
      boolean palindrome = left.data == right.data ? true : false;
      if(palindrome)
      {
        left = (left.link != null) ? left.link : left;
        return left;
      }
    }
    return null;
  }

Read more ...

Reverse a linked list

One of the frequently asked question in the interviews is to reverse a singly-linked list using iterative and recursive approach.

Iterative Approach

void ireverse()
    {
      Node *current = head;
      Node *prev = NULL;
      Node *next = current->link;

      while(next != NULL)
      {
        current->link = prev;
        prev = current;
        current = next;
        next = next->link;
      }

      current->link = prev;
      head = current;
    }

Recursive Approach

void reverse(Node *current, Node *prev, Node *next)
    {
      if(next == NULL)
      {
        current->link = prev;
        head = current;
        return;
      }
      current->link = prev;
      reverse(next, current, next->link);
    }

1. The complete C++ program can be viewed here
2. Java programmers can find the Java version of the above problem here
Read more ...

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

Read more ...

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;
}

Read more ...