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

Given a max-heap represented as an array, return the kth largest element without modifying the heap.

  Here are all the header files included to make the compilation successful.
 

    
#include <iostream>
#include <vector>
#include <stack>

#include <math.h>
using namespace std;
 

    
  This is how we heapify the given array of elements.
  

#define SWAP(x,y) \
  x = x ^ y;      \
  y = x ^ y;      \
  x = x ^ y;      \

void siftDown(vector<int> &v, int start, int end)
{
  int root = start;

  while (root*2+1 <= end){
    int child = root*2+1;
    int swap = root;

    if (child <= end && v[swap] < v[child]) {
      swap = child;
    }
    if(child+1 <= end && v[swap] < v[child+1]) {
      swap = child+1;
    }

    if (swap != root) {
      SWAP(v[root], v[swap]);
      root = swap;
    } else {
      return;
    }
  }
}

void heapify(vector<int> &v, int count)
{

  int start = floor((count-2)/2);

  while (start >=0 ) {
    siftDown(v, start, count-1);
    start = start - 1;
  }
}

 

    
  We modify the stack functionality a little to maintain the element order in the stack with the incoming elements.
  

void insertToStack(vector<int> &v, stack<int> &s, int val)
{
  /* Temporary vector to keep the order from the stack */
  vector<int> tmp;

  /* Pop the elements till new value finds its place */
  while(!s.empty() && v[s.top()] > v[val]){
    tmp.insert(tmp.begin(), s.top());
    s.pop();
  }

  /* push the new value into the stack */
  s.push(val);

  /* Push all the elements in the same order 
     which are previously popped out */
  vector<int>::iterator it;
  for (it=tmp.begin(); it<tmp.end(); it++) {
    s.push(*it);
  }
}

 

    
  This function traverses the heap to find the Kth element in log time
  

int find(vector<int> &v, stack<int> &s, int index, int pos, int count)
{
  /* If current element is smaller than the element in the stack,
     update the current element with the top of the stack and 
     push the current element into the stack*/
  if (!s.empty() && v[s.top()] > v[index]) {
    insertToStack(v, s, index);
    index = s.top();
  }

  if (pos == count) {
    /* If the count reaches pos, return the current element */
    return v[index];
  } else {
    int lchild = index*2+1;
    int rchild = lchild+1;

    /* Check if the current element has right child */
    if (rchild > v.size()-1) {
      
      /* Check if the current element has left child */
      if (lchild > v.size()-1) {
        
        /* The current element is the leaf node. Get the top of 
           the stack to proceed further */
        index = s.top();
        s.pop();
      } else {
        
        /* The current element has only left child. */
        if (s.empty() || v[lchild] > v[s.top()]) {
          index = lchild;
        } else {
          index = s.top();
          s.pop();
          insertToStack(v, s, lchild);
        }
      }
    } else {
      
      /* Find the max and min from the child nodes */
      int max = 0;
      int min = 0;
      if (v[lchild] > v[rchild]) {
        max = lchild;
        min = rchild;
      } else {
        min = lchild;
        max = rchild;
      }

      /* Find the highest element among the child nodes & the top
         of the stack, Update the current element with the highest 
         element and push the other two elements into the stack */
      if (s.empty()) {
        insertToStack(v, s, min);
        index = max;
      } else {
        int top = s.top();
        if (v[max] < v[top]) {
          index = top;
          s.pop();
          insertToStack(v, s, min);
          insertToStack(v, s, max);
        } else {
          index = max;
          if (v[min] > v[top]) {
            insertToStack(v, s, min);
          } else {
            s.pop();
            insertToStack(v, s, min);
            insertToStack(v, s, top);
          }
        }
      }
    }
    
    /* Call "find" recursively till "count" reaches "pos" */
    return find(v, s, index, pos, count+1);
  }
}

int findElement(vector<int> &v, int pos)
{
  /* Start with am empty stack */
  stack<int> s;
  return find(v, s, 0, pos, 1);
}
 

  You are NOT A FAN of recursion? Here you go,
 

@@ -1,5 +1,6 @@
 int find(vector<int> &v, stack<int> &s, int index, int pos, int count)
 {
+  while (count <= v.size()) {
   /* If current element is smaller than the element in the stack,
      update the current element with the top of the stack and 
      push the current element into the stack*/
@@ -74,8 +75,7 @@
         }
       }
     }
-    
-    /* Call "find" recursively till "count" reaches "pos" */
-    return find(v, s, index, pos, count+1);
+    }
+    count++:
   }
 }
 

  Here is the main function
    

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

  /* Store the inputs into a vector */
  vector<int> input;
  int total= stoi(argv[1]);
  for(int c=0; c<total; c++){
    input.insert(input.end(), stoi(argv[c+2]));
  }

  /* Print them */
  vector<int>::iterator it;
  cout << "     my vector contains:";
  for (it=input.begin(); it<input.end(); it++)
    cout << ' ' << *it;
  cout << endl;

  /* Heapify the input vector */ 
  heapify(input, total);
  cout << "my heap vector contains:";
  for (it=input.begin(); it<input.end(); it++)
    cout << ' ' << *it;
  cout << endl << endl;

  for (int count=1; count<=total; count++) {
    int ret = findElement(input, count);
    cout << "(" << count << "):  " << ret << endl;
  }
  return 0;
}

Output:

$ ./kthInHeap 4 10 6 9 1
     my vector contains: 10 6 9 1
my heap vector contains: 10 6 9 1

(1):  10
(2):  9
(3):  6
(4):  1


$ ./kthInHeap 7 5 6 1 3 8 9 2
     my vector contains: 5 6 1 3 8 9 2
my heap vector contains: 9 8 5 3 6 1 2

(1):  9
(2):  8
(3):  6
(4):  5
(5):  3
(6):  2
(7):  1


$ ./kthInHeap 8 6 5 3 1 8 7 2 4
     my vector contains: 6 5 3 1 8 7 2 4
my heap vector contains: 8 6 7 4 5 3 2 1

(1):  8
(2):  7
(3):  6
(4):  5
(5):  4
(6):  3
(7):  2
(8):  1

In a given 2D binary array, find the area of the biggest rectangle which is filled with 1

   Given array

   1 1 0 1 0 1
   1 1 0 1 1 1
   0 1 1 1 1 1
   0 1 1 1 1 1
   0 0 1 1 1 0
   0 0 0 0 0 0

   Consider each block in the array is an unit and he columns in the array as hanging towers.
   Modify the array in a way that, on each row, the number denotes the height of each column.


   1 1 0 1 0 1
   2 2 0 2 1 2
   0 3 1 3 2 3
   0 4 2 4 3 4
   0 0 3 5 4 0
   0 0 0 0 0 0


   Basic Rules to find the biggest rectangle:
   1. For any tower, the boundaries on each side will be decided by its smaller towers. It means
       that all the towers on each side till we find a smaller tower will be included for the calculation.
   2. Area for the subset equals to (the height of the smaller tower) X (no. of towers in the subset)

   Calculate the area of each subset for each level in the array from top to bottom.

   Level[0] [set 0]              Level[0] [set 1]              Level[0] [set 2]

   1 1 0 1 0 1                   1 1 0 1 0 1                   1 1 0 1 0 1
   ---                                 -                                 -
   2 towers with 1 unit each     1 tower with 1 unit           1 tower with 1 unit
   Maximum Area=2x1=2            Maximum Area=1x1=1            Maximum Area=1x1=1

   Level[0] Maximum Area = 2
   -------------------------------------------------------------------------------
   
   Level[1] [set 0]              Level[1] [set 1]

   2 2 0 2 1 2                   2 2 0 2 1 2
   ---                                 -----
   2 towers with 2 units each    1 tower with 1 unit
   Maximum Area=2x2=4            2 towers with 2 units each
                                 Maximum Area=3x1=3

   For [set 1], even though we have 2 towers with 2 units each in this set, we cannot consider them 
   as a single unit because of the smaller unit's presence in between. So, each tower will be consider 
   as a different subset. But, for the tower with 1 unit has bigger towers around it. So, all the units 
   will be taken (but only one unit from each bigger towers) for the area calculation.

   Level[0] Maximum Area = 4
   -------------------------------------------------------------------------------

   and so on...



int findBigBox (int row, int column, int *matrix)
{
  int max_area = 0;
  int *score = (int *) calloc (row+1, sizeof(int));
  if (NULL != score)
  {
    for (int i=0; i<row; i++)
    {
      for (int j=0; j<column; j++)
      {
        /* Process only if we find 1 */
        if (*(matrix+(i*column)+j) != 0)
        {
          int count = 0;
          int start = j;
          /* Iterate through all the consecutive ones. */
          for (;*(matrix+(i*column)+j) != 0 && j<column; j++)
          {
            /* If it is not the first row, add this element 
               with the previous row element at the same column */
            if (i != 0)
            {
              *(matrix+(i*column)+j) += *(matrix+((i-1)*column)+j);
            }
            *(score+*(matrix+(i*column)+j)) = 1;
          }
          
          getScore (row, column, start, j-1, matrix+(i*column), score);

          for (int s=1; s<=row; s++)
          {
            if (*(score+s))
            {
              int area = s * *(score+s);
              if (max_area < area)
                max_area = area;
            }
          }
          /* Reset the score array to use for the next subset */
          memset (score, 0, (row+1)*sizeof(int));
        }
      }
    }
  }
  free (score);
  
  return max_area;
}



   Here the process of finding the number of towers on each subset for each height is call SCORE.
   This SCORE process can be represented as a tree, which has the following rules,
   1. Node structure
      -> Height
      -> Score
      -> Next
      -> Left
      -> Right
   2. Same numbers on the same set which are non-contiguous will be added as the [Next] node.
   3. Same numbers on the same set which are contiguous will increment the [Score] in the first node.
   4. Taller tower on its left in the set will be added to the [Left] node (child).
   5. Taller tower on its right in the set will be added to the [Right] node (child).
   6. [Score] = [Left]->[score] + [Right]->[score] + no of the same [Height] in the set.

   Example:
   For the below given set,
   3 3 2 3 2 3 1 3 1 3 2 3

   1.    ---------          2.    ---------          3.    ---------
        | H=3|S=1 |              | H=3|S=2 |              | H=2|S=3 |
         ---------                ---------                ---------
                                                             /L
                                                       ---------
                                                      | H=3|S=2 |
                                                       ---------
   In the third step, we move the number 2 as the root and 3 as its left as 3 falls on 2's left in the set and
   3 is bigger than 2.

   4.              --------- 
                  | H=2|S=4 |
                   --------- 
                    /L   \R
            ---------   --------- 
           | H=3|S=2 | | H=3|S=1 |
            ---------   ---------
   We move the number 3 as its right as 3 falls on 2's right in the set

   5.              ---------    N    ---------
                  | H=2|S=5 | ----  | H=2|S=0 |
                   ---------         --------- 
                    /L   \R
            ---------   --------- 
           | H=3|S=2 | | H=3|S=1 |
            ---------   ---------

   We move the number 2 to the [Next] of the existing 2 as they are on the same set still. (Which means it is the ROOT node)
            
   6.              ---------    N    ---------
                  | H=2|S=6 | ----  | H=2|S=0 |
                   ---------         --------- 
                    /L   \R                \R
            ---------   ---------         --------- 
           | H=3|S=2 | | H=3|S=1 |       | H=3|S=1 |
            ---------   ---------         ---------

    This 3 falls on the right side of the second 2, and increase the count on the first 2

    7.             ---------
                  | H=1|S=7 |
                   --------- 
                       /L 
                   ---------    N    ---------
                  | H=2|S=6 | ----  | H=2|S=0 |
                   ---------         --------- 
                    /L   \R                \R
            ---------   ---------         --------- 
           | H=3|S=2 | | H=3|S=1 |       | H=3|S=1 |
            ---------   ---------         ---------
            
   and so on...

   Finally, traverse the tree to find the Maximum SCORE for each height.


void getScore (int row, int column, int start, int end, int *matrix_row, int *score)
{
  /* Intervals to be processed to calculate the score for the number */
  int *currentQ = (int *) calloc (column, sizeof(int));
  /* Intervals to be updated for the next number */
  int *nextQ = (int *) calloc (column, sizeof(int));

  /* Interval counts */
  int currentCount = 1;
  int nextCount = 0;

  /* Start with the whole given set */
  currentQ[0] = start;
  currentQ[1] = end;

  for (int i=1; i<=row; i++)
  {
    if (*(score+i))
    {
      int max = 0;
      for (int c=0; c<currentCount; c++)
      {
        int tmp_score = *(currentQ+(c*2)+1) - *(currentQ+(c*2)) + 1;

        /* Update the temporary max */
        if (max < tmp_score)
        {
          max = tmp_score;
        }

        /* Update the intervals for the next bigger number */
        for (int k=*(currentQ+(c*2)); k<=*(currentQ+(c*2)+1); k++)
        {
          /* Find the start of an interval */
          while (*(matrix_row+k) == i && k<=*(currentQ+(c*2)+1))
          {
            k++;
          }
          
          /* End of the current set */
          if (k > *(currentQ+(c*2)+1))
            break;
          
          *(nextQ+(nextCount*2)) = k;

          /* Find the end of that interval */
          while (*(matrix_row+k) != i && k<=*(currentQ+(c*2)+1)) k++;

          if (k > *(currentQ+(c*2)+1)) // End of the current set
          {
            *(nextQ+(nextCount*2)+1) = k-1;
          }
          else
          {
            *(nextQ+(nextCount*2)+1) = k-1;
          }
          nextCount++;
        }
      }

      int *tmp = currentQ;
      currentQ = nextQ;
      nextQ = tmp;
      
      currentCount = nextCount;
      nextCount = 0;
    
      /* Update the score */
      *(score+i) = max;
    }
  }
}

Associative Arrays in Bash

#!/bin/bash

# -A declares v to be an associative array
# [key]=vlaue
declare -A v
v=(
    ["var1"]="variable 01"
    ["var2"]="variable 02"
    ["var3"]="variable 03"
    ["var4"]="variable 01"
)

# ${!v[@]} gives us the keys
# to access the value use ${v[key]}
for k in ${!v[@]}
do
    echo "v: [$k] => [${v[$k]}]"
done


# key can have spaces
declare -A vws
vws=(
    ["var 1"]="variable 01"
    ["var 2"]="variable 02"
)

echo "vsw: [var 1] => [${vws['var 1']}]"
echo "vsw: [var 2] => [${vws['var 2']}]"

Output:

v: [var1] => [variable 01]
v: [var3] => [variable 03]
v: [var2] => [variable 02]
v: [var4] => [variable 01]
vsw: [var 1] => [variable 01]
vsw: [var 2] => [variable 02]

Reference: http://www.linuxjournal.com/content/bash-associative-arrays