Number of ways decoding a message

A message containing letters from A-Z is being encoded to numbers using the following mapping:

‘A’ => 1
‘B’ => 2
…
‘Z’ => 26

Given an encoded message containing digits, determine the total number of ways to decode it.
For example, given encoded message “12″, it could be decoded as “AB” (1 2) or “L” (12). The number of ways decoding “12″ is 2.

Solution:

1. Find all the subsets where we have 1 and 2 in the sequence continuously and keep the counts of total no of elements in each subset.
   • If the next element is 0 and count is more than 1, subtract the count by 1
   • Else increase the count by 1
2. find the fibonacci number for each count [0]=1 [1]=1 [2]=2 [3]=3 ...
3. Multiply all the fibonacci numbers gives the result

#include <stdio.h>
#include <stdlib.h>
#include <strings.h>

int main (int argc, char **argv)
{
  int length = strlen(argv[1]);
  char *result = (char *) calloc (length + 1, sizeof (char));
  int noofways = 1;

  int *fibonacci = (int *) calloc (length, sizeof(int));
  *fibonacci = 1;
  *(fibonacci+1) = 2;

  for (int i=2; i<length; i++)
  {
    *(fibonacci+i) = *(fibonacci+i-1) + *(fibonacci+i-2);
  }

  for (int i=1; i<=26; i++)
  {
    printf ("[%c:%d] ", 'A'+i-1, i);
  }
  printf ("\n");


  char *input = argv[1];

  while (*input != '\0')
  {
    if (*input >= '1' && *input <='2')
    {
      int count = 0;
      for (;*input >= '1' && *input <='2'; input++, count++)
        ;
      if (*input != '\0')
      {
        if ((*(input-1) == '1' && *input >= '1' && *input <= '9') ||
            (*(input-1) == '2' && *input >= '1' && *input <= '6'))
        {        
          count++;
        }
        else if ((*(input-1) == '1' && *input == '0') ||
                 (*(input-1) == '2' && *input == '0'))
        {
          count--;
          if (count == 0)
            count = 1;
        }
      }
      else if (*input == '\0')
      {
        noofways = noofways * *(fibonacci+count-1);
        break;
      }
      noofways = noofways * *(fibonacci+count-1);
    }
    else if (*input == '0')
    {
      noofways = 0;
      break;
    }
    input++;
  }
  printf ("No of ways: %d\n", noofways);
  return 0;
}

Code to get all the decoded strings
Function call: {decode (input, result, 0);}
[input]   => Input String
[output] => Temporary buffer to form the decoded string
[index]   => Index to decoded character

typedef enum boolean { FALSE=0, TRUE=1}bool;

bool decode (char *input, char *output, int index)
{
  static int count = 0;
  if (*input == '\0')
  {
    *(output+index) = '\0';
    count++;
    printf ("%-4d%s\n", count, output);
    return TRUE;
  }
  else if (*input == '0')
  {
    return FALSE;
  }
  else if ((*input == '1' && *(input+1) == '0') ||
           (*input == '2' && *(input+1) == '0'))
  {
    *(output+index) = 'A' + ((*input - '0') * 10) - 1;
    return decode (input+2, output, index+1);
  }
  else
  {
    *(output+index) = 'A' + (*input - '1');
    decode (input+1, output, index+1);
    
    if ((*input == '1' && *(input+1) >= '1' && *(input+1) <= '9') ||
        (*input == '2' && *(input+1) >= '1' && *(input+1) <= '6'))
    {
      *(output+index) = 'A' + (*input - '0') * 10 + *(input+1) - '0' - 1;
      decode (input+2, output, index+1);
    }
  }

  return TRUE;
}

Spell Check

I am using self balanced binary search tree to create the dictionary because the hash values for the dictionary wordsEn.txt vary from few thousands to few thousands of millions. If I want to map this big range to small one, there may be more collision.

My hash function gives me same hash value for the strings even if the character are jumbled. For example, "add" and "dad" will have the same hash value. I collect the list of words which have the same has value as the given string and find how close these words to the given string. I sort these suggestions in the order where the closest possibility comes first.

To get more words, i repeat this with adding a character each time from 'a' to 'z' with the given string and one more time with removing the character from all the possible indices.
Finally print the list.

Filename: dictionary.hpp

#ifndef __MY_DICTIONARY__
#define __MY_DICTIONARY__

#include <iostream>
#include <string>
using namespace std;

typedef struct word t_word;

class wordlist {
private:
  string dictionaryfile;
  t_word *dictionary;

public:
  wordlist (string dictfile)
  {
    this->dictionaryfile = dictfile;
    this->dictionary = NULL;
  }

  wordlist()
  {
  }

  void setWordFile (string wordfile)
  {
    this->dictionaryfile = wordfile;
  }

  string getWordFile ()
  {
    return this->dictionaryfile;
  }

  ~wordlist ()
  {
  }

  bool generateDictionary ();
  unsigned int calcHash (string);
  t_word *create (string);
  void rotateLeft (t_word*);
  void rotateRight (t_word*);
  void balanceFactors (t_word*, t_word*);
  void balanceLeftRight (t_word*, t_word*);
  void balanceRightLeft (t_word*, t_word*);
  void balance (t_word*, t_word*);
  void insert (string);
  int getScore (string, string);
  int findMatch (string, vector<string>&);
};

#endif

Filename: dictionary.cpp

#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <stdlib.h>

using namespace std;

#include "dictionary.hpp"

// Node to store the word and the corresponding hash values
struct word{
  string word;
  unsigned int hash;

  // Pointers to create the self-balanced binary search tree
  t_word *parent;
  t_word *left;
  t_word *right;
  char balanceFactor;
  
  // Pointer to store the words with the same hash value
  t_word *next;
};

// Generates the dictionary (self-balanced binary search tree)
// with the list of words from the given dictionary file.
bool wordlist::generateDictionary ()
{
  ifstream ifs (this->dictionaryfile.c_str());
  string str;
  
  try 
  {
    while (getline (ifs, str))
    {
      // Remove the new line 
      str.resize (str.length()-1);

      // Add the word into the dictionary
      insert (str);
    }
    ifs.close();
  } 
  catch (exception& e)
  {
    cerr << "[Error]: " << e.what() << endl;
    if (ifs.is_open())
    {
      ifs.close();
    }
    return false;
  }
  
  return true;
}

// Calculates the hash value for the given word
// Position of the characters does not have importance here.
unsigned int wordlist::calcHash (string word)
{
  unsigned int hash = 0;
  int val[26] = {0};
  const char *exp = word.c_str();
  while (('a' <= *exp && 
          'z' >= *exp) ||
         '\'' == *exp)
  {
    hash = hash + ((
                    (int(*exp) & 0x01) * 0xcf * 3+ 
                    (int(*exp) & 0x02) * 0xbf * 37+
                    (int(*exp) & 0x04) * 0xaf * 79+
                    (int(*exp) & 0x08) * 0x9f * 131+
                    (int(*exp) & 0x10) * 0x8f * 181+
                    (int(*exp) & 0x20) * 0x7f * 239+
                    (int(*exp) & 0x40) * 0x6f * 293+
                    (int(*exp) & 0x80) * 0x5f * 359) 
                   * (int (*exp) - int ('a') + 1) * 421 ) +
      (int (*exp) - int ('a') + 1) * 17;
      exp++;
  }
  hash += word.length();
  return hash;
}

// Create a new node with the given string and its has value
t_word* wordlist::create (string str)
{
  unsigned int hash = calcHash (str);
  t_word *t = new t_word;
  if (NULL == t)
  {
    cerr << "[Error] memory allocation failed." << endl;
    exit (1);
  }

  // cout << hash << " [" << str << "]" << endl;
  t->word = str;
  t->hash = hash;
  t->parent = NULL;
  t->left = NULL;
  t->right = NULL;
  t->next = NULL;
  t->balanceFactor = '=';
  
  return t;
}

void wordlist::rotateLeft (t_word *n)
{
  t_word *t = n->right;
  
  n->right = t->left;
  if (NULL != t->left)
  {
    t->left->parent = n;
  }
  
  if (NULL != n->parent)
  {
    if (n->parent->left == n)
    {
      n->parent->left = t;
    }
    else
    {
      n->parent->right = t;
    }
  }
  else
  {
    this->dictionary = t;
    t->parent = NULL;
  }
  t->left = n;
  t->parent = n->parent;
  n->parent = t;
}

void wordlist::rotateRight (t_word *n)
{
  t_word *t = n->left;
  
  if (NULL == n->left && NULL == n->right)
    return;
  
  n->left = t->right;
  if (NULL != t->right)
  {
    t->right->parent = n;
  }
  
  if (NULL != n->parent)
  {
    if (n->parent->left == n)
    {
      n->parent->left = t;
    }
    else
    {
      n->parent->right = t;
    }
  }
  else
  {
    this->dictionary = t;
    t->parent = NULL;
  }
  t->right = n;
  t->parent = n->parent;
  n->parent = t;
}

void wordlist::balanceFactors (t_word *ancestor, t_word *newLeaf)
{
  t_word *t = newLeaf->parent;
  while (t != NULL && t != ancestor)
  {
    if (newLeaf->hash <= t->hash)
      t->balanceFactor = 'L';
    else
      t->balanceFactor = 'R';
    
    t = t->parent;
  }
}

void wordlist::balanceLeftRight (t_word *ancestor, t_word *newLeaf)
{
  if (this->dictionary == ancestor)
  {
    ancestor->balanceFactor = '=';
  }
  else
  {
    t_word *t = ancestor;
    if (newLeaf->hash <= ancestor->parent->hash)
    {
      ancestor->balanceFactor = 'R';
      t = ancestor->parent->left;
    }
    else
    {
      ancestor->balanceFactor = '=';
      ancestor->parent->left->balanceFactor = 'L';
    }
    balanceFactors (t, newLeaf);
  }
}

void wordlist::balanceRightLeft (t_word *ancestor, t_word *newLeaf)
{
  if (this->dictionary == ancestor)
  {
    ancestor->balanceFactor = '=';
  }
  else
  {
    t_word *t = ancestor;
    if (newLeaf->hash > ancestor->parent->hash)
    {
      ancestor->balanceFactor = 'L';
      t = ancestor->parent->right;
    }
    else
    {
      ancestor->balanceFactor = '=';
      ancestor->parent->left->balanceFactor = 'R';
    }
    balanceFactors (t, newLeaf);
  }
}

void wordlist::balance (t_word *ancestor, t_word *newLeaf)
{
  // Balanced tree
  if (NULL == ancestor)
  {
    if (newLeaf->hash <= this->dictionary->hash)
    {
      this->dictionary->balanceFactor = 'L';
    }
    else
    {
      this->dictionary->balanceFactor = 'R';
    }
    balanceFactors (this->dictionary, newLeaf);
  }
  // Added to the other side of the balanced factor
  else if ((ancestor->balanceFactor == 'L' &&
            newLeaf->hash > ancestor->hash) ||
           (ancestor->balanceFactor == 'R' &&
            newLeaf->hash <= ancestor->hash))
  {
    ancestor->balanceFactor = '=';
    balanceFactors (ancestor, newLeaf);
  }
  // Added to the same side of the ancestor's child tree
  else if ((ancestor->balanceFactor == 'R' &&
            newLeaf->hash > ancestor->right->hash) ||
           (ancestor->balanceFactor == 'L' &&
            newLeaf->hash <= ancestor->left->hash))
  {
    char bf = ancestor->balanceFactor;
    ancestor->balanceFactor = '=';
    switch (bf)
    {
      case 'R':
        rotateLeft(ancestor);
        break;
      case 'L':
        rotateRight(ancestor);
        break;
    }
    balanceFactors (ancestor->parent, newLeaf);
  }
  // Added to the right of ancestor's left child
  else if (ancestor->balanceFactor == 'L' &&
           newLeaf->hash > ancestor->left->hash)
  {
    rotateLeft(ancestor->left);
    rotateRight(ancestor);
    balanceLeftRight (ancestor, newLeaf);
  }
  // Added to the left of ancestor's right child
  else if (ancestor->balanceFactor == 'R' &&
           newLeaf->hash <= ancestor->right->hash)
  {
    rotateRight(ancestor->right);
    rotateLeft(ancestor);
    balanceRightLeft (ancestor, newLeaf);
  }
  else
  {
    cerr << "[Error]: Not a valid operation." << endl;
    exit (1);
  }
}

void wordlist::insert (string str)
{
  t_word *t = create (str);
  t_word *ancestor = NULL;
  if (NULL == this->dictionary)
  {
    this->dictionary = t;
  }
  else
  {
    t_word *r = this->dictionary;
    while (NULL != r)
    {
      if (r->balanceFactor != '=')
        ancestor = r;
      
      if (t->hash < r->hash)
      {
        if (NULL != r->left)
        {
          r =r->left;
        }
        else
        {
          break;
        }
      }
      else if (t->hash > r->hash)
      {
        if (NULL != r->right)
        {
          r =r->right;
        }
        else
        {
          break;
        }
      }
      else
      {
        while (NULL != r->next)
          r = r->next;
        
        r->next = t;
        return;
      }
    }
    
    t->parent = r;
    
    if (t->hash <= r->hash)
    {
      r->left = t;
    }
    else
    {
      r->right = t;
    }

    // Balance the tree using AVL
    balance (ancestor, t);
  }
}

int wordlist::getScore (string s1, string s2)
{
  int i = 0;
  int j = 0;
  int len = s2.length() * s1.length();
  int *a_scores = new int [len];
  int score = 0;

  /*
  cout << "  ";
  for (i=0; i<s1.length(); i++)
  {
    cout << s1[i] << " ";
  }
  cout << endl;
  */

  for (j=0; j<s2.length(); j++)
  {
    // cout << s2[j] << " ";
    for (i=0; i<s1.length(); i++)
    {
      if (s1[i] == s2[j])
      {
        if (i == 0 || j == 0)
        {
          *(a_scores+(j*s1.length())+i) = 1;
        }
        else
        {
          int x = i-1;
          int y = j-1;
          int t_score = 0;
          for (;x>=0 && y>=0; x--,y--)
          {
            if (*(a_scores+(y*s1.length())+x) != 0)
            {
              t_score = *(a_scores+(y*s1.length())+x);
              break;
            }
          }
          for (x=i-1; x>=0; x--)
          {
            if (*(a_scores+(j*s1.length())+x) != 0)
            {
              if (t_score < *(a_scores+(j*s1.length())+x))
              {
                t_score = *(a_scores+(j*s1.length())+x) - 1;
              }
              break;
            }
          } 
          for (y=j-1; y>=0; y--)
          {
            if (*(a_scores+(y*s1.length())+i) != 0)
            {
              if (t_score < *(a_scores+(y*s1.length())+i))
              {
                t_score = *(a_scores+(y*s1.length())+i) - 1;
              }
              break;
            }
          }
          *(a_scores+(j*s1.length())+i) = t_score + 1;
        }
        if (score < *(a_scores+(j*s1.length())+i))
        {
          score = *(a_scores+(j*s1.length())+i);
        }
      }
      else
      {
        *(a_scores+(j*s1.length())+i) = 0;
      }
      // cout << *(a_scores+(j*s1.length())+i) << " ";
    }
    // cout << endl;
  }

  score = s1.length()-score;

  delete[] a_scores;

  return score;
}

int wordlist::findMatch (string str, vector<string>& result)
{
  unsigned int hash = calcHash(str);
  t_word *t = this->dictionary;
  unsigned int count = 0;
  unsigned int level = 0;

  while (NULL != t)
  {
    level ++;
    if (hash < t->hash)
    {
      t = t->left;
    }
    else if (hash > t->hash)
    {
      t = t->right;
    }
    else
    {
      while (NULL != t)
      {
        result.resize(count+1);
        result.at(count) = t->word;
        t = t->next;
        count++;
      }
      return level;
    }
  }

  return level;
}

Filename: spellCheck.cpp

#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
#include <sstream>
#include <string>
#include <algorithm>

using namespace std;

#include "dictionary.hpp"

int main ()
{
  wordlist mydict ("wordsEn.txt");
  // My Dictionary
  mydict.generateDictionary ();

  string str;
  // My wordlist which are to be checked
  ifstream ifs ("wordlist.txt");
  while (getline (ifs, str))
  {
    str.resize (str.length()-1);

    vector <string> matches;
    int count  = mydict.findMatch (str, matches);
        
    if (0 < matches.size())
    { 
      for (long index=0; index < matches.size(); index++)
      {
        int score = mydict.getScore (str, matches.at(index));
        ostringstream ss;
        ss << setw(2) << setfill('0') << score;
        matches.at(index) = ss.str() + matches.at(index);

      }
      sort (matches.begin(), matches.end());
      string tmp = matches.at(0);

      // Exact match. Goto the next word in the list
      if ('0' == tmp[0] && '0' == tmp[1])
      {
        cout << "Spelling is CORRECT for (" <<  str << ")" <<endl;
        continue;
      }
    }

    // Add each character from 'a' to 'z' one by one and check if we 
    // get more suggesstions.
    string alpha = "abcdefghijklmnopqrstuvwxyz";
    vector<string> tmp_matches;
    
    for (int i=0; i<alpha.length(); i++)
    {
      mydict.findMatch (str+alpha[i], tmp_matches);
      for (long index=0; index < tmp_matches.size(); index++)
      {

        int score = mydict.getScore (str, tmp_matches.at(index));
        ostringstream ss;
        ss << setw(2) << setfill('0') << score + 1;
        matches.push_back(ss.str() + tmp_matches.at(index));
      }
      tmp_matches.clear();
    }
    
    // Check the suggesstions for the strings by removing one character 
    // in different index and try all the posible index values.
    for (int i=0; i<str.length(); i++)
    {
      string tmp_str = str;
      tmp_str.erase (i, 1);
      mydict.findMatch (tmp_str, tmp_matches);
      for (long index=0; index < tmp_matches.size(); index++)
      {
        int score = mydict.getScore (tmp_str, tmp_matches.at(index));
        ostringstream ss;
        ss << setw(2) << setfill('0') << score + 1;
        matches.push_back(ss.str() + tmp_matches.at(index));
      }
      tmp_matches.clear();
    }

    if (0 < matches.size())
    {
      // Sort all the suggesstions with thr rank
      sort (matches.begin(), matches.end());

      // Remove the rank element from the strings
      for (long index=0; index < matches.size(); index++)
      {
        matches.at(index).erase(0,2);
      }
    
      // Removes duplicate consecutive elements  
      // matches.erase( unique( matches.begin(), matches.end() ), matches.end() );
    
      // Remove all the duplicates
      vector<string> uniqueMatches;
      uniqueMatches.push_back(matches.at(0));
      for (long index=1; index < matches.size(); index++)
      {
        if (uniqueMatches.end() == find (uniqueMatches.begin(), uniqueMatches.end(), matches.at(index)))
        {
          uniqueMatches.push_back(matches.at(index));
        }
      }
    
      // Final result
      cout << "Matcing for (" << str << "): { ";
      for (long index=0; index < uniqueMatches.size(); index++)
      {
        cout <<uniqueMatches.at(index) << " ";
      }
      cout << "}" << endl;
    }
    else
    {
      cout << count << " Matche not found for (" << str << ")" << endl;
    }
  }

  return 0;
}

You can find the wordlist.txt from here

Find the longest palindrome substring

#include <stdio.h>
#include<string.h>
#include <stdlib.h>

/*************************************************************
 * Function    : addSpecialChar
 * Input       : str
 * Output      : newStr
 * Description : This function gets a character array and
 *               inserts # in between each character and
 *               returns the new character array.
 *               Input : abcdef
 *               Output: #a#b#c#d#e#f#
 ************************************************************/
char *addSpecialChar(char *str)
{
  int index = 0;
  char *newStr = (char *) calloc (2*strlen(str)+1, 
                                  sizeof(char));
  if (NULL == newStr)
  {
    fprintf(stderr, 
            "[%s:%d] Memory allocation failed.", 
            __FUNCTION__, __LINE__);
    return NULL;
  }

  while ('\0' != *str)
  {
    newStr[index++] = '#';
    newStr[index++] = *str;
    str++;
  }

  newStr[index++] = '#';
  newStr[index] = '\0';
  return newStr;
}

/*************************************************************
 * Function    : getScore
 * Input       : str, score
 * Output      : maxScore
 * Description : This function calculates the number of 
 *               symmetric characters around each character
 *               in the given string and updates the score
 *               array. It returns the index of the max score
 *               from the score array.
 *               Input : #   a   #   a   #   b   #   c   #   b   #   a   #   
 *               Output: 0   1   2   1   0   1   0   5   0   1   0   1   0
 ************************************************************/
int getScore (char *str, int **score)
{
  int index = 1;
  int maxIndex = 0;
  int maxScore = 0;

  **score = 0;

  while ('\0' != str[index])
  {
    int leftindex = index - 1;
    int rightindex = index + 1;

    /* Calculate the score */
    int tmpScore = 0;
    for (;; leftindex--, rightindex++)
    {
      if (str[leftindex] != str[rightindex])
      {
        break;
      }
      if (leftindex == 0)
      {
        tmpScore++;
        break;
      }
      tmpScore++;
    }

    *((*score)+index) = tmpScore;
    if (maxScore < tmpScore)
    {
      maxScore = tmpScore;
      maxIndex = index;
    }

    /* The score on the left should be identical to the right
     * if the score at the new index is less than the difference
     * between score on the axis (current index) and the offset
     */
    int newIndex = 1;
    for (; newIndex < tmpScore; newIndex++)
    {
      if (*((*score)+index-newIndex) < *((*score)+index)-newIndex)
      {
        *((*score)+index+newIndex) = *((*score)+index-newIndex);
      }
      else
      {
        break;
      }
    }
    index = index + newIndex;

  }

  printf ("Max Index [%d]\n", maxIndex);
  return maxIndex;
}

int main (int agrc, char **argv)
{

  int *score = NULL;
  char *newStr = addSpecialChar (argv[1]);

  if (NULL != newStr)
  {
    score = (int *) calloc (strlen(newStr), sizeof (int));
    if (NULL == score)
    {
      fprintf(stderr, 
              "[%s:%d] Memory allocation failed.", 
              __FUNCTION__, __LINE__);
    }

    /* Print the actual string */
    printf ("%s\n%s\n", argv[1], newStr);

    int maxIndex = getScore (newStr, &score);

    /* Print the new string */
    for (int i=0; i<strlen(newStr); i++)
    {
      printf ("%-4c", newStr[i]); 
    }
    printf ("\n");

    /* Print the scores */
    for (int i=0; i<strlen(newStr); i++)
    {
      printf ("%-4d", score[i]); 
    }
    printf ("\n");

    /* Here is the longest palindrome */
    printf ("Longest Palindrome: ");
    int i = maxIndex/2 - score[maxIndex]/2;
    for (; i <= maxIndex/2 + score[maxIndex]/2; i++)
    {
      printf ("%c", argv[1][i]);
    }
    printf("\n");
  }

  return 0;
}

Output:

[COMMAND] ===>   ./logestPalindrome aabcba
aabcba
#a#a#b#c#b#a#
Max Index [7]
#   a   #   a   #   b   #   c   #   b   #   a   #   
0   1   2   1   0   1   0   5   0   1   0   1   0   
Longest Palindrome: abcba
-----------------------------------------------------------------------
[COMMAND] ===>   ./logestPalindrome aabcbabcbabcba
aabcbabcbabcba
#a#a#b#c#b#a#b#c#b#a#b#c#b#a#
Max Index [15]
#   a   #   a   #   b   #   c   #   b   #   a   #   b   #   c   #   b   #   a   #   b   #   c   #   b   #   a   #   
0   1   2   1   0   1   0   5   0   1   0   9   0   1   0   13  0   1   0   9   0   1   0   5   0   1   0   1   0   
Longest Palindrome: abcbabcbabcba
-----------------------------------------------------------------------
[COMMAND] ===>   ./logestPalindrome aabcbabcbaccba
aabcbabcbaccba
#a#a#b#c#b#a#b#c#b#a#c#c#b#a#
Max Index [11]
#   a   #   a   #   b   #   c   #   b   #   a   #   b   #   c   #   b   #   a   #   c   #   c   #   b   #   a   #   
0   1   2   1   0   1   0   5   0   1   0   9   0   1   0   5   0   1   0   1   0   1   2   1   0   1   0   1   0   
Longest Palindrome: abcbabcba
-----------------------------------------------------------------------
[COMMAND] ===>   ./logestPalindrome babcbabcbaccba
babcbabcbaccba
#b#a#b#c#b#a#b#c#b#a#c#c#b#a#
Max Index [11]
#   b   #   a   #   b   #   c   #   b   #   a   #   b   #   c   #   b   #   a   #   c   #   c   #   b   #   a   #   
0   1   0   3   0   1   0   7   0   1   0   9   0   1   0   5   0   1   0   1   0   1   2   1   0   1   0   1   0   
Longest Palindrome: abcbabcba
-----------------------------------------------------------------------
[COMMAND] ===>   ./logestPalindrome aaaaaaaaaaaaaaa
aaaaaaaaaaaaaaa
#a#a#a#a#a#a#a#a#a#a#a#a#a#a#a#
Max Index [15]
#   a   #   a   #   a   #   a   #   a   #   a   #   a   #   a   #   a   #   a   #   a   #   a   #   a   #   a   #   a   #   
0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  14  13  12  11  10  9   8   7   6   5   4   3   2   1   0   
Longest Palindrome: aaaaaaaaaaaaaaa
-----------------------------------------------------------------------
[COMMAND] ===>   ./logestPalindrome aaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaa
#a#a#a#a#a#a#a#a#a#a#a#a#a#a#a#a#
Max Index [16]
#   a   #   a   #   a   #   a   #   a   #   a   #   a   #   a   #   a   #   a   #   a   #   a   #   a   #   a   #   a   #   a   #   
0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16  15  14  13  12  11  10  9   8   7   6   5   4   3   2   1   0   
Longest Palindrome: aaaaaaaaaaaaaaaa
-----------------------------------------------------------------------
[COMMAND] ===>   ./logestPalindrome a
a
#a#
Max Index [1]
#   a   #   
0   1   0   
Longest Palindrome: a

Reference: http://leetcode.com/2011/11/longest-palindromic-substring-part-i.html

Heapsort

Heap
 Sort in place
 Binary tree
 Worst case runtime (n lg n)

PARENT(i) -> i/2
Left (i)  -> 2i
Right (i) -> 2i + 1

MAX_HEAP

A[PARENT(i)] >= A[i]

MIN_HEAP

A[PARENT(i)] <= A[i]

MAX-HEAPIFY
 Maintain the max-heap propert

 MAX-HEAPIFY (A, i)
   l = LEFT (i)
   r = RIGHT (i)
   if l <= A:heap-size and A[l] > A[i]
        largest = l
   else largest = i
   if r <= A.heap-size and A[r] > A[largest]
        largest = r
   if largest != i
        exchange A[i] with A[largest]
        MAX-HEAPIFY (A, largest)

Heap Sorting

 HEAPSORT (A)
  BUILD-MAX-HEAP (A)
  for i = A.length downto 2
    exchange A[1] with A[i]
    A.heap-size = A.heap-size - 1
    MAX-HEAPIFY (A, 1)

Priority queues
 One of the main usage is that we can use max-priority queues to schedule jobs on a shared computer.The max-priority queue keeps track of the jobs to
be performed and their relative priorities. When a job is finished or interrupted,the scheduler selects the highest-priority job from among those pending by calling EXTRACT-MAX. The scheduler can add a new job to the queue at any time by calling INSERT.

Reference: Introduction to Algorithms By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein

AVL tree - self-balancing binary search tree

In an AVL tree, the heights of the two child subtrees of any node differ by at most one; therefore, it is also said to be height-balanced. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.

Psuedo code:

IF tree is right heavy
{
  IF tree's right subtree is left heavy
  {
     Perform Double Left rotation
  }
  ELSE
  {
     Perform Single Left rotation
  }
}
ELSE IF tree is left heavy
{
  IF tree's left subtree is right heavy
  {
     Perform Double Right rotation
  }
  ELSE
  {
     Perform Single Right rotation
  }
}

Reference:
http://en.wikipedia.org/wiki/AVL_tree
http://oopweb.com/Algorithms/Documents/AvlTrees/Volume/AvlTrees.htm

Signal handler is not your regular function

Signal handler is a function which will be called when the program receives a signal. Most of the signals have their own default handlers and for few the parent program should handle/ignore this signal explicitly. In case of SIGCHLD, if the parent process should define the handler explicitly and wait for the child to exit (we can use SIGIGN too and no need to wait),otherwise the child process will become zombie.

Signal handler can not do everything what any normal function can do. It can call the functions and system calls which are async-safe.
This is the list of async-safe fuctions and system calls,

_Exit(), _exit(), abort(), accept(), access(), aio_error(), aio_return(), aio_suspend(), alarm(), bind(), cfgetispeed(), cfgetospeed(), cfsetispeed(), cfsetospeed(), chdir(), chmod(), chown(), clock_gettime(), close(), connect(), creat(), dup(), dup2(), execle(), execve(), fchmod(), fchown(), fcntl(), fdatasync(), fork(), fpathconf(), fstat(), fsync(), ftruncate(), getegid(), geteuid(), getgid(), getgroups(), getpeername(), getpgrp(), getpid(), getppid(), getsockname(), getsockopt(), getuid(), kill(), link(), listen(), lseek(), lstat(), mkdir(), mkfifo(), open(), pathconf(), pause(), pipe(), poll(), posix_trace_event(), pselect(), raise(), read(), readlink(), recv(), recvfrom(), recvmsg(), rename(), rmdir(), select(), sem_post(), send(), sendmsg(), sendto(), setgid(), setpgid(), setsid(), setsockopt(), setuid(), shutdown(), sigaction(), sigaddset(), sigdelset(), sigemptyset(), sigfillset(), sigismember(), sleep(), signal(), sigpause(), sigpending(), sigprocmask(), sigqueue(), sigset(), sigsuspend(), sockatmark(), socket(), socketpair(), stat(), symlink(), sysconf(), tcdrain(), tcflow(), tcflush(), tcgetattr(), tcgetpgrp(), tcsendbreak(), tcsetattr(), tcsetpgrp(), time(), timer_getoverrun(), timer_gettime(), timer_settime(), times(), umask(), uname(), unlink(), utime(), wait(), waitpid(), and write().

Ref : http://beej.us/guide/bgipc/output/html/singlepage/bgipc.html#signals

Prime numbers

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <sys/time.h>
#include <string.h>
#include <errno.h>

#define ERRNUM -1

typedef enum bool {
  FALSE =0,
  TRUE
} e_bool;

typedef enum stauts {
  FAILURE = 0,
  SUCCESS
} e_status;

typedef struct list* tsp_list;
struct list{
  unsigned int val;
  unsigned int index;
  tsp_list next;
};

e_status Append (unsigned int num, tsp_list *list)
{
  tsp_list lsp_primeNode = NULL;
  lsp_primeNode = (tsp_list) calloc (1, sizeof (struct list));
  if (NULL == lsp_primeNode)
  {
    fprintf (stderr, "ERROR: memory allocation failed.\n");
    return FAILURE;
  }
  lsp_primeNode->val = num;
  lsp_primeNode->next = NULL;

  if (NULL == *list)
  {
    *list = lsp_primeNode;
    lsp_primeNode->index = 1;
  }
  else
  {
    tsp_list node = *list;
    while (NULL != node->next)
    {
      node = node->next;
    }

    node->next = lsp_primeNode;
    lsp_primeNode->index = node->index + 1;
  }

  return SUCCESS;
}


e_bool IsPrime (unsigned int num, tsp_list list)
{
  if (1 >= num)
  {
    return FALSE;
  }

  switch (num)
  {
    case 2:
    case 3:
      return TRUE;
    default:
      {
        unsigned int lv_max_limit = (unsigned int) sqrt (num);
        
        while (list && list->val <= lv_max_limit)
        {
          if (0 == num % list->val)
          {
            return FALSE;
          }
          list = list->next;
        }
        return TRUE;
      }
  }
}

void GetPrimeList (tsp_list *list, unsigned count)
{
  unsigned int i = 2;
  unsigned int index = 1;
  struct timeval start;
  struct timeval end;
  struct timeval diff;

  if(-1 == gettimeofday(&start, NULL))
  {
    fprintf (stderr, "ERROR: %s\n", strerror (errno));
    return;
  }

  for (; i && 0 < count; i++)
  {
    if (TRUE == IsPrime (i, *list))
    {
      if(-1 == gettimeofday(&end, NULL))
      {
        fprintf (stderr, "ERROR: %s\n", strerror (errno));
        return;
      }

      /* Ref [http://www.linuxquestions.org/questions/programming-9/how-to-calculate-time-difference-in-milliseconds-in-c-c-711096] */
      diff.tv_sec =end.tv_sec - start.tv_sec ;
      diff.tv_usec=end.tv_usec - start.tv_usec;

      if(diff.tv_usec<0)
      {
        diff.tv_usec+=1000000;
        diff.tv_sec -=1;
      }

      printf ("%d (index: %d) (Time taken: %f sec)\n", i, index++, (float)(1000000LL*diff.tv_sec + diff.tv_usec)/1000000);
      
      if (FAILURE == Append (i, list))
      {
        return;
      }
      else
      {
        count --;
      }
    }
  }
}

int main (int argc, char *argv[])
{
  tsp_list primeList = NULL;
  int dig = 0;

  if ( 2 != argc)
  {
    return 0;
  }

  GetPrimeList (&primeList, (int) atoi(argv[1]));

  return 0;
}

Find the permutation and combination for a given string

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define ERRNUM -1
#define SUCCESS 0

#define TRUE 1
#define FALSE 0

#define TOTAL_ALPHA 26

/* Function   : permutations
 * Args       : str [IN]
 *              index [IN]
 *              result [IN/OUT]
 * Description: Function will print all the permutations and combinations of a given string 
 *              without repeated patterns. PnC(ABC) = { A+PnC(BC), B+PnC(CA), C+PnC(AB) } 
 * Note       : This "without repeated patterns" will not work for non-alpha characters [TBD]. 
 */
int permutations (char *str, int index, char *result)
{
  char *temp = NULL;           // To store the given string for processing
  int len = strlen (str);      // Length of the given string
  int count = 0;               // Counter variable used in the loop
  int j = 0;                   // Temporary variable
  char found[52] = {0};        // To check the variable to check the duplicate characters to avoid duplicate patterns

  /* Allocate memory for the temp variable to store the given string for processing.
   * So that the given string will not change. 
   */
  temp = (char *) calloc (len+1, sizeof (char));
  if (NULL == temp)
  {
    fprintf (stderr, "Memory allocation failed.\n");
    return ERRNUM;
  }

  /* Copy the given string into the temporary variable */
  strcpy (temp, str);

  /* Traverse through the string and find the permutations and combinations of the substring 
   * PnC(ABC) = { A+PnC(BC), B+PnC(CA), C+PnC(AB) } 
   */
  for (count=0; count < len; count++)
  {
    char ch = 0;
    
    *(result + index) = *temp;
    if (1 == len)
    {
      /* We can store in an array of string or a stack */
      printf ("%s\n", result);
    }
    else
    {
      if (isupper (*temp))
      {
        
        if (FALSE == found [TOTAL_ALPHA + (*temp) - 'A'])
        {
          found [TOTAL_ALPHA + (*temp) - 'A'] = TRUE;
        }
        else
        {
          /* Its a duplicate character */
          goto NEXT;
        }
      }
      else if (islower (*temp))
      {
        if (FALSE == found [(*temp) - 'a'])
        {
          found [(*temp) - 'a'] = TRUE;
        }
        else
        {
          /* Its a duplicate character */
          goto NEXT;
        }
      }
      
      /* We can store in an array of string or a stack */
      for (j=0; j<=index; j++)
      {
        printf ("%c", *(result+j));
      }
      printf ("\n");

      /* Find the permutations and combinations for the substring too */
      if (ERRNUM == permutations (temp+1, index+1, result))
      {
        return ERRNUM;
      }

    NEXT:
      ch = *temp;
      memcpy (temp, temp+1, len-1);
      temp[len-1] = ch;
    }
  }

  /* Free the allocated memory for the temporary variable */
  free (temp);

  return SUCCESS;
}

int main (int argc, char *argv[])
{
  char *result = NULL;        // Variable to store the result for printing 
  int retVal = SUCCESS;       // Variable to stroe the return value

  // No code to check/validate the input [TBD].

  if (NULL == result)
  {
    result = (char *) calloc (strlen (argv[1])+1, sizeof (char));
    if (NULL == result)
    {
      fprintf (stderr, "Memory allocation failed.\n");
      return ERRNUM;
    }
  }

  retVal = permutations (argv[1], 0, result);
  
  free (result);
    
  return retVal;
}

The results:

prompt$ ./permutationsNconbination ABC

A

AB

ABC

AC

ACB

B

BC

BCA

BA

BAC

C

CA

CAB

CB

CBA

prompt$ ./permutationsNconbination AAB

A

AA

AAB

AB

ABA

B

BA

BAA

prompt$ ./permutationsNconbination AAA

A

AA

AAA

prompt$

Get information about all the network interfaces in linux

This program lists all active network interfaces in the system with associated IP address, MAC address and the subnetmask.

#include <stdio.h>
#include <string.h>
#include <errno.h>
#include <unistd.h>

#define __KERNEL__
#include <asm/types.h>
#undef __KERNEL__

#include <linux/ethtool.h>
#include <linux/sockios.h>

#include <net/if.h>
#include <sys/ioctl.h>
#include <arpa/inet.h>

/* this is straight from beej's network tutorial. It is a nice wrapper
 * for inet_ntop and helpes to make the program IPv6 ready
 */
char *get_ip_str(const struct sockaddr *sa, char *s, size_t maxlen)
{
  switch(sa->sa_family) {
    case AF_INET:
      inet_ntop(AF_INET, &(((struct sockaddr_in *)sa)->sin_addr), s, maxlen);
      break;

    case AF_INET6:
      inet_ntop(AF_INET6, &(((struct sockaddr_in6 *)sa)->sin6_addr), s, maxlen);
      break;

    default:
      strncpy(s, "Unknown AF", maxlen);
      return NULL;
  }

  return s;
}

int main (int argc, char **argv)
{
  char          buf[1024] = {0};
  struct ifconf ifc = {0};
  struct ifreq *ifr = NULL;
  int           sck = 0;
  int           nInterfaces = 0;
  int           i = 0;
  struct ifreq ifr_subnet;
  struct sockaddr *addr_subnet = NULL;

  /* Get a socket handle. */
  sck = socket(AF_INET, SOCK_DGRAM, 0);
  if(-1 == sck) {
    perror("socket");
    return 1;
  }

  /* Query available interfaces. */
  ifc.ifc_len = sizeof(buf);
  ifc.ifc_buf = buf;
  if(-1 == ioctl(sck, SIOCGIFCONF, &ifc)) {
    perror("ioctl(SIOCGIFCONF)");
    close (sck);
    return 1;
  }

  /* Iterate through the list of interfaces. */
  ifr = ifc.ifc_req;
  nInterfaces = ifc.ifc_len / sizeof(struct ifreq);
  for(i = 0; i < nInterfaces; i++)
  {
    struct ifreq *item = &ifr[i];

    /* Show the device name and IP address */
    struct sockaddr *addr = &(item->ifr_addr);
    char ip[INET6_ADDRSTRLEN];
    printf("%s: IP %s",
           item->ifr_name,
           get_ip_str(addr, ip, INET6_ADDRSTRLEN));

    /* Get the MAC address */
    if(-1 == ioctl(sck, SIOCGIFHWADDR, item)) {
      perror("ioctl(SIOCGIFHWADDR)");
      close (sck);
      return 1;
    }

    /* display result */
    printf(", MAC %.2x:%.2x:%.2x:%.2x:%.2x:%.2x ",
           (unsigned char)item->ifr_hwaddr.sa_data[0],
           (unsigned char)item->ifr_hwaddr.sa_data[1],
           (unsigned char)item->ifr_hwaddr.sa_data[2],
           (unsigned char)item->ifr_hwaddr.sa_data[3],
           (unsigned char)item->ifr_hwaddr.sa_data[4],
           (unsigned char)item->ifr_hwaddr.sa_data[5]);

    /* Reset the memory allocated for ifreq */
    memset (&ifr_subnet, 0, sizeof (struct ifreq));

    /* Update interface name into ifreq */
    strcpy (ifr_subnet.ifr_name, item->ifr_name);

    /* Call ioctl function */
    if(-1 == ioctl (sck, SIOCGIFNETMASK, &ifr_subnet ))
    {
      perror("ioctl(SIOCGIFNETMASK)");
      close (sck);
      return 1;
    }
    addr_subnet = &(ifr_subnet.ifr_addr);
    printf("SubnetMask: %s\n", get_ip_str(addr_subnet, ip, INET6_ADDRSTRLEN));
  }

  close (sck);
  return 0;
}

Reference: http://www.adamrisi.com/?p=84

Simple PING implementation in C

#include <netinet/in.h>
#include <netinet/ip.h>
#include <netinet/ip_icmp.h>
#include <arpa/inet.h>
#include <netdb.h>
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <sys/signal.h>
#include <string.h>

#define DEFDATALEN      56
#define MAXIPLEN        60
#define MAXICMPLEN      76

static char *hostname = NULL;

static int in_cksum(unsigned short *buf, int sz)
{
  int nleft = sz;
  int sum = 0;
  unsigned short *w = buf;
  unsigned short ans = 0;
  
  while (nleft > 1) {
    sum += *w++;
    nleft -= 2;
  }
  
  if (nleft == 1) {
    *(unsigned char *) (&ans) = *(unsigned char *) w;
    sum += ans;
  }
  
  sum = (sum >> 16) + (sum & 0xFFFF);
  sum += (sum >> 16);
  ans = ˜sum;
  return (ans);
}

static void noresp(int ign)
{
  printf("No response from %s\n", hostname);
  exit(0);
}

static void ping(const char *host)
{
  struct hostent *h;
  struct sockaddr_in pingaddr;
  struct icmp *pkt;
  int pingsock, c;
  char packet[DEFDATALEN + MAXIPLEN + MAXICMPLEN];
  
  if ((pingsock = socket(AF_INET, SOCK_RAW, 1)) < 0) {       /* 1 == ICMP */
    perror("ping: creating a raw socket");
    exit(1);
  }
  
  /* drop root privs if running setuid */
  setuid(getuid());
  
  memset(&pingaddr, 0, sizeof(struct sockaddr_in));
  
  pingaddr.sin_family = AF_INET;
  if (!(h = gethostbyname(host))) {
    fprintf(stderr, "ping: unknown host %s\n", host);
    exit(1);
  }
  memcpy(&pingaddr.sin_addr, h->h_addr, sizeof(pingaddr.sin_addr));
  hostname = h->h_name;
  
  pkt = (struct icmp *) packet;
  memset(pkt, 0, sizeof(packet));
  pkt->icmp_type = ICMP_ECHO;
  pkt->icmp_cksum = in_cksum((unsigned short *) pkt, sizeof(packet));
  
  c = sendto(pingsock, packet, sizeof(packet), 0,
             (struct sockaddr *) &pingaddr, sizeof(struct sockaddr_in));
  
  if (c < 0 || c != sizeof(packet)) {
    if (c < 0)
      perror("ping: sendto");
    fprintf(stderr, "ping: write incomplete\n");
    exit(1);
  }
  
  signal(SIGALRM, noresp);
  alarm(2);                                     /* give the host 5000ms to respond */
  /* listen for replies */
  while (1) {
    struct sockaddr_in from;
    size_t fromlen = sizeof(from);
    
    if ((c = recvfrom(pingsock, packet, sizeof(packet), 0,
                      (struct sockaddr *) &from, &fromlen)) < 0) {
      if (errno == EINTR)
        continue;
      perror("ping: recvfrom");
      continue;
    }
    if (c >= 76) {                   /* ip + icmp */
      struct iphdr *iphdr = (struct iphdr *) packet;
      
      pkt = (struct icmp *) (packet + (iphdr->ihl << 2));      /* skip ip hdr */
      if (pkt->icmp_type == ICMP_ECHOREPLY)
        break;
    }
  }
  printf("%s is alive!\n", hostname);
  return;
}

int main ()
{
  ping ("192.168.1.2");

}

Reference: http://www.koders.com/c/fid30EA22902AFF5800481BBC6F65DADCDAF92D6E37.aspx