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