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