Sunday, September 28, 2014

number system with only 3 and 4

Reference :-

Problem statement:-
Form a number system with only 3 and 4. Find the nth number of the number system.
Eg.) The numbers are: 3, 4, 33, 34, 43, 44, 333, 334, 343, 344, 433, 434, 443, 444, 3333, 3334, 3343, 3344, 3433, 3434, 3443, 3444 ….

My approach.
3 & 4 are starting numbers.
Prefixing them with 3 gives next numbers viz. 33, 34
Similarly prefixing then gives next numbers viz. 43,44.

So now list is 3,4,33,34,43,44.

We have already considered 3 & 4. If we repeat the process for remaining numbers  i.e. 33,34,43,44.
viz. Prefixing them with 3 gives next numbers viz. 333, 334, 343, 344
viz. Prefixing them with 4 gives next numbers viz. 433, 434, 443, 444

So now list is 3,4,33,34,43,44,333, 334, 343, 344,433, 434, 443, 444

Code :-
Also shared at

import java.util.ArrayList;
public class CombinationOf3And4 {

 * Form a number system with only 3 and 4. Find the nth number of the number system.
 * e.g. The numbers are: 3, 4, 33, 34, 43, 44, 333, 334, 343, 344, 433, 434, 443, 444, 3333, 3334, 3343, 3344, 3433, 3434, 3443, 3444 ….
public static void main(String[] args) {
public static void printCombinations(int n){
ArrayList<String> numbers = new ArrayList<String> ();
int currentNumber = 0;
ArrayList<String> threePrefixed = new ArrayList<String>();
ArrayList<String> fourPrefixed = new ArrayList<String>();

for(int i=currentNumber;i<numbers.size();i++){
// Retrieve all numbers.
// For every number create new number with prefix "3"  & with prefix "4".
// then push all 3-prefixed-number into array and then 4-prefixed-number 

for(String s:threePrefixed){
for(String s:fourPrefixed){
System.out.println("Printing result");
for(String s:numbers){
System.out.print(" "+s);


Saturday, September 13, 2014

Subset sum problem.

Subset sum problem. determine if there is a subset of the given set with sum equal to given sum.


Problem statement :-
Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.
Examples: set[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output: True //There is a subset (4, 5) with sum 9.

My approach
I do not propose different approach here but helping to understand it. 
Code for approach 2 of Dynamic programming given there is too compact to understand easily. 
So I expanded the steps and added few comments so that it is easier to grasp. 
Once you have understood expanded code correctly try to combining/shortening the commands; you will reach original code.

Java code.
Also shared at

public class SubsetSumProblem {

public static void main(String[] args) {
int set[] = {12, 34, 4, 3, 5, 2};
 int sum = 9;
 int n = set.length;
 if (isSubsetSum(set, n, sum) == true)
    System.out.println("Found a subset with given sum");
 System.out.println("No subset with given sum");

// Returns true if there is a subset of set[] with sun equal to given sum
public static boolean isSubsetSum(int set[], int n, int sum)
   // The value of subset[i][j] will be true if there is a subset of set[0..j-1]
   //  with sum equal to i
boolean subset[][] = new boolean[sum+1][n+1];
   // If sum is 0, then answer is true
   for (int i = 0; i <= n; i++)
     subset[0][i] = true;
   // If sum is not 0 and set is empty, then answer is false
   // This is not needed in Java as default value of boolean is false. 
//    for (int i = 1; i <= sum; i++)
//      subset[i][0] = false;

    // Fill the subset table in bottom up manner
    for (int i = 1; i <= sum; i++)
      for (int j = 1; j <= n; j++)
      if(subset[i][j-1] == true){
    // it is possible to generate sum "i" from smaller subset itself. 
    // So obviously it can be generated by bigger one. So no need to think more
    subset[i][j] = true;   
      }else if (i == set[j-1]) {
      subset[i][j] = true;
      }else if (i >= set[j-1]) {
          //  sum "i" is bigger than set[j-1]. Lets say  set[j-1] + x = i
        // So x = i - set[j-1]
        // Now we need to refer currently populated array to check if "x" can be achieved by first j-1 elements.
          int x = i - set[j-1];
          subset[i][j] = subset[x][j-1];
    return subset[sum][n];

Sunday, September 7, 2014

Program to find amount of water in a given glass in pyramid


Problem statement
There are some glasses with equal capacity as 1 liter. The glasses are kept as follows:
           2    3
        4    5    6
     7    8    9   10
You can put water to only top glass. If you put more than 1 litre water to 1st glass, water overflows and fills equally in both 2nd and 3rd glasses. Glass 5 will get water from both 2nd glass and 3rd glass and so on.
If you have X 
liter of water and you put that water in top glass, how much water will be contained by jth glass in ith row?
Example. If you will put 2 liter on top.
1st – 1 
2nd – 1/2 
3rd – 1/2 

My approach
The approach given in the article if of nested-loop.
I have thought of a recursive approach. This approach is easy to understand and memory efficient.

Consider that rows are numbered starting from 1 and columns are numbered from 1.
So triangle will look like.

            1 -> Row 1
        1 2 -> Row 2
    1      2     3 -> Row 3
1 2 3 4 -> Row 4

Input is amount poured at topmost glass and required rownumber and column number.

For a given glass if water is poured on it; then it can store only 1 unit; and and remaining water is divided into half and passed to right child and left child.
So amount passed to each child  = (amount at this glass -1) /2
Its children will have row number as (current row number +1)
Its left child will have column number same as current cup
Its right child will have column number as (current column number +1)

So start with topmost glass as current glass.
If required row number matches 
       then if required column matches amount is minimum(1,actual amonut)
       otherwise it is other cup of same row. So no need to go further down
else i.e. row does not match then 
       call the same function to get the amount of water in required cup by pouring water in left child 
       call the same function to get the amount of water in required cup by pouring water in right child 
       sum two amounts to get total amount from both path.
       value in the cup min(1, above sum) 

Java implementation
Also shared at

class PyramidOfGlassAndWater {

public static float findWaterInGlass(float inputAtTop, int rownum,int colnum){
return findWaterInGlassInternal(inputAtTop,1,1,rownum,colnum);

public static float findWaterInGlassInternal(float input,int currentRow,int currentCol, int requiredRown,int requiredColnum){
if(requiredColnum>requiredRown) throw new RuntimeException("requiredColnum>requiredRown");
return min(input,1);
return 0;
// Pour water in right side and in left side equally
float waterForNextLevel = (input-1)/2;
float waterFromLeftBranch= findWaterInGlassInternal(waterForNextLevel,currentRow+1,currentCol,requiredRown,requiredColnum) ; 
float waterFromRightBranch = findWaterInGlassInternal(waterForNextLevel,currentRow+1,currentCol+1,requiredRown,requiredColnum);
return min(waterFromLeftBranch+waterFromRightBranch,1);
return 0;
public static void main(String[] args) {
int totalRounum =5;
int waterQuantity =10;
for(int i=1;i<=totalRounum;i++){
for(int j=1;j<=i;j++){
System.out.println("findWaterInGlass("+waterQuantity+","+i+","+j+")="+ findWaterInGlass(waterQuantity,i,j));
public static float  min(float a, float b){
return a<b?a:b;


Improving code of "maximum sum leaf in a Binary Tree"


My approach
The approach to find the leaf node which has maximum sum is correct. But after we get the leaf node; we traverse whole tree again to print the full path. 

if (root == target_leaf || printPath(root->left, target_leaf) ||
            printPath(root->right, target_leaf) )
        printf("%d ", root->data);
        return true;

In worst case; if right-most leaf is max-sum-leaf then we traverse tree twice once to find target node and once to print path. 

We can improve this by remembering path to target node while finding node itself.

If we can describe path of a node from root node in terms of "L" and "R" i.e. "L" indicated go to left child of current node and "R" indicate go to right child of current node as.
Then we can have a path from root to leaf as LRLRRRL etc.
Once we get the target node we can just check its path string and traverse to that one node directly.

There should be a variable to save path to target node like we have to store max sum. 
While finding the target node; we should send current path along with max sum. And as an whenever we update  we update max_sum we should update path variable as well.

Then print path will be just check "L" and "R" and go to appropriate node. 

Java implementation :-
class MaximumSumPath {
// A utility function that prints all nodes on the path from root to target_leaf
static boolean  printPath (TreeNode root, String path)
   // base case
   if (root == null)
       return false;
   System.out.println(root.key+" ");
   TreeNode currNode= root;
   for (int i = 0; i<path.length();i++){
    System.out.println(currNode.left.key+" ");
    System.out.println(currNode.right.key+" ");
   return false;
// This function Sets the target_leaf_ref to refer the leaf node of the maximum 
// path sum.  Also, returns the max_sum using max_sum_ref
static void  getTargetLeaf (TreeNode node,  int curr_sum, String curr_path, Temp tempObj )
   if (node == null)
   // Update current sum to hold sum of nodes on path from root to this node
   curr_sum = curr_sum + node.key;
   // If this is a leaf node and path to this node has maximum sum so far,
   // then make this node target_leaf
   if (node.left == null && node.right == null)
       if (curr_sum > tempObj.max_value)
        tempObj.max_value = curr_sum;
   // If this is not a leaf node, then recur down to find the target_leaf
   getTargetLeaf (node.left, curr_sum,curr_path+'L', tempObj);
   getTargetLeaf (node.right, curr_sum,curr_path+'R', tempObj);
// Returns the maximum sum and prints the nodes on max sum path
static int  maxSumPath (TreeNode node)
   // base case
   if (node == null)
       return 0;
   Temp tempObj= new Temp();
   // find the target leaf and maximum sum
   getTargetLeaf (node, 0,"", tempObj);
   // print the path from root to the target leaf
   printPath (node,tempObj.path);
   return tempObj.max_value;  // return maximum sum
public static void main(String args[])
   TreeNode  root = null;

   root = new TreeNode (10);
   root.left = new TreeNode (-2);
   root.right = new TreeNode (7);
   root.left.left = new TreeNode (8);
   root.left.right = new TreeNode (-4);
   System.out.println ("Following are the nodes on the maximum sum path \n");
   int sum = maxSumPath(root);
   System.out.println("\nSum of the nodes is %d "+sum);

class Temp{
int max_value;
String path;

//Class for a tree node
class TreeNode {
public TreeNode(int key) { this.key = key; left = null; right = null; }
 public int key;
 public TreeNode left;
 public TreeNode right;

Output :-
Following are the nodes on the maximum sum path 


Lexicographical order of alien language

Reference Problem :-

Problem statement
Given a Alien language, we have the dictionary of that language , but we have only very few words, but they are all arranged in the lexicographical order. We need to first find whether we will be able to get a alphabetical order or not, if yes explain approach
The order of letters for the given example would be

My approach 
Answer :-
Process is divided in two parts.

Visit every string and create a sequence of their initial character.
Also we will populate a map (character and list of strings). Those strings which started with this character (key of map) will be considered. We will enlist substring after initial character.
So for strings,

After visiting all strings, sequence is

So Map will be
a    [bc,cd]
b    [cc,ed,dc]
d    [ab]

Now for each we will call same procedure

1) So for map “a    [bc,cd]” list is   [bc,cd]
Sequence will be
b ->c
And map will be
b     [c]
c      [d]

As each list has only one string; there is no use of calling method those lists

2) ) So for map “b    [cc,ed,dc]” list is   [cc,ed,dc]
Sequence will be
And map wil be
c              [c]
e             [d]
d             [c]

As each list has only one string; there is no use of calling method for those list

After part 1, we have three sequences
b ->c

Now we need to reconcile these sequences.
Till we have more than one sequence we need to try all combination of sequences

Reconcile two sequences
Check if t2 is completely present in t1 (directly or indirectly) 
Example 1).  t1 = a->b->c               t2 = b->c
So t2 is present. Remove t2 from list

Example 2) If t1 = a->b->d->x->c      t2 = b->c
Root of t2 i.e. “b” is present is present in t1.
Next of root of t2 i.e. “c”  is present downward in sequence.
So it sequence is b->c indirectly present in t1. So remove t2 from list

Check if t2 is partially present in t1.
“Leaf node of t1” case
t1 = a->b->c               t2 = b->c->m->n
b->c part is already present.
“c” is leaf node so attach remaining part to t1
t1 == = a->b->c->m->n        
So remove t2 from list.

“Non leaf node of t1” case
t1 = a->b->d ->c->p              t2 = b->c->m->n
b->c part is already present.
“c” is non leaf node of t1.
So remove redundant part of t2. t2 == c->m->n
t1 remain as it is

As sequence are modified by one of the above condition, try again reconciling till there remains only one sequence.

Java implementation
It is also shared at

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Set;

class Dictionary {

public static void main(String[] args) {
ArrayList<String> dictionary = new ArrayList<String>();
ArrayList<CharNode> treeList = new ArrayList<CharNode>() ;
System.out.println("Printing trees");
for(CharNode lst:treeList){
System.out.println("Final tree is ");
public static void reconcileTrees(ArrayList<CharNode> treeList){
for(int i =0;i<treeList.size();i++){
for(int j =i+1;j<treeList.size();j++){
// if list is not modified call reverse way
if(i<treeList.size() && j<treeList.size()){
public static void mergeOrModifyTwoTrees(ArrayList<CharNode> treeList , int first , int secodnd,boolean firstCall){
CharNode t1 = treeList.get(first);
CharNode t2 = treeList.get(secodnd);
// Check if root of t2 is found in tree of t1
CharNode currOfT1 = t1;
CharNode currOfT2 = t2;
CharNode lastMatchingNodeOfT1 =null,lastMatchingNodeOfT2=null;
while(currOfT1 != null && currOfT1.value !=currOfT2.value ){
currOfT1 = currOfT1.nextNode;
if(currOfT1 != null){   
// loop ended when currOfT1 so match for t2 found in t1 
// So go for next of t2
lastMatchingNodeOfT1 = currOfT1;
lastMatchingNodeOfT2 = currOfT2;
currOfT2 = currOfT2.nextNode;
// no match found for current node
if(lastMatchingNodeOfT1 == null && lastMatchingNodeOfT2 == null){
// t2 is completely present in t1 directly or indirectly
// So remove from arrayList
// There is part of t2 that is not present in t1
if(lastMatchingNodeOfT1 != null && lastMatchingNodeOfT1.nextNode ==null){
// lastMatchingNodeOfT1 was a leaf node then you can append remaining of t2 there
lastMatchingNodeOfT1.nextNode = currOfT2;
// lastMatchingNodeOfT1 is not present or NOT leaf.
// Do reverse way. Check if next of lastMatchingNodeOfT1 is present t2
// e.g. t1==a->b->d   t2 == b->c->e->d
// lastMatchingNodeOfT1 == b->d
// lastMatchingNodeOfT2 == b->c->e->d
// So check if lastMatchingNodeOfT1.nextNode i.e. "d" is present in  lastMatchingNodeOfT2
CharNode temp = lastMatchingNodeOfT2.nextNode;
CharNode nodeBeforeTemp = lastMatchingNodeOfT2;
while(temp !=null && temp.value != lastMatchingNodeOfT1.nextNode.value){
nodeBeforeTemp = temp;
temp = temp.nextNode;
// t1== a->b->d->n  t2 == b->c->e->d->m
// them lastMatchingNodeOfT1=lastMatchingNodeOfT2= b
// = d->n
// temp = d->m
// nodeBeforeTemp = e->d->m
if(temp !=null ){
nodeBeforeTemp.nextNode = lastMatchingNodeOfT1.nextNode;  //   e->d->n
lastMatchingNodeOfT1.nextNode = lastMatchingNodeOfT2.nextNode;  // a->b->c
// together it became a->b->c->e->d->n
if(temp.nextNode !=null){
treeList.add(secodnd, temp);   // d->m added as separate string
// t2 is completely consumed

// do the same for reverse

public static void buildDictionaryTree(ArrayList<String> dictionary, ArrayList<CharNode> treeList){
//System.out.println("Input strings are");
CharNode currentNode = null;
HashMap<Character, ArrayList<String>> charStringMap = new HashMap<Character, ArrayList<String>>();
for(String str : dictionary){
char firstChar = str.charAt(0);
ArrayList<String> strlst = charStringMap.get(firstChar);
//first time this character was visited
strlst = new ArrayList<String>();
// If this string is more than one character add substring to this list
// First time creating tree in this call. So create node and also add it in input tree list 
currentNode = new CharNode(firstChar);
// We are still processing strings starting with same character so no need to add in tree
currentNode.nextNode=new CharNode(firstChar);
currentNode= currentNode.nextNode;
// All first character done. Now call same process for substrings one by one
// Each call will create a separate tree
Set<Character> charCovered =  charStringMap.keySet();
for(char ch:charCovered){
//System.out.println("Only one string. No use");

class CharNode{
char value;
CharNode nextNode;
public CharNode(char value) {
public String toString() {
return value+"->"+nextNode.toString();
return value+"";