#include <iostream>
using namespace std;
#define HEIGHT 25
#define WIDTH 80
char Matrix[HEIGHT][WIDTH];
double findSlope(int x1,int x2, int y1, int y2)
{
    if(x1 == x2)
        return 0;
    return (double(y2-y1)/double(x2-x1));
}
void initializeMatrix()
{
     for(int i=0; i<HEIGHT; i++)
     {
         for(int j=0; j<WIDTH; j++)
         {
             Matrix[i][j] = '.';  
         }
     }
}
int roundToInt(float val)
{
    if(val - int(val) < 0.5)
       return int(val);
    return int(val+1);
}
void setPoint(float slope,float constant,int x)
{
     int y = roundToInt(slope * x + constant);    
     if(y >=0 && y < HEIGHT)
     {
          Matrix[x][y] = '*';
     }
}
void fillArray(float slope,float constant,int x1,int x2, int y1, int y2)
{
     for(int x=0; x < WIDTH; x++)
     {
         setPoint(slope,constant,x);
     }
}
float findConstant(float slope,int x1,int y1)
{
    return (y1 - slope * x1);
}
void displayMatrix()
{
     for(int row=0; row<HEIGHT; row++)
     {
         cout<<"\n"<<row<<" = ";
         for(int col = 0; col<WIDTH; col++)
         {
             cout<<" "<<Matrix[row][col];
         }
     }
}
int main()
{
    int x1,x2,y1,y2;
    x1= 10;
    y1= 20;
    x2= 20;
    y2= 30;
    float slope= findSlope(x1,x2,y1,y2);
    float constant = findConstant(slope,x1,y1);
    initializeMatrix();
    fillArray(slope,constant,x1,x2,y1,y2);
    displayMatrix();
    system("pause");
}

Program to get the number and print the number in words (number <= 99999). For eg. 1234 is one thousand two hundred thirty four.

#include <iostream>
#include <sstream>

using namespace std;
    string unit[] = {"","one","two","three","four","five","six","seven","eight","nine"};
    string teen[] = {"","eleven","twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen","nineteen"};
    string ty[]   = {"","ten","twenty","thirty","forty","fifty","sixty","seventy","eighty","ninety"};

int countDigits(int n)
{
    int count = 0;
    while(n)
    {
            n/= 10;
            count++;
    }
    return count;
}


string numToString(int n)
{
    string result ;
    ostringstream r;
    r<<n;
    result = r.str();
    return result;
}

void print10000(int d1,int d2)
{
     if(d1 > 1)
     {
         cout<<ty[d1]<<" ";
         cout<<unit[d2]<<" ";
     }
     else
     {
         if(d2)
              cout<<teen[d1]<<" ";
         else
              cout<<"Ten ";
     }
     cout<<"thousand ";
}

void print1000(int d)
{
     if(d)
     {
          cout<<unit[d]<<" thousand ";
     }
}

void print100(int d)
{
     if(d)
     {
          cout<<unit[d]<<" hundred ";
     }
}

void print10(int d1,int d2)
{
     if(d1)
     {
         if(d1 > 1)
         {
             cout<<ty[d1]<<" ";
             cout<<unit[d2]<<" ";
         }
         else if(d2)
             cout<<teen[d2];
         else
             cout<<"Ten";
     }
     else if(d2)
     {
          cout<<unit[d2];
     }
}


string lengthFive(string number)
{
       int digit5,digit4,digit3,digit2,digit1;
       cout<<"Number is "<<number<<"\n";
       digit1 = number[4] - 48;
       digit2 = number[3] - 48;
       digit3 = number[2] - 48;
       digit4 = number[1] - 48;
       digit5 = number[0] - 48;
       print10000(digit5,digit4);
       print100(digit3);
       print10(digit2,digit1);
}

string lengthFour(string number)
{
       int digit4 = number[0] - 48;
       int digit3 = number[1] - 48;
       int digit2 = number[2] - 48;
       int digit1 = number[3] - 48;
       print1000(digit4);
       print100(digit3);
       print10(digit2,digit1);
}
string lengthThree(string number)
{
       int digit3 = number[0] - 48;
       int digit2 = number[1] - 48;
       int digit1 = number[2] - 48;
       print100(digit3);
       print10(digit2,digit1);
}

string lengthTwo(string number)
{
       int digit2 = number[0] - 48;
       int digit1 = number[1] - 48;
       print10(digit2,digit1);
}

string lengthOne(string number)
{
       int digit1 = number[0] - 48;
       cout<<unit[digit1];
}



int main()
{
    int n = 10002;

    if(!n)
    {
         cout<<"zero";
         return 0;
    }
    int len = countDigits(n);
    string number = numToString(n);
    switch(len)
    {
         case 1: lengthOne(number);break;
         case 2: lengthTwo(number);break;
         case 3: lengthThree(number);break;
         case 4: lengthFour(number);break;
         case 5: lengthFive(number);break;
         default: cout<<"Invalid";
    }
    system("pause");
}

Checking Parity.

#include <iostream>
using namespace std;

int setParity(int n)
{
     int number = 1;
     number = number<<8 ;
     return (n|number);
}

bool isParitySet(int n)
{
     int number = 128;
     if(number && n)
         return true;
     else
         return false;
}

int countOnes(int n)
{
    int number = 1;
    int count = 0;
    for(int i=0; i<7; i++)
    {
            if(number & n)
            {
                      count++;
            }
            number = number<<1;
    }
    return count;
}


int main()
{
    int n = 2;
    if(countOnes(n) % 2 == 0)
    {
        if(isParitySet(n))
        {
             n = n ^ 128;;
        }
        cout<<n;
    }
    else
    {
        cout<<"INVALLID NUMBER";
    }
    system("pause");
}

Parity Bit for 7-bit Integer.

#include <iostream>
using namespace std;

int setParity(int n)
{
     int number = 1;
     number = number<<7 ;
     return (n|number);
}

int countOnes(int n)
{
    int number = 1;
    int count = 0;
    for(int i=0; i<7; i++)
    {
            if(number & n)
            {
                      count++;
            }
            number = number<<1;
    }
    return count;
}

int main()
{
    int n = 11;
    if(countOnes(n)%2 ==1)
        n = setParity(n);
    cout<<n;
    system("pause");
}

Implementation of K-DTrees (2-D)

/*
    * If all points are in k – dimensions then Select one of the dimension for a level.
    * Get median element in selected dimension.
    * Push all points smaller than median elements in left sub tree and all greater points in right sub tree.
    * Recursively call the buildTree function with leftSubset and Set leftChild of curNode.
    * Recursively call the buildTree function with rightSubset and set rightChild of curNode.
*/

#include <iostream>
#include <vector>

using namespace std;

class Point
{
public:
       int x;
       int y;
     
       Point()
       {
           x = 0;
           y = 0;
       }
     
       Point(int xp, int yp)
       {
           x = xp;
           y = yp;
       }
};

class TreeNode
{
public:
      Point p;
      TreeNode *left;
      TreeNode *right;
         
      TreeNode()
      {
         left = NULL;
         right = NULL;
      }
   
      TreeNode(Point pt)
      {
          p = pt;
          left = NULL;
          right = NULL;
      }
};

class KDTree
{
      TreeNode *root;
public:
      KDTree()
      {
           root = NULL;
      }
   
      TreeNode* getRoot()
      {      
          return root;
      }
   
      TreeNode* createNode(Point ptr)
      {
           TreeNode *n = new TreeNode(ptr);
           return n;
      }
   
      void CreateLeftRightSubset(vector <Point> PointSet, Point median, vector <Point> &leftSet, vector <Point> &rightSet, int depth)
      {
           // Check x coordinates
           if(depth %2 == 0)
           {
                // Push all points having x coordinate
                // less than median to leftSet and rest to right set
                for(int i=0; i < PointSet.size() ; i++)
                {
                     // Skip median.
                     if(PointSet[i].x == median.x && PointSet[i].y == median.y )
                         continue;
                     if(PointSet[i].x < median.x)
                         leftSet.push_back(PointSet[i]);
                     else
                         rightSet.push_back(PointSet[i]);
                }
           }
           // Check y coordinates
           else
           {
                // Push all points having y coordinate
                // less than median to leftSet and rest to rightSet.
                for(int i=0; i < PointSet.size() ; i++)
                {
                     // Skip median.
                     if(PointSet[i].x == median.x && PointSet[i].y == median.y )
                         continue;
                     if(PointSet[i].y < median.y)
                         leftSet.push_back(PointSet[i]);
                     else
                         rightSet.push_back(PointSet[i]);
                }
           }
      }
   
      // Sort vector on x coordinates
      void sortX(vector <Point> &PointSet);

      // Sort vector on y coordinates
      void sortY(vector <Point> &PointSet);
   
      // Return median of all points in PointSet.
      Point getMedian(vector <Point> &PointSet , int depth)
      {
            //Median of x coordinates.
            if(depth % 2 ==0 )
            {
                sortX(PointSet);
                Point M = PointSet[PointSet.size()/2];
                // To prevent infinite recurrence
                if(M.x > PointSet[0].x)
                {
                    return M;
                }
                M.x = M.x+1;
                return M;
            }
            //Median of y coordinates.
            else
            {
                sortY(PointSet);
                Point M = PointSet[PointSet.size()/2];
                // TO prevent infinite recurrence
                if(M.y > PointSet[0].y)
                {
                     return M;
                }
                M.y = M.y+1;
                return M;
            }
      }
   
      TreeNode* buildTree(vector <Point> PointSet , int depth)
      {
           if(PointSet.size() == 1)
               return (createNode(PointSet[0]));

           Point M = getMedian(PointSet,depth);
           TreeNode* curNode = createNode(M);
           if(isEmpty())
                root = curNode;
           vector <Point> leftSet;
           vector <Point> rightSet;
         
           CreateLeftRightSubset(PointSet,M,leftSet,rightSet,depth);
           if(leftSet.size() != 0)
                      curNode->left = buildTree(leftSet, depth+1);
           if(rightSet.size() != 0)
                      curNode->right = buildTree(rightSet, depth+1);
           return curNode;
      }
   
};

int main()
{
    vector <Point> v;
    v.push_back(Point(6,1));
    v.push_back(Point(5,5));
    v.push_back(Point(9,6));
    v.push_back(Point(3,6));
    v.push_back(Point(4,9));
    v.push_back(Point(4,0));
    v.push_back(Point(7,9));
    v.push_back(Point(2,9));
    KDTree tree;
    tree.buildTree(v,0);
    tree.preorder(tree.getRoot());
    system("pause");
}

Print encoding for an Array: Rules: consider BST made from given array. Let say number x is present in the BST and to reach x, If you go right print 1, if left then 0.Now you are given an index i in the array A (so x = A[i]) and print the encoding without constructing BST to reach x and without space with least time complexity.

/*    
      ALGORITHM
      1. Scan array from left to right.
      2. Keep 2 variables min = INT_MIN and max = INT_MAX
                min and max are used to keep track of whether the subtree of current node will store desired number searchNumber.
      3. If value of current elements is between min and max, then subtree of this node will contain searchNumber.
      4. If search number is less than current element, then update min = currentElement and print 1  since it will take right path.
      5. If search number is greater than current element then update max = currentElement and print 0, since it will take left path.
     
      COMPLEXITY
      Time  : O(n)
      Space: O(1)
*/

    #include <iostream>
    #include <climits>
   
    using namespace std;
   
    int main()
    {
            int a[]={50,30,10,20,70,60,55,65,63,80};
            int searchNumber = 63;
            int size = sizeof(a)/sizeof(a[0]);
            int min = INT_MIN;
            int max = INT_MAX;
            for(int i=0; i<size && a[i] != searchNumber ; i++)
            {
                 if(a[i] >min && a[i] < max)
                 {
                     if(a[i] < searchNumber)
                     {
                        min = a[i];
                        cout<<" 1";
                     }
                     else
                     {
                         max = a[i];
                         cout<<" 0";
                     }
                 }
            }  
        system("pause");
    }

Implementation of SkipList Datastructure.

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

class skipNode
{
private:
        int data;
        int height;
        skipNode **forward;
public:
        skipNode(int d,int h)
        {
            data = d;
            height = h;
            forward = new skipNode*[height];
        }
        
        // Return max height of skipList Node.
        int getHeight()
        {
            return height;
        }
        
        // Set data value of skipList Node.
        void setData(int number)
        {
             data =  number;
        }
        
        // Return Data value of skipList Node.
        int getData()
        {
            return data;
        }
        
        // Set forward[pos] = ptr
        void setForwardLink(skipNode *ptr, int pos)
        {
             forward[pos] = ptr;
        }
        
        // Return forward[index]
        skipNode* getForwardLink(int index)
        {
             return forward[index];
        }
};

class skipList
{
private:
        int maxHeight;
        skipNode *head;
        skipNode *tail;
        
        // static int count to be used as seed to srand
        static int count;
public:
        skipList()
        {
             maxHeight = 5;
             head = new skipNode(INT_MIN,maxHeight);
             tail = new skipNode(INT_MAX,maxHeight);
             for(int i=0; i<maxHeight; i++)
             {
                 head->setForwardLink(tail,i);
                 tail->setForwardLink(NULL,i);
             }
        }
        
        // Generate a random number betweem 1 - maxHeight.
        int getHeight()
        {
            count++;
            srand(count);
            return ((rand() % maxHeight) +1);
        }
        
        // Traverse and print all nodes at a level.
        void levelTraversal()
        {
             for(int level = maxHeight-1; level >=0 ; level--)
             {
                  cout<<"nLevel = "<<level;
                  skipNode *next = head->getForwardLink(level);
                  while(next != tail )
                  {
                      cout<<"t"<<next->getData();
                      next = next->getForwardLink(level);
                  }
             }
        }
        
        void insertNode(int val)
        {
             // Check if already Present.
             if(searchNode(val))
             {
                 return;
             }
             
             // If not get Random height for New Node.
             int h = getHeight();
             skipNode *newNode = new skipNode(val,h);
             
             // Need to update nodes forward pointer to point to new node.
             skipNode *curNode = head;
             for(int i=h-1; i>=0; i--)
             {
                  while(curNode->getForwardLink(i) != tail && curNode->getForwardLink(i)->getData() < val)
                  {
                      curNode = curNode->getForwardLink(i);
                  }
                  // curNode represents node at level i whose forward[i] = new Node . 
                  // copy newNode.forward[i] = curNode.forward[i]
                  newNode->setForwardLink(curNode->getForwardLink(i),i);
                  curNode->setForwardLink(newNode,i);
             }
        }
        
        // Search value if present return node else return NULL.
        skipNode* searchNode(int val)
        {
             // Start from head Node and search at topMost level.
             skipNode *ptr = head;
             for(int level = maxHeight-1; level >=0; level--)
             {
                 skipNode *nextNode = ptr->getForwardLink(level);
                 // Narrow down search from ptr to tail or node having value >= val
                 while(nextNode->getData() < val && nextNode != tail)
                 {
                      ptr = nextNode;
                      nextNode = nextNode->getForwardLink(level);
                 }
                 if(nextNode->getData() == val)
                      return nextNode;
             }
             return NULL;
        }
        
        void deleteNode(int val)
        {
             // check if node exist
             skipNode *toDelete = searchNode(val);
             if(toDelete)
             {
                 // Get height of node to be deleted.
                 int level = toDelete->getHeight();
                 
                 // forward pointer of nodes just before delete node neeeds updation of forward pointer.
                 skipNode *curNode = head;
                 for(int i=level-1; i>=0; i--)
                 {
                      while(curNode->getForwardLink(i) != toDelete)
                      {
                          curNode = curNode->getForwardLink(i);
                      } 
                      curNode->setForwardLink(toDelete->getForwardLink(i),i);
                 }
             }
             else
             {
                 return;
             }
        }
        
        void displaySkipList()
        {             
             for(int level = maxHeight-1; level >=0; level--)
             {
                 cout<<"n";
                 skipNode* ptr = head;
                 while(ptr != tail)
                 {
                      cout<<" "<<ptr->getData();
                      ptr = ptr->getForwardLink(level);
                 }
             }
        }
};

int skipList::count = 0;
int main()
{
    skipList list ;
    list.insertNode(10);
    list.insertNode(20);
    list.insertNode(40);
    list.insertNode(50);
    list.insertNode(60);
    list.insertNode(70);
    list.insertNode(30);
    list.levelTraversal();
    list.deleteNode(40);
    cout<<"nnAFTER DELETION";
    list.levelTraversal();
    system("pause");
}

Given an array of n elements, with all elements ranging from 1 to n except one is missing and one is duplicated; find the duplicate and missing element.

/*
     ALGORITHM
     ---------
     If we can get the duplicate element, missing elements can be found out by adding all the elements and subtracting from (n(n+1))/2 = sum of 1st n elements.
     Add the difference to duplicate element.
     1. Scan array from left to right.
                Pos =0 ; while pos < N
     2. Get value of current element and also its position if the array is in sorted order (desiredPos)
                which will be arr[pos]-1 (since array index begins with 0).
         a. If element is at its correct position
                If desiredPos == arr[pos-1] then move on to next element pos++.
         b. Else check value at desiredPos if it is correct then this is a case of duplicate element. Return duplicate value.
                Else if (arr[desiredPos] == arr[pos]) return arr[pos]
         c. Else swap arr[pos] and arr[desiredPos] and repeat step 2 .
   
     COMPLEXITY
     ----------
     Time  : O(n)
     Space : O(1)
   
*/

    int getDuplicate(int arr[],int size)
    {
        int pos = 0;
        while(pos <size)
        {
             int desiredPos = arr[pos]-1;
             if(pos == desiredPos)
             {
                 pos++;
             }
             else if(arr[desiredPos] == arr[pos])
                     return arr[pos];
             else
             {
                 swap(arr,pos,desiredPos);
             }
        }
        return -1;
    }

/*
    ALTERNATE METHOD
    ----------------
    Let the missing number be x and duplicate element be y.
   
    Sum of all elements = 1+…+n – x + y (y is duplicate and x is missing).
    Sum (constant) = (n(n+1))/2 –x + y
    Let constant C1 = sum and constant C2 = (n(n+1))/2.
    Y – x = C1-C2.
   
    Product of all elements =( 1……n *y )/x
    Product = (n! * y )/x
    Let constant C3 = product and constant C4 = n!.
   
    C3/C4 = y/x
    (C3 * x)/C4 = y.
   
    2 variables and 2 equations, Substitute value of y in 1st equation and solve for x and y.
   
   
    COMPLEXITY
    Time  : O(n)
    Space : O(1)
*/

Given a number print the next largest number and just smallest number that have same number of 1's in binary representation.

   /*
        NEXT GREATER NUMBER
        -------------------
        1. Scan number from right to left bits.
        2. As soon as first 1 bit is encountered set the encounterFlag.
        3. If encounterFlag is set Turn on the first 0 bit.
        4. Turn off the 1 bit on right of above bit.
        5. Make this as small as possible to get just next larger number, Push all 1's after this bit to right end.
       
        NEXT SMALLER NUMBER
        -------------------
        1. Scan number from right to left bits.
        2. As soon as first 0 bit is encountered set the encounterFlag.
        3. If encounterFlag is set Turn off the first 1 bit.
        4. Turn on the 0 bit on right of above bit.
        5. Make this as large as possible to get just previous smaller number, Push all 1's after this bit to as much left as possible.
    */
    #include <iostream>
    using namespace std;
   
    //check if bit at pos is 1 or 0
    bool isSet(int number , int pos)
    {
         if( (number & (1<<pos)) > 0)
             return true;
         return false;
    }
   
    //set Bit at index pos to 1
    int setBit(int number , int pos)
    {
        number |= 1<<pos;
        return number;
    }
   
    //set bit at index pos to 0
    int unsetBit(int number, int pos)
    {
        number &= ~(1<<pos);
        return number;
    }
   
    //Return Next Greater number
    int getNextGreater(int number)
    {
        if(number <= 0)
            return -1;
        int maxIndex;
        int countOnes = 0;
        int pos = 0;
       
        //Scan number from right to left bit.
        for(bool encounterFlag = false; pos < 32 ; pos++)
        {
                if(encounterFlag)
                {
                     if( !isSet(number , pos) )
                     {
                         // set first 0 bit after encounteredFlag is true 
                         number = setBit(number, pos);
                         // unset 1 bit immediately right of the above bit. 
                         number = unsetBit(number, --pos);
                         break;
                     }
                     else
                         continue;
                }
                     //As soon as a 1 is encountered, encounteredFlag is set.
                if( isSet(number , pos))
                     encounterFlag = true;
        }
       
        //Count no. of 1's after maxIndex.
        for(int i=pos -1; i>=0 ; i--)
        {
                if(isSet(number, i))
                    countOnes++;
        }
        //Pushing all 1's to left.
        for(int j=pos -1; j>= countOnes; j--)
            number = unsetBit(number, j);
       
        for(int k=countOnes-1 ; k>=0; k--)
            number = setBit(number, k);
       
        return number;
    }
   
    int getNextSmaller(int number)
    {
        if(number < 0)
            return -1;
        int maxIndex;
        int countOnes = 0;
        int pos = 0;
        for(bool encounterFlag = false; pos < 32; pos++)
        {
             if(encounterFlag)
             {
                  if(isSet(number, pos))
                  {
                      //After encounterFlag is set Turnoff next 1 Bit.
                      number = unsetBit(number, pos);
                      //Turn on 0 bit on right of this bit.
                      number = setBit(number, --pos);
                      break;
                  }
                  else
                      continue;
             }
             //Set encounter flag after first zero is encountered.
             if(!isSet(number,pos))
             {
                  encounterFlag = true;
             }
            
        }
       
        //Count no. of 1's after maxIndex.
        for(int i=pos -1; i>=0 ; i--)
        {
             if(isSet(number, i))
                 countOnes++;
        }
      
        //Pushing all 1's to left.
        for(int j=pos -1; j>= countOnes; j--)
            number = setBit(number, j);
       
        for(int k=countOnes-1 ; k>=0; k--)
            number = unsetBit(number, k);
       
        return number;
       
    }
   
    int main()
    {
        cout<<getNextGreater(18)<<endl;
        cout<<getNextSmaller(18)<<endl;
        system("pause");
    }