Find minimum number of different type of dishes to be ordered

There are n persons and k different type of dishes. Each person has some preference for each dish. Either he likes it or not. We need to feed all people. Every person should get at least one dish of his choice. What is the minimum number of different type of dishes we can order? 

Input is n x k matrix boolean matrix.For each person a row represent his likes or not likes each row. 

n = 6 k = 7 
1 0 0 0 1 0 0 
1 0 0 0 0 1 0 
1 0 0 0 0 0 1 
0 1 0 0 1 0 0 
0 0 1 0 0 1 0 
0 0 0 1 0 0 1 

Output 
3 

Explanation 
Take dish number 5,6,7.

Update the dishes array with the input vector.
N(i) = (N(i) << 1) | V(i)

void updateDishes(vector<string> list, int **dishes)
{
  int index = 0;
  for (vector<string>::const_iterator i = list.begin(); i != list.end(); ++i)
  {
    *((*dishes)+index) = (*((*dishes)+index) << 1) | (stoi(*i) & 0x1);
    index++;
  }
}    
  

Read the input file and update the dishes array.

int *CreateArrayFromFile(string filename, int &totalDishes, int &totalPersons)
{

  int *num = NULL;
  string line;
  string buf; 
  ifstream inFile(filename);

  // Read line by line for processing
  while ( getline (inFile, line) )
 {

    // Tokenize the line
    stringstream ss(line);
    vector<string> tokens;

    // Store all the tokens in a vector
    while (ss >> buf)
      tokens.push_back(buf);

    // Allocate the memory for the dishes array
    if (NULL == num)
    {
      totalDishes = tokens.size();
      num = new int[totalDishes]();

#ifdef DEBUG
      for (int i=0; i<tokens.size(); i++)
        cout << i << ": " << num[i] << endl;
#endif

}

    // Update the dishes array with person's like/dislike
    updateDishes(tokens, &num);

#ifdef DEBUG
    for (int i=0; i<tokens.size(); i++)
      cout << i << ": " << num[i] << endl;
    
    printVector(tokens);
#endif
    
    totalPersons++;
  }

  // Return the updates dishes array 
  return num;
}

This counts the numbers of bits set in a given numbers. Its a very silly way of counting bits set :(

 int getOnesCount(int num)
{
  int count = 0;

  while(num)
  {
    count = count + (num & 0x1);
    num = num >> 1;
  }

  return count;
}   
  

It interartes over the range (1..2^n) where n is the total number of dishes and create sets which holds the same number of bits set. This data will be used to find all the possible combinations of the same number of bits set in the range.

void getCombinations(vector < vector <int> > &combinations, int totalDishes, int totalPersons)
{

  // Place holders for all the sets
  for (int i=0; i<totalDishes; i++)
  {
    combinations.push_back(vector <int>());
  }

  // Update the sets
  int end = (1 << totalDishes);
  for (int i=1; i<end; i++)
  {
    combinations[getOnesCount(i)-1].push_back(i);
  }

#ifdef DEBUG
  for (int i=0; i<combinations.size(); i++)
  {
    cout << "Vector " << i+1 << " : " ;
    for (vector<int>::iterator it = combinations[i].begin(); it != combinations[i].end(); ++it)
    {
      cout << *it << " ";
    }
    cout << endl;
  }
  cout << endl;
#endif
  
}    
  

Checks if the given combination (bits set in the given num) satisfies all the persons.

bool doesSatisfy(int *dishes, int num, int totalPersons)
{
  int satisfy = (1 << totalPersons) - 1;
  int result = 0;
  int index = 0;
  bool retval = false;
  
  while (num)
  {
    if (num & 0x1)
      result = result | *(dishes+index);

    index++;
    num = num >> 1;
  }

  if(result == satisfy)
    retval = true;

  return retval;
}    
  

This is our main function.

int findMinDishCount(int *dishes, int totalDishes, int totalPersons)
{
  int start = 0;
  int end = totalDishes - 1;
  int index = (int) ((end - start) / 2);
  int retval = -1;

  // Get the combinations with respect to the number of bits set
  vector < vector <int> > combinations;
  getCombinations(combinations, totalDishes, totalPersons);

 /*
  * Here we are using binary search tree traversal to select the numbers of dishes to
  * satisfy all the persons likes.
  */
  while (start != end)
  {
#ifdef DEBUG    
    cout << "[Start:" << start << "] [End:" << end << "]" << endl;
#endif
    index = (int) (start + ((end - start) / 2));
    
    bool foundMatch = false;

    for (vector<int>::iterator it = combinations[index].begin(); it != combinations[index].end(); ++it)
    {
#ifdef DEBUG      
      cout << "[" << index << "] (" << *it << ") ";
#endif
      if (doesSatisfy(dishes, *it, totalPersons) == true)
      {
        foundMatch = true;
        retval = index;
#ifdef DEBUG
        cout << "true" << endl;
#endif

        // If the combination satisfies all the persons likes, We do not need to check
        // with other combinations from the same set
        break;
      }
#ifdef DEBUG
      cout << "false" << endl;
#endif
    }
    
    if (foundMatch == true)
    {
      end = index;
    }
    else
    {
      if (start == end-1)
      {
        if (end == totalDishes - 1 && doesSatisfy(dishes, combinations[end][0], totalPersons) == true)
        {
          retval = end;
        }
        break;
      }
      start = index;
    }    
  }

  return retval + 1;
}    
  

Here is the helper/wrapper function.

int main(int argc, char **argv)
{
  int totalDishes = 0;
  int totalPersons = 0;
  int *dishes = NULL;

  cout << "Filename: " << argv[1] << endl;
  dishes = CreateArrayFromFile(argv[1], totalDishes, totalPersons);
  cout << "Total Dishes: " << totalDishes << endl;
  cout << "Total Persons: " << totalPersons << endl;
  
  cout << endl;
  printLikesDislikes(dishes, totalDishes, totalPersons);
  
  cout << endl;
  int minDishes = findMinDishCount(dishes, totalDishes, totalPersons);
  cout << "Minimun dishes to statisfy everyone: " << minDishes <<endl;
  
  return 0;
}  
  

Supportive hearders.

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

using namespace std;    
  

These functions will be used to get the output in verbose mode.This will be useful in debugging.

void printVector(vector<string> list)
{
  for (vector<string>::const_iterator i = list.begin(); i != list.end(); ++i)
  {
    cout << "[" << *i << "] ";
  }
  cout << endl;
}
  

void printLikesDislikes(int *dishes, int totalDishes, int totalPersons)
{
  string heading = "------------";
  cout << "Dishes   :  ";
  for (int j=1; j<=totalDishes; j++)
  {
    cout << j << " ";
    heading = heading + "--";
  }
  cout << endl << heading << endl;
  
  for (int i=totalPersons-1; i>=0; i--)
  {
    string likeDislike = "";
    for (int j=0; j<totalDishes; j++)
    {
      int pos = 1 << i;
      likeDislike = likeDislike + " " + ((pos & *(dishes+j)) == 0 ? "0" : "1");
    }
    cout << "Person " << totalPersons - i << " : " << likeDislike << endl;
  }
}
  

Write a function which does zig-zag traverse of binary tree and prints out nodes.

All the header files which are needed

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdexcept>
    

Brings all the named entities from std namespace into current declarative region

using namespace std;
    

This is the node structure we use to store the values and form the binary tree. For the simplicity, we use int data type to store the node data.

struct node {
  int val;
  struct node *left;
  struct node *right;
};

    

It prints the vector contents for debug purpose.

void printVector(vector<node *> list)
{
  for (vector<node *>::const_iterator i = list.begin(); i != list.end(); ++i)
  {
    if (NULL != *i)
      cout << "[" << (*i)->val << "] -> ";
    else
      cout << "[EMPTY] -> ";
  }
  cout << "NULL" << endl;
}

    

The input vector has all the nodes of a certain level (or depth) in the given tree, stored from left to right. This function is capable of printing either in the same order as the vector is created or in reverse order.

void printLevels(vector<node *>& level, int count, int forward)
{
  
  if (1 == forward) { // Print vector as it is
    for(vector<node *>::iterator it = level.begin(); it != level.end(); ++it) {
      if (*it)
        cout << (*it)->val << " ";
      else
        cout << "- "; // Empty Node
    }
  } else { // Print vector in reverse order
    for(vector<node *>::reverse_iterator it = level.rbegin(); it != level.rend(); ++it) {
      if (*it)
        cout << (*it)->val << " ";
      else
        cout << "- "; // Empty Node
    }
  }
  cout << endl;
}
    

The main function to trave level by level.

void traverse(node *binaryTree, bool ziczac)
{
  string zz = ziczac? "True":"False";
  cout << "ZicZac: [" << zz << "]" << endl;
  
  int count = 1;             // Initial count for the ROOT node (Level 1)
  int countNext = 0;         // Node count in the Next Level
  int forward = 1;           // Decides how to print the list
  vector<node *> nodeList;   // Store nodes level-by-level
  node *tmp = NULL;          // Store the node pointer temporarily 

  // Push the ROOT
  nodeList.push_back(binaryTree);
  
  while (0 != count) {
    // Print the nodes from the current level
    printLevels(nodeList, count, forward);
    
    // Iterate the nodes from current level and get the nodes from
    // the next level
    countNext = 0;
    for (int i=0; i<count;){
      tmp = nodeList.front();

      // Remove the node which is getting processed
      nodeList.erase(nodeList.begin());

      // Node is NULL. Don't count the NULL nodes
      if (NULL == tmp) {
        nodeList.push_back(NULL);
        nodeList.push_back(NULL);
      } else {
        i++;
      
        // Check the left child node
        if (tmp->left) {
          countNext++;
          
          // Push it to the list
          nodeList.push_back(tmp->left);
        } else {
          nodeList.push_back(NULL);
        }
        
        // Check the right child node
        if (tmp->right) {
          countNext++;
          
          // Push it to the list
          nodeList.push_back(tmp->right);
        } else {
          nodeList.push_back(NULL);
        }
      }
    }

    // update the current with the level count from the next level
    count = countNext;
    
    if (true == ziczac) {
      // Toggle the way the level is getting printed
      forward = (forward ^ 0x1) & 0x1;
    }
  }
}
    

Read the file with the following format,
('|' is the delimitor)
   1
   2|3
   4|5| |7
   8|9|0|1| | |2|3

and create the binary tree

node *createBinaryTreeFromFile(string filename)
{
  node *binaryTree = NULL;
  vector<node *> nodeList;
  vector<node *> childNodeList;
  vector<string> stringList;
  string line;
  
  try {

    // Open the given file
    ifstream inFile (filename);

    while ( getline (inFile, line) )
    {
      // First Line => ROOT node
      if (NULL == binaryTree) {
        binaryTree = new node;
        binaryTree->val = stoi(line);
        binaryTree->right = NULL;
        binaryTree->left = NULL;
        nodeList.push_back(binaryTree);
      } else {
        stringList.clear();
        string::size_type prev_pos = 0, pos = 0;
        // Split the line with '|' delimitor 
        while( (pos = line.find('|', pos)) != string::npos )
        {
          std::string substring( line.substr(prev_pos, pos-prev_pos) );
          stringList.push_back(substring);
          prev_pos = ++pos;
        }
        string substring( line.substr(prev_pos, pos-prev_pos) ); // Last word
        stringList.push_back(substring);

        // Create the binary tree here (level by level)
        vector<string>::iterator itStringList = stringList.begin();
        while (!nodeList.empty()) {
          
          if (itStringList >= stringList.end())
            break;

          if (NULL == *(nodeList.begin())) {
            itStringList = itStringList + 2;
          } else {
            // Left Node
            try{
              int val = stoi(*itStringList);
              node *tmp = new node;
              tmp->val = val;
              tmp->left = NULL;
              tmp->right = NULL;
              (*(nodeList.begin()))->left = tmp;
              itStringList++;
              nodeList.push_back(tmp);
            } catch (const invalid_argument& ia) {
              cerr << "Invalid argument: " << ia.what() << '\n';
              nodeList.push_back(NULL);
              itStringList++;
            }

            // Right Node
            try{
              int val = stoi(*itStringList);
              node *tmp = new node;
              tmp->val = val;
              tmp->left = NULL;
              tmp->right = NULL;
              (*(nodeList.begin()))->right = tmp;
              itStringList++;
              nodeList.push_back(tmp);
            } catch (const invalid_argument& ia) {
              cerr << "Invalid argument: " << ia.what() << '\n';
              nodeList.push_back(NULL);
              itStringList++;
            }
          }
          
          // Remove the node which is getting processed
          nodeList.erase(nodeList.begin());
        }
      }
    }
    inFile.close();
  } catch (ifstream::failure e) {
    cerr << e.what() << endl;
  }

  // Print the tree
  traverse(binaryTree, false);
  
  return binaryTree;
}
    

Everything starts from here,

int main(int argc, char** argv)
{
  node *binaryTree = createBinaryTreeFromFile(argv[1]);
  traverse(binaryTree, true);
  return 0;
}

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

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