Interview Programming Challenge: Print me a tree

Posted on by

Last Thursday I had a interview with a software company. During the interview that asked me write out a program which I was unable to complete within 10 minutes time. But I think am OK because their goal seemed to be to determine how I approached the problem rather than if I could produce a working program.

Anyhow, I decided to finished the program during my spare time in case if it every comes up again. And here it is.

Question: (Not exact wording)
Design a program in any language that will print a tree using only UNICODE or/and ANSI characters. The program should accept user input an integer value to set the base of the tree.
Example:

// base length is 7
   *
  ***
 *****
*******
   *

My Program
I decided to use Groovy and Test Driven Development to solve this problem. After a little bit of thinking I managed to come up with the following two files that create a working program.
Tree.groovy – Program that prints the tree
TreeTest.groovy – Test cases for Tree.groovy

TreeTest.groovy (Test Cases)

/**
* @author Larry Battle
* @date 1/3/2011
* @purpose Provide test cases for the Tree class.
*/
import Tree;
 
class TreeTest extends GroovyTestCase{
    private Tree tree = new Tree();
    private testValues = [
        [baseLength:-1, level:-1, length:0],
        [baseLength:1, level:0, length:1],
	[baseLength:1, level:0, length:1],
	[baseLength:1, level:5, length:0],
        [baseLength:1, level:9, length:0],
        [baseLength:2, level:0, length:1],
        [baseLength:2, level:2, length:1],
	[baseLength:2, level:5, length:0],
	[baseLength:6, level:0, length:1],
	[baseLength:6, level:2, length:5],
        [baseLength:6, level:3, length:6],
        [baseLength:6, level:4, length:1],
        [baseLength:6, level:5, length:0],
        [baseLength:7, level:0, length:1],
        [baseLength:7, level:2, length:5],
        [baseLength:7, level:3, length:7],
        [baseLength:7, level:4, length:1],
        [baseLength:7, level:5, length:0]
    ];
    void testHeight(){
        def vals = [ 0:0, 1:1, 2:3, 3:3, 4:4, 7:5, 40:22 ];
        def msg;
        vals.each{
            msg = "baseLength of {$it.key} should have height of {$it.value}";
            assert tree.getHeight( it.key as short ) == it.value : msg;
        }
    }
    void testTreeBranchLength(){
        def msg; 
        def length;
        testValues.each{ obj ->
            length = tree.getBranchLength( obj.level, obj.baseLength );
            msg = "BaseLength $obj.baseLength at Level $obj.level should be $obj.length, not $length";
            assert length == obj.length : msg;
        }
    }
// Other test cases not included.
}

Tree.groovy

/**
* @author Larry Battle
* @date 1/3/2011
* @purpose Tree Interview Question: Display a tree in ansi format with a specified integer base length.
*/
// function documentation excluded.
class Tree{
    short getHeight( baseLength ){
        short height = 0;
        if( baseLength > 0 ){
            height = 1;
            if( baseLength > 1 ){
                height += Math.floor( baseLength / 2 ) + 1;
            }
        }
        return height;
    }
    short getBranchLength( levelNum, baseLength ){
        short length = 0;
        short height = getHeight( baseLength );
        if( levelNum > -1 && height > levelNum ){
            if( height - levelNum == 2 ){
                length = baseLength;
            }else{
                if( height - levelNum == 1 ){
                    length = 1;
                }else{
                    length = 2 * levelNum + 1;
                }
            }
        }
        return length;
    }
    short getWhiteSpaceOnLeftNum( levelNum, baseLength ){
        short i = 0;
        short height = getHeight( baseLength );
        if( levelNum > -1 && height > levelNum ){
            if( height - levelNum == 2 ){
                i = 0;
            }else{
                if( height - levelNum == 1){
                    levelNum = 0;
                }
                i = Math.floor( baseLength / 2 ) - levelNum;
            }
        }
        return i;
    }
    String getTreeBranch( levelNum, baseLength ){
        char x = '*';
        short xNum = getBranchLength( levelNum, baseLength );
        short spaceNum = getWhiteSpaceOnLeftNum( levelNum, baseLength );
        String str = "";
        spaceNum.times{
            str += ' ';
        }
        xNum.times{
            str += x;
        }
        return str;
    }
    String[] getTreeAsStrArr( short baseLength ){
        short height = getHeight( baseLength );
        return (0..height-1).collect{
            return getTreeBranch( it, baseLength );
        }
    }
    void printTree( short baseLength ){    
        if( 1 > baseLength || baseLength > 49 ){
            throw new Error( "BaseLength must be bigger than 1 and less than 50." );
        }
        String[] strArr = getTreeAsStrArr( baseLength );
        println strArr.join( '\n' );
        println "------Base length = $baseLength -------";
    }
    static void main( String[] args ){
        Tree a = new Tree();
	def vals = [1,2,6,7,49];
	if( args.length ){
		vals = [];
		args.each{
			vals.push( Integer.parseInt( it ) );
		}
	}
	vals.each{
		a.printTree( it as short );
	}
    }
}

Output ( Run Tree.groovy 2 7 12 > output.txt )

 *
**
 *
------Base length = 2 -------
   *
  ***
 *****
*******
   *
------Base length = 7 -------
      *
     ***
    *****
   *******
  *********
 ***********
************
      *
------Base length = 12 -------
(Page view Count: 38)