Posts

TopCoder problem solution: ChristmasBatteries

This post provides a solution to the TopCoder problem of ChristmasBatteries .  This problem can be modeled as a 0-1 Knapsack problem . We can mode each toy as an item that can be put into the knapsack. The total weight allowed in the knapsack is the total number of available batteries. Each toy has two properties: fun and required batteries. The "fun" parameter is the value of the item. The required batteries is the weight of the item. The ChristmasBatteries problem can be solved by finding a subset of the toys that will maximize the fun while subjected to the constraint of the total number of available batteries. Note that the number of batteries is an integer, this is crucial for the Dynamic Programming solution to work. Implementation of the 0-1 Knapsack problem using Dynamic Programming  First, we define an interface that represents a single abstract item that can be stored in a knapsack: public interface KnapsackItem { double getValue (); int getWeight (); } Then...
Post a Comment
Read more

Calculate the height of a tree

Image
In this post, we define the height of a tree as the number of nodes in the path between the root node of the tree and the leaf node that is the furthest from the root node. See the following illustration for examples: Note that even though the trees in the examples above only have at most 2 branches, we don't need to make such an assumption. We can define a Java class to represent the tree as follows: @Builder @Value public class Tree < T > { T value ; List < Tree < T >> branches ; } We define an interface for calculating the height of the tree as follows: interface TreeHeightSolver < T > { int treeHeight ( Tree < T > tree); } Recursive solution We can recursively move down to each branch of the tree, find the height of the branch, and pick the branch with the greatest height, and add 1 to get the height of the tree. See the solution below: public class RecursiveTreeHeightSolver < T > implements TreeHeightSolver < T > { @Ove...
Post a Comment
Read more