Young Tableau

Young tableau consists of rows and columns of numbers in the form of a matrix. The special property of young tableau is that its rows and columns are sorted. Young tableau can also function as a min heap. There are different interesting algorithms relating to young tableau.

Example of young tableau.

1 2 3
4 6 7
5 7 12

It's clear from the example that each row and column is sorted.

Here is one interesting problem on Young Tableau: How to find an element in an Young Tableau?

Naive search on the table would require O(mn) time. Where m is the number of rows and n is the number of columns. Can we do bit better? Turns out we can. The trick is to start from the top right corner> if the element we are searching for is greater we move down in the column. If the element we are searching for is smaller we move left in the row. We repeat the procedure until we find the element or we end up in a row or column beyond the table. This would translate to a simple code below:

The example assumes 3 X 3 matrix for simplicity. row is the number of rows and col is the number of columns in the matrix and n is the element being looked for.

int find_n(int x[][3],int row, int col, int n) {

 int r =0 , c = col -1;
 while( r < row && col >=0) {
  if(x[r][c] == n)
   return n;
  else if ( x[r][c] > n)
   c--;
  else
   r++;
 }
 return -1;
}

Another problem in Young Tableau is extracting minimum element. The minimum element is the element in (0,0) position. The main problem is replacing the spot (0,0) after minimum element has been removed. The code is given below (sorry that i have it in Java because I did these two things separately but still i believe it is simple enough so i thought it was not necessary to put both of these in same language)

/*
a is young tableau, i and j are current position in the tableau that we are filling
m and n are number of rows and column
*/
void youngify(int[][] a, int i, int j, int m, int n) {
  if (i > m || j > n)
   return;

  int x = -1, y = -1;

  if (i + 1 < m && a[i + 1][j] < a[i][j]) {
   a[i][j] = a[i + 1][j];
   x = i + 1;
   y = j;

  }
  if (j + 1 < n && a[i][j + 1] < a[i][j]) {
   a[i][j] = a[i][j + 1];
   x = i;
   y = j + 1;
  }

  if (x != -1) {
   //the empty space is filled with marked
   //by maximum value a integer can hold
   a[x][y] = Integer.MAX_VALUE;
   youngify(a, x, y, m, n);
  }

 }

Inserting an element into non full young tableau follows the similar process as extracting minimum element. The idea is to put the element into last row and column and move it upto the position where is should be.

Sorting can also be implemented for n X n young tableau in O(n ^3) time by using the operation by which we extract minimum element. The idea is to extract minimum element which takes O(n+n) = O(n) time, IF we repeat this for n^2 element it will take O (n ^3)time.

Finding overflows during arithmetic operations

We know that data in computers have limited size. For example, integer may be limited to 4 bytes. So, while writing programs sometimes we might need to check for overflows to make sure that the resulting value fits the size. But finding overflows are easy.

Finding overflow during addition

Lets say you are adding number a and b. Lets say maximum value that the types of a and b can hold be MAX. Then we can check for overflow using following condition:

if ( (MAX - a) < b then the result overflows else not.

Finding overflow during multiplication

One example of its use is while computing factorial. Lets say you want to compute n!. But you also want to make sure that appropriate error is thrown when it overflows. This is also quite simple. Lets say again that the maximum value a data type can hold be MAX and you are multiplying a and b. The result overflows if MAX/a < b.

Finding median or Kth element in Binary Search Tree (BST)

Finding kth element in BST is quite simple. We know that all the elements in left subtree is smaller than all the elements in right subtree. If we count the number of elements in left and right subtree then we know in which subtree the required element exists and then we move to this subtree and repeat the same steps again. For example starting from root we are looking for 11th element. Lets say left subtree has 7 elements and right subtree has 6 elements.Then as the number 11 is greater than 7 we know that the 11th median exists in the right subtree. Now in the right subtree we look for (11 - 7 -1 = 3)rd element (Why?? because we have discarded left subtree). We proceed similarly in the new subtree until we get the kth median as the root.

The example described above can very well be described in recursive form. The code below is a complete program in recursive form.

  
 //find kth element in a BST recursively
Node * find_kth_element(Node *tree, int &k) {

 if(tree == 0)
  return 0;

 int count = 0;

 //count the nodes in left subtree
 count_nodes(tree->left_, count);

 //check if the root is median
 if( k == count + 1)
  return tree;

 //check if median falls on left subtree
 else if (count >= k) {

  return find_kth_element(tree->left_,k);
 }
 //the median falls on right subtree
 else {
  k = k - (count + 1);
  return find_kth_element(tree->right_, k);
 }
}

Iterative Solution

We know that recursive solutions are not that efficient and it's always good to avoid it if it's possible. The problem however is equally simple in iterative form as well. The code below translates recursive form into iterative form.

  
 

//find kth element iteratively
Node * find_kth_element_iterative(Node *tree, int &k) {
 if(tree == 0)
  return 0;

 Node *node = tree;
 int count = 0;
 int pos = k;


 while(node != 0) {
  count = 0;

  //count nodes on the left subtree
  count_nodes(node->left_, count);

  //check if root is the median
  if( pos == count + 1)
   return node;

  //check if median falls on left subtree
  else if (count >= pos)
   node = node->left_;

  //median falls on right subtree
  else {
   pos -= (count + 1);
   node = node->right_;
  }

 }
 return 0;
}

Complexity

What's the complexity of above algorithms? While finding median You are moving along a path in the tree, so in the worst case it can be height of the tree (h) and also you are counting the number of nodes in left subtree at each step. Which requires O(n) time in the worst case. Thus the overall algorithm is O(nh).

Is there a way to improve it? Yes, of course ( at least one technique I know of). If you need to keep on computing the kth median on a single tree many times, then you can construct a tree with a count of elements in its subtree. If you do this the counting of number of nodes in left subtree takes O(1) time. Effectively the algorithm will reduce to O(h) algorithm. In case tree is balanced this is just O(log n). Not bad :).

Counting the number of ways BST can be formed

The problem is posed as follows: Given numbers from 1 to n, In how many ways can you form a BST. For example if number given is 1 to 3. How many ways can we proceed? We can break this down to problem where we count number of possibilities when root is 1,2 and 3 respectively. And then we sum all those values to give total number of possibilities. Now when 1 is root, we can proceed to count possibilities when 2 is the root for the right subtree of 1 and when 3 is the root of the right subtree of 1. This gives us the fair idea that we can proceed recursively and count the possibilities. For left and right subtrees we multiply each other to give total number of possibilities. This translates into simple code given below:

  
//compute how many BST can be formed for given number of inorder, no duplicates
int comb_count(int begin, int end) {

 if(begin >= end)
  return 1;
 int count = 0;
 for(int i = begin ; i <= end; i++) {
  //take this as root and find how the 
//nodes can be arranged on the left or right
  count+= comb_count(begin, i - 1) *  comb_count(i + 1, end);
 }
 return count;
} 

Inserting a value in sorted circular linked list

Inserting an item in sorted circular linked list is tricky. If the elements in the list are unique then there are 3 cases to consider:

Case I: The new element to be inserted falls between 2 elements in the list.

Case II: The new element is larger than all the elements in the list.

Case III: The new element is smaller than all the elements in the list.

For cases where list is empty or list has only 1 element, it doesn't matter where you insert the new node.

In the solution below I assume ascendingly sorted list and no duplicates are considered. It would be easy to extend the program for that but it would grow a bit complex. So I have only presented code for the simple case. I might post another version with all cases handled later.

//linked list node
struct LNode {
LNode(int val_):val(val_),next(0){}
int val;
LNode *next;
};
LNode* insert(LNode *list, int val) {

//construct new node for this value
LNode *newNode = new LNode(val);

//check if list has no item
if(list == 0){
newNode->next = newNode;
return newNode;
}
//check if list contains only one item
else if (list->next == list) {
list->next = newNode;
newNode->next = list;
return newNode;
}
LNode  *temp, *node = list;
node = node->next;
while(list != node) {

//Case I: val falls between 2 values in the list
if(val > node->val && val <>next->val){
break;

}
//case II: val is greater than all the values in the list
else if(val > node->val && node->next->val <>val) {
break;

}
//case III: val is smaller than all the values in the list
else if( val <>next->val && node->next->val <>val) {
break;
}
node = node->next;
}

temp = node->next;
node->next = newNode;
newNode->next = temp;

return newNode;
}

Handling duplicate values

Capability to handle duplicate values can easily be added to the above code by replacing greater than and less than in value comparisons by greater than equal to and less than equal to. The new conditions will be:

  //Case I: val falls between 2 values in the list
if(val >= node->val && val <>next->val){
break;

}
//case II: val is greater than all the values in the list
else if(val >= node->val && node->next->val <>val) {
break;

}
//case III: val is smaller than all the values in the list
else if( val <= node->next->val && node->next->val <>val) {
break;
}

When how the list is sorted is not known

When how the list is sorted is not known you can add similar conditions for descending sorted list. But first you need to determine how the list is sorted. The sorting order can be determined by traversing elements until we find 2 increasing(ascending) or decreasing (descending) numbers in sequence. Why two? Because with one you never know if it is at the end of the list where the element order reverses. But when list has 2 elements, you never know how the list is sorted. Consider for example list 1, 2 as circular (1->2->1), then you have no way of telling if it is sorted in ascending order or descending order. Same is the case when list has more elements but each of them have same value except one (e.g 1,1,1,1,1,1,1,3).

Serializing and De-serializing Binary Tree

Serializing a binary tree is easy. Only thing we need to do is to serialize null pointers as well. So a preorder traversal of the tree with a special symbol indicating null left or right child of the tree will be sufficient to reconstruct tree. In the example code below we indicate null by ~0 (which is the number with all 1 binary digit. For example if you have a tree like A->B->C (where B is a right child of A and C is a right child of B), the serialization will produce A NULL B NULL C NULL NULL. During reconstruction you start from the first element and proceed creating left child until you hit NULL. After we hit NULL, we drop it and look for nother element. If another element is not NULL we create right child. The process is straight forward and can easily be understood from the code.

  

std::vector<int> queue;

void serialize_bst(Node * node) {

 if(node == 0 )
 {
  queue.push_back(~0);
  return;
 }

 queue.push_back(node->value_);
 serialize_bst(node->left_);
 serialize_bst(node->right_);
}
 

  
Node* deserialize_bst(std::vector<int> &queue) {
 if(queue.empty())
  return 0;
 if(queue[0] == ~0) {
  queue.erase(queue.begin());
  return 0;
 }

 //creates node with null left and right child
 //and given value
 Node *node = new Node(0,0,queue[0]);
 queue.erase(queue.begin());
 node->left_ = deserialize_bst(queue);
 node->right_ = deserialize_bst(queue);
 return node;
}
 

Conversion from Roman Number to Decimal

Conversion from roman number to decimal is quite straightforward if you look at the pattern of the number. You can start from the rightmost letter of roman number and keep on adding the decimal number that it corresponds to. But when the letter encountered while moving left is smaller than the maximum value of the letter encountered previously we need to subtract it. For example take XLV, rightmost letter is V which is 5 , the second one is L which is 50 and the third one is X which is 10 (this is less than the max value encountered, 50, so we need to subtract it. Thus the total is 5+50-10 = 45.

  
/*I - 1
V - 5
X -10
L - 50
C - 100
D -500*/

int get_val(char roman) {

 switch (roman) {
  case 'I':
   return 1;
  case 'V':
   return 5;
  case 'X':
   return 10;
  case 'L':
   return 50;
  case 'C':
   return 100;
  case 'D':
   return 500;
  case 'M':
   return 1000;
  default:
   return 0;
 }
 return 0;
}

int roman_to_int (const std::string &roman) {
 int max = 0;
 int num = 0;
 int len = roman.length() - 1;
 while(len >= 0) {
  int val = get_val(roman[len]);

  if(val < max)
   num -= val;
  else {
   num += val;
   max = val;
  }
  len--;
 }
 return num;
}