number system with only 3 and 4

Reference :-
http://www.geeksforgeeks.org/zoho-interview-set-2-campus/

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
http://ideone.com/nkuJkT


import java.util.ArrayList;
public class CombinationOf3And4 {

/*
 * http://www.geeksforgeeks.org/zoho-interview-set-2-campus/
 * 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) {
printCombinations(20);
}
public static void printCombinations(int n){
ArrayList<String> numbers = new ArrayList<String> ();
numbers.add("3");
numbers.add("4");
int currentNumber = 0;
while(numbers.size()<n){
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 
threePrefixed.add("3"+numbers.get(i));
fourPrefixed.add("4"+numbers.get(i));
currentNumber++;
}

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

}
}

Subset sum problem.

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

Reference 

http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/

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

http://ideone.com/uUxNgb

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");

 else

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

}

 

}

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

Reference
http://www.geeksforgeeks.org/find-water-in-a-glass/

Problem statement

There are some glasses with equal capacity as 1 liter. The glasses are kept as follows:

              1
           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 liter
2nd – 1/2 liter
3rd – 1/2 liter

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 http://ideone.com/2ecUuD

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");

if(currentRow==requiredRown){

if(currentCol==requiredColnum) 

return min(input,1);

else

return 0;

}else{

// Pour water in right side and in left side equally

float waterForNextLevel = (input-1)/2;

if(waterForNextLevel>0){

float waterFromLeftBranch= findWaterInGlassInternal(waterForNextLevel,currentRow+1,currentCol,requiredRown,requiredColnum) ; 

float waterFromRightBranch = findWaterInGlassInternal(waterForNextLevel,currentRow+1,currentCol+1,requiredRown,requiredColnum);

return min(waterFromLeftBranch+waterFromRightBranch,1);

}else{

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;

}

}

Output

findWaterInGlass(10,1,1)=1.0
findWaterInGlass(10,2,1)=1.0
findWaterInGlass(10,2,2)=1.0
findWaterInGlass(10,3,1)=1.0
findWaterInGlass(10,3,2)=1.0
findWaterInGlass(10,3,3)=1.0
findWaterInGlass(10,4,1)=0.375
findWaterInGlass(10,4,2)=1.0
findWaterInGlass(10,4,3)=1.0
findWaterInGlass(10,4,4)=0.375
findWaterInGlass(10,5,1)=0.0
findWaterInGlass(10,5,2)=0.0
findWaterInGlass(10,5,3)=0.0
findWaterInGlass(10,5,4)=0.0
findWaterInGlass(10,5,5)=0.0

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

Reference
http://www.geeksforgeeks.org/find-the-maximum-sum-path-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++){

    if(path.charAt(i)=='L'){

    System.out.println(currNode.left.key+" ");

    currNode=currNode.left;

    }else{

    System.out.println(currNode.right.key+" ");

    currNode=currNode.right;

    }

   }

 

   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)

       return;

 

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

        tempObj.path=curr_path;

       }

   }

 

   // 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();

   tempObj.max_value=0;

   tempObj.path="";

 

   // 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 

10 
7

Lexicographical order of alien language

Reference Problem :-
http://www.geeksforgeeks.org/flipkart-interview-set-6/

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
Eg:

abc

acd

bcc

bed

bdc

dab

The order of letters for the given example would be

a->b->c->e->d

My approach 

Answer :-

Process is divided in two parts.

PART 1 ) CREATE SEQUENCE

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,

abc

acd

bcc

bed

bdc

dab

After visiting all strings, sequence is

a->b->d

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

c->e->d

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

PART 2) RECONCILE SEQUENCE

After part 1, we have three sequences

a->b->d

b ->c

c->e->d

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 http://ideone.com/W7NMpN

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>();

dictionary.add("abc");

dictionary.add("acd");

dictionary.add("bcc");

dictionary.add("bed");

dictionary.add("bdc");

dictionary.add("dab");

ArrayList<CharNode> treeList = new ArrayList<CharNode>() ;

buildDictionaryTree(dictionary,treeList);

System.out.println("Printing trees");

for(CharNode lst:treeList){

System.out.println(lst);

}

reconcileTrees(treeList);

System.out.println("Final tree is ");

System.out.println(treeList.get(0));

System.out.println("done");

}

public static void reconcileTrees(ArrayList<CharNode> treeList){

while(treeList.size()>1){

for(int i =0;i<treeList.size();i++){

for(int j =i+1;j<treeList.size();j++){

mergeOrModifyTwoTrees(treeList,i,j,true);

// if list is not modified call reverse way

if(i<treeList.size() && j<treeList.size()){

mergeOrModifyTwoTrees(treeList,j,i,true);

}

}

}

}

}

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(currOfT2!=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;

}else{

// no match found for current node

break;

}

}

if(lastMatchingNodeOfT1 == null && lastMatchingNodeOfT2 == null){

return;

}

if(currOfT2==null){

// t2 is completely present in t1 directly or indirectly

// So remove from arrayList

treeList.remove(t2);

}else{

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

treeList.remove(t2);

}else{

// 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

// lastMatchingNodeOfT1.next = 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.remove(t2);

treeList.add(secodnd, temp);   // d->m added as separate string

}else{

// t2 is completely consumed

treeList.remove(t2);

}

}

}

}

// do the same for reverse

}

public static void buildDictionaryTree(ArrayList<String> dictionary, ArrayList<CharNode> treeList){

//System.out.println("Input strings are");

//System.out.println(dictionary);

if(dictionary.size()>1){

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

if(strlst==null){

//first time this character was visited

strlst = new ArrayList<String>();

charStringMap.put(firstChar,strlst);

}

// If this string is more than one character add substring to this list

if(str.length()>1){

strlst.add(str.substring(1));

}

if(currentNode==null){

// First time creating tree in this call. So create node and also add it in input tree list 

currentNode = new CharNode(firstChar);

treeList.add(currentNode);

}else{

if(currentNode.value==firstChar){

// We are still processing strings starting with same character so no need to add in tree

}else{

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){

buildDictionaryTree(charStringMap.get(ch),treeList);

}

}else{

//System.out.println("Only one string. No use");

}

}

}

class CharNode{

char value;

CharNode nextNode;

public CharNode(char value) {

this.value=value;

}

@Override

public String toString() {

if(nextNode!=null){

return value+"->"+nextNode.toString();

}else{

return value+"";

}

}

}