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 ...