Another Google question - drop glassballs from a building 2 博客分类： algorithms GoogleJ#RESTjunitUP

Here is the code following the logic from the previous post:

java 代码

 

1. package glassball;  
2.   
3. import java.util.List;  
4. import java.util.ArrayList;  
5.   
6. /** 
7.  * Google interview question 
8.  */  
9. public class GlassBallPuzzle  
10. {  
11.     // first index is on glassballs, second is on sum.  
12.     // The sum is used to compare with the total floors of the building and  
13.     // then determine the last element in the previous sum, which is used  
14.     // as the starting point of the floor array.  
15.     private int[][] recursiveSums;  
16.   
17.     // the top selection of floors to try. This is not essential, but  
18.     // helpful for testing.  
19.     private int[][] floors;  
20.   
21.     private int numOfGlassballs;  
22.   
23.     private int numOfFloors;  
24.   
25.     public GlassBallPuzzle(int numOfGlassballs, int numOfFloors)  
26.     {  
27.         this.numOfGlassballs = numOfGlassballs;  
28.         this.numOfFloors = numOfFloors;  
29.   
30.         generateSumArrays();  
31.   
32.         generateFloorArrays();  
33.     }  
34.   
35.     public int getMinimalTrials()  
36.     {  
37.         // since all worst paths should have the same number, we pick up any  
38.         // worst path and should have the same number of trials. This path  
39.         // has the broken floor at level 1.  
40.         int len = recursiveSums[numOfGlassballs - 1].length;  
41.   
42.         int minimalTrials = recursiveSums[0][len-1] - 1;  
43.   
44.         // add trials.  
45.         minimalTrials += getTrials(numOfGlassballs, len);  
46.   
47.         return minimalTrials;  
48.     }  
49.   
50.     public int[] getOptimalTrialsAndBalls()  
51.     {  
52.         int minimalTrials = numOfFloors;  
53.         int minimalBalls = numOfGlassballs;  
54.   
55.         for (int nballs=1; nballs<=numOfGlassballs; nballs++)  
56.         {  
57.             int len = recursiveSums[nballs - 1].length;  
58.   
59.             int newTrials = recursiveSums[0][len-1] - 1;  
60.             // add trials.  
61.             newTrials += getTrials(nballs, len);  
62.   
63.             if (newTrials < minimalTrials)  
64.             {  
65.                 minimalTrials = newTrials;  
66.                 minimalBalls = nballs;  
67.             }  
68.         }  
69.   
70.         return new int[] { minimalTrials, minimalBalls};  
71.     }  
72.   
73.     private int getTrials(int balls, int index)  
74.     {  
75.         // to move across the arrays for balls.  
76.         int ret=0;  
77.         //  
    
78.         for (int i=0; i<balls; i++)  
79.         {  
80.             // otherwise, there is no need to try.  
81.             if (recursiveSums[i][index-1] < numOfFloors)  
82.                 ret++;  
83.         }  
84.   
85.         return ret;  
86.     }  
87.   
88.     public int[][] getRecursiveSums() { return recursiveSums; }  
89.   
90.     private void generateSumArrays()  
91.     {  
92.         recursiveSums = new int[numOfGlassballs][];  
93.   
94.         // initialize the first array with 1, 2, 3, 4, ...  
95.         recursiveSums[0] = new int[this.numOfFloors];  
96.         for (int j=0; j<numOfFloors; j++)  
97.         {  
98.             recursiveSums[0][j] = j + 1;  
99.         }  
100.   
101.         // now recursively generate the rest of arrays by summation  
102.         for (int i=1; i<numOfGlassballs; i++)  
103.         {  
104.             // since the size is unknown, so we use a list.  
105.             List sums = new ArrayList();  
106.             for (int j=0; j<numOfFloors; j++)  
107.             {  
108.                 int total = 0;  
109.                 for (int k=0; k<=j; k++) total += recursiveSums[i-1][k];  
110.                 sums.add(new Integer(total));  
111.                 if (total >= numOfFloors) break;  
112.             }  
113.             recursiveSums[i] = new int[sums.size()];  
114.             for (int j=0; j<sums.size(); j++)  
115.             {  
116.                 recursiveSums[i][j] = ((Integer)sums.get(j)).intValue();  
117.             }  
118.         }  
119.     }  
120.   
121.     private void generateFloorArrays()  
122.     {  
123.         floors = new int[numOfGlassballs][];  
124.   
125.         // If there is one ball, we have to start from floor 1, 2, etc.  
126.         floors[0] = recursiveSums[0];  
127.   
128.         // The floors starts from the end of sums series.  
129.         for (int i=1; i<numOfGlassballs; i++)  
130.         {  
131.             floors[i] = new int[recursiveSums[i].length];  
132.             int total=0;  
133.             for (int j=0; j<recursiveSums[i].length; j++)  
134.             {  
135.                 total += recursiveSums[i-1][recursiveSums[i].length - 1 - j];  
136.                 floors[i][j] = total;  
137.             }  
138.         }  
139.     }  
140.   
141.     // could be moved to somewhere else.  
142.     public void printAllResults()  
143.     {  
144.         for (int i=0; i<numOfGlassballs; i++)  
145.         {  
146.             printIntermediateSteps(i);  
147.         }  
148.     }  
149.   
150.     private void printIntermediateSteps(int ballIndex)  
151.     {  
152.         System.out.print("sum series for " + (ballIndex + 1) + " balls=");  
153.         int[] segments = recursiveSums[ballIndex];  
154.         for (int i=0; i<segments.length; i++)  
155.         {  
156.             System.out.print(segments[i] + ", ");  
157.         }  
158.         System.out.println();  
159.   
160.         System.out.print("floors series for " + (ballIndex + 1) + " balls=");  
161.         segments = floors[ballIndex];  
162.         for (int i=0; i<segments.length; i++)  
163.         {  
164.             System.out.print(segments[i] + ", ");  
165.         }  
166.         System.out.println();  
167.     }  
168. }  

The generateSumArrays() does the forward sum-ups, e.g., (1), (2), ..., this is the main functionality. There is also a floors field that holds the results from backward sum-ups, (A), (B), .... However, this field is not really used in computation, because the
starting point is dynamic, not fixed like in this field. So this is merely for information and debug. A similar method to
compute this backward sum is in another class.

Another functionality of this class is to answer the questions posted in the above Chinese paragraph. For a given height of the build, i.e., the number of  floors is fixed, how many balls are optimal, e.g., if we are given a building with 10 floors, 50 balls won't reduce the minimal trials, in fact maybe it takes the same number of trials as 10 balls. These are in the first 3 methods. The basic logic is that since the worst case trials are evenly distributed, we just find one worst path of floors to count the trials.

The test cases is

java 代码

 

1. package glassball;  
2.   
3. import junit.framework.TestCase;  
4.   
5. /** 
6.  * Testcases for minimal trials. 
7.  */  
8. public class GlassBallPuzzleTest extends TestCase  
9. {  
10.     public void test2Balls()  
11.     {  
12.         GlassBallPuzzle puzzle = new GlassBallPuzzle(2, 100);  
13.         puzzle.printAllResults();  
14.         System.out.println("minimal trials=" + puzzle.getMinimalTrials());  
15.         assertTrue(puzzle.getMinimalTrials() == 14);  
16.     }  
17.   
18.     public void test3Balls()  
19.     {  
20.         GlassBallPuzzle puzzle = new GlassBallPuzzle(3, 100);  
21.         puzzle.printAllResults();  
22.         System.out.println("minimal trials=" + puzzle.getMinimalTrials());  
23.         assertTrue(puzzle.getMinimalTrials() == 9);  
24.     }  
25.   
26.     public void test4Balls()  
27.     {  
28.         GlassBallPuzzle puzzle = new GlassBallPuzzle(4, 100);  
29.         puzzle.printAllResults();  
30.         System.out.println("minimal trials=" + puzzle.getMinimalTrials());  
31.         assertTrue(puzzle.getMinimalTrials() == 8);  
32.         int[] optimals = puzzle.getOptimalTrialsAndBalls();  
33.         System.out.println("optimal trials and balls=" + optimals[0] + ", " + optimals[1]);  
34.     }  
35.   
36.     public void test5Balls()  
37.     {  
38.         GlassBallPuzzle puzzle = new GlassBallPuzzle(5, 100);  
39.         puzzle.printAllResults();  
40.         System.out.println("minimal trials=" + puzzle.getMinimalTrials());  
41.         assertTrue(puzzle.getMinimalTrials() == 8);  
42.     }  
43.   
44.     public void test6Balls()  
45.     {  
46.         GlassBallPuzzle puzzle = new GlassBallPuzzle(6, 100);  
47.         puzzle.printAllResults();  
48.         System.out.println("minimal trials=" + puzzle.getMinimalTrials());  
49.         assertTrue(puzzle.getMinimalTrials() == 8);  
50.     }  
51.   
52.     public void test50Balls()  
53.     {  
54.         GlassBallPuzzle puzzle = new GlassBallPuzzle(50, 200);  
55.         puzzle.printAllResults();  
56.         System.out.println("minimal trials=" + puzzle.getMinimalTrials());  
57.         assertTrue(puzzle.getMinimalTrials() == 20);  
58.     }  
59. }  

The method test4Balls() prints out the optimal number which are verified by test5Balls() and test6Balls().