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

Reconstruct the itinerary in order

Given an bunch of airline tickets with [from, to], for example [MUC, LHR], [CDG, MUC], [SFO, SJC], [LHR, SFO]
please reconstruct the itinerary in order, 
[ CDG, MUC, LHR, SFO, SJC ]. 
Note: tickets can be represented as nodes

#!/usr/bin/env python

import sys

# Reads the given file which contains airline tickets
# and returns 2 hash,
#  * (1) with all the ticket info
#  * (2) wth the starting and ending points
def getTicketsFromFile(filename):
    lines = []

    # Read the file
    with open(filename, "r") as fp:
        lines = lines = fp.readlines()

    lines = map(lambda s: s.strip(), lines)

    tickets = {}
    points = {}
    for line in lines:
        if line !="":
            point = map(lambda s: s.strip(), line[1:-1].split(","))
            tickets[point[0]] = point[1]

            # create 2 nodes for each ticket (start, end) and
            # do this for all the tickets
            for p in point:
                try:
                    # Delete the key from the points if it exists to find the start and end
                    # points for the entire trip.
                    del points[p]
                except:
                    points[p] = ""

    # Find the starting point
    for k in points.keys():
        if k in tickets.keys():
            startPoint = k
            break
        
    return (tickets, startPoint)


if __name__ == "__main__":
    (tickets, startPoint) = getTicketsFromFile(sys.argv[1])

    # print the order
    point = startPoint
    while True:
        print point,
        
        try:
            point = tickets[point]
        except:
            break

Write a function that subtract two integer streams

You are given two streams 's_a' and 's_b' of digits. Each stream represents an integer 'a' and 'b' from its less significant digit to the most significant digit.
For example, integer 2048 is represented in the stream as 8, 4, 0, 2. 

Write a function that subtract two integers 'a - b' and returns the result as a string. You are not allowed to buffer entire 'a' or 'b' into a single string, i.e. you may access only a single digit per stream at time (imagine that 'a' and 'b' are stored in huge files). You may assume that 'a>=b'.

#include <stdio.h>

/* Subtracts two single digits, prints the reminder and returns 1(carry) if a<b */
int subtract(char c_a, char c_b)
{
  /* Convert the char to interger */
  int i_a = c_a - '0';
  int i_b = c_b - '0';
  int ret = 0;

  /* If a<b, increase 'a' by 10 and return 1(carry) to subtract it from 'a' of the next set */
  if (i_a < i_b) {
    i_a += 10;
    ret = 1;
  }
  
  printf ("%d", i_a - i_b);

  return ret;
}


int main(int agrc, char **argv)
{
  /* Get the two operand streams from input arguments */
  char *s_a = argv[1];
  char *s_b = argv[2];

  int carry_one = 0;
  
  /* Pass one char at a time from each input arguments to function subtract */
  while(*s_b != '\0'){
    /* Subtract carry_one from first operand before sending it to function subtract */
    carry_one = subtract(*s_a - carry_one, *s_b);
    s_a++;
    s_b++;
  }

  /* Print the remining digits from the first operand */
  while(*s_a != '\0'){
    printf("%c", *s_a - carry_one);
    s_a++;
    carry_one = 0;
  }
  printf("\n");
  
  return 0;
}

Output:

  $ ./str_subtract 00051 1005 | rev
  09999
  
  $ ./str_subtract 5 3 | rev
  2
  
  $ ./str_subtract 1234 1233 | rev
  1000

Find the conflicting appointments

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

/* 
   Time interval format: yyymmddhhmm yyyymmddhhmm 

   Example Input:
   --------------
   4
   5 6
   1 9
   7 8
   2 10

   Process:
   --------

   Data Structure
   time_node to store the intervals
    ------------------------------
   | timestamp | is_start | index |
    ------------------------------

   Step 1:
   -------

   - stores the timestamps into an array
   
    -----------   -----------   -----------   -----------
   | 5 | 1 | 0 | | 6 | 0 | 0 | | 1 | 1 | 1 | | 9 | 0 | 1 |
    -----------   -----------   -----------   -----------
         0             1             2             3

    -----------   -----------   -----------   ------------
   | 7 | 1 | 2 | | 8 | 0 | 2 | | 2 | 1 | 3 | | 10 | 0 | 3 |
    -----------   -----------   -----------   ------------
         4             5             6              7

   Step 2:
   -------

   - Sort the array wrt the timestamp value

    -----------   -----------   -----------   -----------
   | 1 | 1 | 1 | | 2 | 1 | 3 | | 5 | 1 | 0 | | 6 | 0 | 0 |
    -----------   -----------   -----------   -----------
         0             1             2             3

    -----------   -----------   -----------   ------------
   | 7 | 1 | 2 | | 8 | 0 | 2 | | 9 | 0 | 1 | | 10 | 0 | 3 |
    -----------   -----------   -----------   ------------
         4             5             6              7
   
   Step 3:
   -------

     3.1 Push the index value to the index_list if it is the start of an interval
     3.2 Delete the index value from the index_list if it is the end of an interval
       3.2.1 add all the index values from the index_list to the conflict_list of the this interval
       3.2.2 add this interval index into the conflict_list of all the index values in the index_list
*/


/* Index to find parent and the childern */
#define LEFT(a) (2*(a+1) -1)
#define RIGHT(a) (2*(a+1))
#define PARENT(a) ((a-1)/2)

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

/* To store the calendar appointment intervals */
typedef struct time_node time_node;
struct time_node {
  unsigned long long timestamp;
  bool is_start;
  int index;
};

/* To store the conflicts */
typedef struct index_node index_node;
struct index_node {
  int index;
  index_node *next;
};

/* Swap function */
#define XORSWAP(a, b) ((a.timestamp)^=(b.timestamp),(b.timestamp)^=(a.timestamp),(a.timestamp)^=(b.timestamp), \
                         (a.is_start)^=(b.is_start),(b.is_start)^=(a.is_start),(a.is_start)^=(b.is_start), \
                         (a.index)^=(b.index),(b.index)^=(a.index),(a.index)^=(b.index))

/* Heapify */
void maxheapify (time_node *list, int count, int index)
{
  int left = LEFT (index);
  int right = RIGHT (index);
  
  int largest = index;
  
  if (left <= count-1 && list[left].timestamp > list[largest].timestamp)
    largest = left;
  if (right <= count-1 && list[right].timestamp > list[largest].timestamp)
    largest = right;
  
  if (largest != index)
  {
    XORSWAP (list[index], list[largest]);
    maxheapify (list, count, largest);
  }
}

/* Buids the heap */
void build_max_heap (time_node *list, int count)
{
  for (int i = (count-1)/2; i >= 0; i--)
  {
    maxheapify (list, count, i);
  }  
}

/* Sorts the intervals using heap sort */
void heap_sort (time_node *list, int count)
{
  build_max_heap (list, count);
  
  int tmp_count = count-1;
  for (int i = count-1; i > 0; i--)
  {
    XORSWAP (list[0], list[i]);
    maxheapify (list, i, 0);
  }
}

/* Adds the index node into the list */
bool add_index_node (index_node **list, int index)
{
  if (NULL == *list)
  {
    *list = (index_node *) calloc (1, sizeof (index_node));
    if (NULL == *list)
    {
      fprintf (stderr, "Error: memory allocation failure.");
      return FALSE;
    }
    else
    {
      (*list)->index = index;
      (*list)->next = NULL;
    }
  }
  else
  {
    index_node *t = *list;
    
    while (NULL != t->next)
      t = t->next;

    t->next = (index_node *) calloc (1, sizeof (index_node));
    t = t->next;

    if (NULL == t)
    {
      fprintf (stderr, "Error: memory allocation failure.");
      return FALSE;
    }
    else
    {
      t->index = index;
      t->next = NULL;
    }
  }
  return TRUE;
}

/* Deletes the index node from the list */
void delete_index_node (index_node **list, int index)
{
  if (NULL == *list)
  {
    return;
  }
  else
  {
    index_node *t = *list;
    index_node *lbo = *list;

    while (t->index != index)
    {
      if (t->next->next == NULL)
      {
        lbo = t;
      }
      t = t->next;
    }
    
    if (t == *list)
    {
      *list = (*list)->next;
      free (t);
    }
    else if (NULL == t->next)
    {
      lbo->next = NULL;
      free(t);
    }
    else
    {
      t->index = t->next->index;
      index_node *d = t->next;
      t->next = t->next->next;
      free (d);
    }
  }
}

int main (int argc, char **argv)
{
  time_node *interval_list = NULL;

  /* Reads the input file for the intervals */
  FILE *fp = NULL;
  fp = fopen ("intervals.txt", "r");
  if (NULL == fp)
  {
    fprintf (stderr, "Error: Could not read the file.");
    return -1;
  }

  int count = 0;
  int readcount = 0;
  int tmp_count = 0;
  
  /* Reads the count */
  readcount = fscanf (fp, "%d", &count);
  if (0 >= readcount)
  {
    fprintf (stderr, "Error: Nothing in the file.");
    return -2;
  }
  
  interval_list = (time_node *) calloc (count*2, sizeof (time_node));
  if (NULL == interval_list)
  {
    fprintf (stderr, "Error: Memory allocation failed.");
    return -3;
  }

  /* Reads the intervals */
  printf ("Input:\n");
  for(tmp_count = 0; tmp_count < count; tmp_count++)
  {
    if (feof(fp))
    {
      break;
    }
    unsigned long long start = 0;
    unsigned long long end = 0;
    readcount = fscanf (fp, "%llu %llu", &start, &end);
    printf ("%5d) : %llu <-> %llu\n", tmp_count+1, start, end);
    interval_list[tmp_count*2].timestamp = start;
    interval_list[tmp_count*2].is_start = TRUE;
    interval_list[tmp_count*2].index = tmp_count;
    interval_list[tmp_count*2+1].timestamp = end;
    interval_list[tmp_count*2+1].is_start = FALSE;
    interval_list[tmp_count*2+1].index = tmp_count;
  }
  printf ("\n");
  fclose(fp);

  /* Sort the timestamp values */
  heap_sort (interval_list, count*2);
  
  index_node *index_list = NULL;
  index_node **conflict_list = NULL;
  conflict_list = (index_node **) calloc (count, sizeof (index_node*));
  if (NULL == conflict_list)
  {
    fprintf (stderr, "Error: Memory allocation failed.");
    return -3;
  }

  /* main loop to find the conflicts */
  for (int i = 0; i < count*2; i++)
  {
    if (interval_list[i].is_start == TRUE)
    {
      if (FALSE == add_index_node (&index_list, interval_list[i].index))
      {
        fprintf (stderr, "Error: Memory allocation failed.");
        return -3;
      }
    }
    else
    {
      delete_index_node (&index_list, interval_list[i].index);

      index_node *t = index_list;
      while (t)
      {
        if (FALSE == add_index_node (&(conflict_list[interval_list[i].index]), t->index) || 
            FALSE == add_index_node (&(conflict_list[t->index]), interval_list[i].index))
        {
          fprintf (stderr, "Error: Memory allocation failed.");
          return -3;
        }
        t = t->next;
      }
    }
  }

  /* Print the result */
  printf ("Conflicts:\n");
  for (int i = 0; i < count; i++)
  {
    printf ("%5d : ", i+1);
    index_node *t = conflict_list[i];
    while (t)
    {
      printf ("%d ", t->index+1);
      t = t->next;
    }
    printf ("\n");
  }
  return 0;
}

We can use self-balanced binary search tree to keep the index_list to get a better time complexity.

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

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

Largest Sum Subarray

You are given a binary array with N elements: d[0], d[1], ... d[N - 1].
d[i] can only be 0 or 1
You can perform AT MOST one move on the array: choose any two integers [L, R], and flip all the elements between (and including) the L-th and R-th bits. L and R represent the left-most and right-most index of the bits marking the boundaries of the segment which you have decided to flip.
What is the maximum number of '1'-bits (indicated by S) which you can obtain in the final bit-string?

import copy

def max_subarray(array):
    # Start & End indices of the max subarray 
    start = end = 0

    # Temporary Variable to hold the new Start
    t_start = 0

    # Holds the latest max sum
    # starts with array[0] because it addresses the 
    # case where all the elements in the array are
    # negative numbers.
    max_ending_here = max_so_far = array[0]

    # Holds the max subarray
    # Starts with the first element array[0]
    maxsubarray = t_maxsubarray = [array[0]]

    for index, x in enumerate(array[1:]):
        # max(x, max_ending_here + x) => max_ending_here
        if x > max_ending_here + x:
            # This is where the set starts
            t_start = index + 1
            t_maxsubarray = []
            max_ending_here = x
        else:
            max_ending_here = max_ending_here + x

        # max(max_so_far, max_ending_here) => max_so_far
        if max_so_far < max_ending_here:
            # The set ends here
            t_maxsubarray.append(x)
            # This is the latest max subarray
            maxsubarray = copy.deepcopy(t_maxsubarray)
            # Update the new Start index
            start = t_start
            # Update the new End index
            end = index + 1
            max_so_far = max_ending_here
        else:
            t_maxsubarray.append(x)

    print maxsubarray
    print start, end
    print max_so_far

Reference: [WIKI] Maximum Subarray Problem