Interview Programming Challenge: Print me a tree

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

Larry Battle

I love to program, and discover new tech. Check out my stackoverflow and github accounts.

More Posts - Website

Follow Me:
TwitterLinkedInYouTube

Code of the Day: Groovy Print all Methods of an object

Groovy Code

/**
* @function printAllMethods
* @purpose Prints an objects class name and then list the associated class functions.
*/
// Filename: printAllMethodsExample.groovy
void printAllMethods( obj ){
    if( !obj ){
		println( "Object is null\r\n" );
		return;
    }
	if( !obj.metaClass && obj.getClass() ){
        printAllMethods( obj.getClass() );
		return;
    }
	def str = "class ${obj.getClass().name} functions:\r\n";
	obj.metaClass.methods.name.unique().each{ 
		str += it+"(); "; 
	}
	println "${str}\r\n";
}

Example Code

// Filename: printAllMethodsExample.groovy
void printAllMethods( obj ){
    if( !obj ){
		println( "Object is null\r\n" );
		return;
    }
	if( !obj.metaClass && obj.getClass() ){
        printAllMethods( obj.getClass() );
		return;
    }
	def str = "class ${obj.getClass().name} functions:\r\n";
	obj.metaClass.methods.name.unique().each{ 
		str += it+"(); "; 
	}
	println "${str}\r\n";
}
printAllMethods( null );
printAllMethods( 1 );
printAllMethods( "string" );
printAllMethods( [1:1] );

Output

Object is null
 
class java.lang.Integer functions:
equals(); getClass(); hashCode(); notify(); notifyAll(); toString(); wait(); byteValue(); doubleValue(); floatValue(); intValue(); longValue(); shortValue(); bitCount(); compare(); compareTo(); decode(); getInteger(); highestOneBit(); lowestOneBit(); numberOfLeadingZeros(); numberOfTrailingZeros(); parseInt(); reverse(); reverseBytes(); rotateLeft(); rotateRight(); signum(); toBinaryString(); toHexString(); toOctalString(); valueOf(); 
 
class java.lang.String functions:
equals(); getClass(); hashCode(); notify(); notifyAll(); toString(); wait(); charAt(); codePointAt(); codePointBefore(); codePointCount(); compareTo(); compareToIgnoreCase(); concat(); contains(); contentEquals(); copyValueOf(); endsWith(); equalsIgnoreCase(); format(); getBytes(); getChars(); indexOf(); intern(); isEmpty(); lastIndexOf(); length(); matches(); offsetByCodePoints(); regionMatches(); replace(); replaceAll(); replaceFirst(); split(); startsWith(); subSequence(); substring(); toCharArray(); toLowerCase(); toUpperCase(); trim(); valueOf(); 
 
class java.lang.Class functions:
equals(); getClass(); hashCode(); notify(); notifyAll(); toString(); wait(); clear(); containsKey(); containsValue(); entrySet(); get(); isEmpty(); keySet(); put(); putAll(); remove(); size(); values(); clone();

Larry Battle

I love to program, and discover new tech. Check out my stackoverflow and github accounts.

More Posts - Website

Follow Me:
TwitterLinkedInYouTube

How to install Groovy 1.8.4. on Windows XP, Vista and 7.


What’s Groovy?
Groovy is an agile and dynamic language for the Java Virtual Machine and much more. Check out the
Groovy Homepage for more information.

Installation Guide:
Requires: Java JDK 1.5+ (Download here)

Windows-Installer for Groovy 1.8.4: (Download Here)

Alternative installation method: Guide.

You can check to see if groovy was properly installed by trying “groovy –version” in the command prompt.

Note: You need to close and re-open the console after changing the path environment variable.

Larry Battle

I love to program, and discover new tech. Check out my stackoverflow and github accounts.

More Posts - Website

Follow Me:
TwitterLinkedInYouTube