Home ›

Java Challenge: Dropping Balloons in Java

Nico Heid's picture
by Nico Heid on Sun, 11/15/2009 - 18:24
in

Recently I read about a nice article in one of my monthly magazines. I won't give you the author right now, otherwise googling for the solution would be too easy.
He stated it as a possible interview question, but I really like it for the algorithm side of it. It reminded my strongly of some of the
examples given in the book How Would You Move Mount Fuji? Which is excellent by the way.

So your task is to write a Java function which computes the following:

You're in possesion of two water balloons. In front of you is a building which is 100 stories high. As we're programmers there is a floor 0 (that's ok for US I guess but you have to mention that to Europeans). The challenge: Give an algorithm that tells you the highest floor where you can drop a waterballoon without breaking it. In the progress it's ok if both waterballons break, if after that you can name the correct floor. Because that's still easy, eg. we just start out with one balloon at floor 0 and work our way up, here's the real callenge: You have a maximum of 15 tries.

Append the answer in the comments. Enclose you code with the <java>your_code_here</java> tags so it gets syntax highilghting.

If nobody posts the right answer it will be published as Xmas present.

Happy coding ;-)

SPOILERS on the second page.

Comments

coworker's picture
should really sleep now
coworker (not verified) - Tue, 11/17/2009 - 03:56

  1. def checkBurst(level):
  2.     # our baloon bursts at level 99
  3.     return (level >= 99)
  4.  
  5. leftOverTries = 15
  6. checkLevel = leftOverTries
  7.  
  8. while not checkBurst(checkLevel):
  9.     print("Balloon 1 didn't burst at", checkLevel)
  10.     leftOverTries -= 1
  11.     checkLevel += leftOverTries
  12.  
  13. print("Balloon 1 burst at", checkLevel)
  14.  
  15. startLevel2ndBallon = checkLevel - leftOverTries + 1
  16.  
  17. for checkLevel in range(startLevel2ndBallon, checkLevel):
  18.     if not checkBurst(checkLevel):
  19.         print("Balloon 2 didn't burst at", checkLevel)
  20.         result = checkLevel
  21.     else:
  22.         print("Balloon 2 burst at", checkLevel)
  23.         result = checkLevel - 1
  24.         break
  25.  
  26. print ("Result:", result)

coworker's picture
more elegant
coworker (not verified) - Wed, 11/18/2009 - 13:16

This is a more elegant version... Next challenge: How has the code to be altered to support more than 2 ballons?

  1. # Ballon bursts at floor 99
  2. stillOkAtFloor = 98
  3.    
  4. def balloonIsOk(floor):
  5.     return (floor <= stillOkAtFloor)
  6.  
  7. triesLeft = 15
  8. balloonsLeft = 2
  9. currentFloor = 0
  10. testFloor = 0
  11.  
  12. while balloonsLeft and triesLeft:
  13.     stepSize = triesLeft**(balloonsLeft-1)
  14.     testFloor = currentFloor + stepSize
  15.     if balloonIsOk(testFloor):
  16.         print "%s: OK" %(testFloor)
  17.         currentFloor = currentFloor + stepSize
  18.         result = testFloor
  19.     else:
  20.         print "%s: *BURST*" %(testFloor)
  21.         balloonsLeft = balloonsLeft -1
  22.         result = testFloor - stepSize
  23.     triesLeft = triesLeft - 1
  24.  
  25. print "Ballon is still OK at: %s. floor" %(result)

dag

davidecr - David Castañeda's picture
a solution??
davidecr - David Castañeda (not verified) - Tue, 11/17/2009 - 04:23

The algorithm move incrementing the floor to test using the max number of tries available, until the first ball braks, after that go backwards (substracting the last amount added to the floors in the last operation and start adding until it finds the max floor where water ball won´t brake.

I leave the max amount of tries available inside the class that contains the algorithm after realizing that the max amount of tries depends on the number of floors available (actually for this excersise the max amount of tries available should be 14, I didn't implement how to find that number, because it's late & I'm lazy &I think somebody will tell me how to do it easyly (the first number given (1+2+3+4+n > numberOfFloors) & because I want to check my Nokia N900 order status:) )

  1. class WaterBallomsTest {
  2.  
  3.     private static final int MAX_NUMBER_OF_TRIES = 15;
  4.  
  5.     /**
  6.      * For descriptions see <a href="http://united-coders.com/nico-heid/java-challenge-dropping-balloons-in-java<br />
  7. " title="http://united-coders.com/nico-heid/java-challenge-dropping-balloons-in-java<br />
  8. ">http://united-coders.com/nico-heid/java-challenge-dropping-balloons-in-j...</a>     *
  9.      * @param topFloor        The number of bouilding floors.
  10.      * @param fisicConditions The element that determinates the conditions for ballon brake.
  11.      * @return The top floor where ballon won't brake or -1 if even from the last floor the ballon won't brake.
  12.      */
  13.     public int findMaxFloorWhereBallonWontBrake(int topFloor, FisicConditions fisicConditions) {
  14.         int numberOfTries = 0;
  15.         int numberOfBalloms = 2;
  16.         int floorToTest = 1;
  17.        
  18.         return this.doFindMaxFloor(numberOfBalloms, floorToTest, numberOfTries, topFloor, fisicConditions);
  19.     }
  20.  
  21.     private int doFindMaxFloor(int numberOfBalloms,
  22.                                int floorToTest,
  23.                                int numberOfTries,
  24.                                int topFloor,
  25.                                FisicConditions fisicConditions) {
  26.  
  27.         if (floorToTest <= topFloor) {
  28.  
  29.             if (numberOfBalloms == 2) {
  30.  
  31.                 int bestTestFloor = floorToTest + (MAX_NUMBER_OF_TRIES - numberOfTries);
  32.  
  33.                 if (fisicConditions.doesBallonBreakAtFloor(bestTestFloor)) {
  34.                     return doFindMaxFloor(1, floorToTest, ++numberOfTries, topFloor, fisicConditions);
  35.                 } else {
  36.                     return doFindMaxFloor(2, bestTestFloor, ++numberOfTries, topFloor, fisicConditions);
  37.                 }
  38.  
  39.             } else {
  40.  
  41.                 if (numberOfTries > MAX_NUMBER_OF_TRIES) {
  42.                     return floorToTest - 1;
  43.                 } else {
  44.                     if (fisicConditions.doesBallonBreakAtFloor(floorToTest)) {
  45.                         return floorToTest - 1;
  46.                     } else {
  47.                         return doFindMaxFloor(1, ++floorToTest, ++numberOfTries, topFloor, fisicConditions);
  48.                     }
  49.                 }
  50.             }
  51.            
  52.         } else {
  53.             return -1;
  54.         }
  55.     }
  56. }
  57.  
  58. class FisicConditions {
  59.     private int lastFloorWhereDoesNotBreak;
  60.  
  61.     public FisicConditions(int topFloorWhereDoesNotBreak) {
  62.         this.lastFloorWhereDoesNotBreak = topFloorWhereDoesNotBreak;
  63.     }
  64.  
  65.     boolean doesBallonBreakAtFloor(int testFloor) {
  66.         return testFloor > lastFloorWhereDoesNotBreak;
  67.     }
  68. }
  69.  
  70. public class Test {
  71.  
  72.     public static void main(String[] args) {
  73.  
  74.         WaterBallomsTest waterBallomsTest = new WaterBallomsTest();
  75.  
  76.         int topFloor = 100;
  77.  
  78.         //test before first floor and all floors
  79.         for (int topFloorWhereDoesNotBreak = 0; topFloorWhereDoesNotBreak < topFloor; topFloorWhereDoesNotBreak++) {
  80.  
  81.             FisicConditions fisicConditions = new FisicConditions(topFloorWhereDoesNotBreak);
  82.  
  83.             int maxFloorWhereBallonWontBrake =
  84.                     waterBallomsTest.findMaxFloorWhereBallonWontBrake(topFloor, fisicConditions);
  85.  
  86.             if (topFloorWhereDoesNotBreak != maxFloorWhereBallonWontBrake) {
  87.                 throw new RuntimeException("HollySh*tException: " +
  88.                         "{topFloorWhereDoesNotBreak:" + topFloorWhereDoesNotBreak +
  89.                         ",result:" + maxFloorWhereBallonWontBrake + "}");
  90.             }
  91.         }
  92.  
  93.  
  94.         //test not floor found condition
  95.         FisicConditions fisicConditions = new FisicConditions(100);
  96.  
  97.         int maxFloorWhereBallonWontBrake =
  98.                 waterBallomsTest.findMaxFloorWhereBallonWontBrake(topFloor, fisicConditions);
  99.  
  100.         if (-1 != maxFloorWhereBallonWontBrake) {
  101.             throw new RuntimeException("HollySh*tException: " + "{topFloorWhereDoesNotBreak:" + 100 + ",result:" + maxFloorWhereBallonWontBrake + "}");
  102.         }
  103.     }
  104. }

Anonymous's picture
Trying to recall my physics,
Anonymous (not verified) - Tue, 11/17/2009 - 09:42

Trying to recall my physics, I would like to ask the following question. Could we assume that if a waterballon would break at floor n, then it would break if we dropped it from higher floors? If this is the case, then we need log2(100) attempts.

Nico Heid's picture
getting closer
Nico Heid - Tue, 11/17/2009 - 10:03

yes, we can assume this. so 2 more spoilers for you:
as we can see, linear won't work, too many attempts.
logarithmic (binary search) won't work because you'd need more than 2 balloons. and creating more balloons will count as cheating.

so think of something else. it's a bit tricky, but that's why it's called a challenge.

antorun's picture
dynamic programming
antorun (not verified) - Tue, 11/17/2009 - 11:46

Dynamic programming and some precalculation.
Key function f(floor,egg) = minimal number of try need to find correct floor number. Consider 2 cases and construct idea of calculation based on floor count and egg (waterbaloon) count.

  1. // dynamic programming
  2.  
  3. public class Solution {
  4.         public static void main(String[] args) {
  5. EagleOnARoofSolution solution = new EagleOnARoofSolution();
  6.                 int maxFloor = 100;
  7.                 int maxEgg = 2;
  8.                 solution.prepare();
  9.                 System.out.println(solution.getMinimalNumberOfExperiments(maxFloor,
  10.                                 maxEgg));
  11.         }
  12. }
  13.  
  14. class EagleOnARoofSolution {
  15.  
  16.         public void prepare() {
  17.                 getPrecalcMinimalNumberOfExperiments(1000, 1000);
  18.         }
  19.  
  20.         public int getMinimalNumberOfExperiments(int maxFloor, int maxEgg) {
  21.                 int result, log;
  22.                 if (maxEgg == 1) {
  23.                         result = maxFloor;
  24.                 }
  25.                 else {
  26.                         log = Util.getBinLogarithm(maxFloor);
  27.                         if (maxEgg > log) {
  28.                                 maxEgg = log;
  29.                         }
  30.                         result = this.dpTable[maxFloor][maxEgg];
  31.                 }
  32.                 return result;
  33.         }
  34.  
  35.         private int getPrecalcMinimalNumberOfExperiments(int maxFloor, int maxEgg) {
  36.                 int floor, egg;
  37.                 int result;
  38.                 int log;
  39.  
  40.                 if (maxEgg == 1) {
  41.                         result = maxFloor;
  42.                 }
  43.                 else {
  44.                         log = Util.getBinLogarithm(maxFloor);
  45.                         if (maxEgg > log) {
  46.                                 maxEgg = log;
  47.                         }
  48.                         init(maxFloor, maxEgg);
  49.                         for (floor = 1; floor <= maxFloor; ++floor) {
  50.                                 for (egg = 2; egg <= maxEgg; ++egg) {
  51.                                         int cur = Integer.MAX_VALUE;
  52.                                         for (int index = 1; index <= floor; ++index) {
  53.                                                 int tmp = Math.max(this.dpTable[index - 1][egg - 1],
  54.                                                                 this.dpTable[floor - index][egg]);
  55.                                                 if (cur > tmp)
  56.                                                         cur = tmp;
  57.                                         }
  58.                                         this.dpTable[floor][egg] = ++cur;
  59.                                 }
  60.                         }
  61.                         result = this.dpTable[maxFloor][maxEgg];
  62.                 }
  63.                 return result;
  64.         }
  65.  
  66.         private void init(int floor, int egg) {
  67.                 int i;
  68.                 for (i = 1; i <= floor; ++i) {
  69.                         this.dpTable[i][1] = i;
  70.                 }
  71.                 for (i = 0; i <= egg; ++i) {
  72.                         this.dpTable[0][i] = 0;
  73.                 }
  74.         }
  75.  
  76.         int[][] dpTable = new int[MAX_FLOOR][MAX_EGG];
  77.  
  78.         private static final int MAX_FLOOR = 1000 + 1;
  79.         private static final int MAX_EGG = 10 + 1;
  80. }
  81.  
  82. class Util {
  83.         public static int getBinLogarithm(int floor) {
  84.                 int result = 0;
  85.                 while (floor > 0) {
  86.                         floor >>= 1;
  87.                         ++result;
  88.                 }
  89.                 return result;
  90.         }
  91. }

Matthias Reuter's picture
Javascript version
Matthias Reuter - Tue, 11/17/2009 - 12:12

I'm not much of a Java coder, so here's my Javascript solution. The algorithm basically consists of two functions, "jump", which is called until the first balloon pops, and "walk" which is called afterwards until the second balloon pops or there are no more tries left:

var numberOfFloors    = 100;
var numberOfTrialsLeft = 15;

// What a coincidence it is to call floor when randomly generating a floor number :-)
var highestFloor = Math.floor(Math.random() * numberOfFloors);

var balloonBreaksOnFloor = function (floorNumber) {
    if (numberOfTrialsLeft === 0) {
        throw "Sorry, no more trials left";
    }
    numberOfTrialsLeft--;
    return floorNumber > highestFloor;
};

var walk = function (lastFloorThatWorked) {
    if (numberOfTrialsLeft === 0) {
        return lastFloorThatWorked;
    }
    var nextFloorToCheck = lastFloorThatWorked + 1;
    if (balloonBreaksOnFloor(nextFloorToCheck)) {
        return lastFloorThatWorked;
    }
    return walk(nextFloorToCheck);
};

var jump = function (lastFloorThatWorked) {
    var nextFloorToCheck = lastFloorThatWorked + numberOfTrialsLeft;
    if (balloonBreaksOnFloor(nextFloorToCheck)) {
        return walk(lastFloorThatWorked);
    }
    return jump(nextFloorToCheck);
};

var getHighestFloorNumber = function () {
    return jump(-1);
};

Matthias Reuter's picture
More challenging
Matthias Reuter - Tue, 11/17/2009 - 12:18

Actually, more challenging is the following task:

Given a number of balloons and a number of trials, what is the maximum number of floors you can check?

Nico Heid's picture
recursion
Nico Heid - Tue, 11/17/2009 - 13:48

if you figured out the pattern for the given problem your question would lead to using on part of the puzzle solving recursively till you have only one balloon left.
so it is indeed a nice bonus for complexity. (and maybe another challenge in javascript? ) :-)

kkreja's picture
int nrOfTries = 15; int
kkreja (not verified) - Tue, 11/17/2009 - 13:03

  1. int nrOfTries = 15;
  2. int currFloor = 0;
  3.                
  4. while(currFloor < 100 && (nrOfTries > 0)){
  5.         --nrOfTries;
  6.         currFloor += nrOfTries;
  7.         if (currFloor>100) currFloor=100;
  8.         System.out.println("trying floor: " + currFloor + " tries left for 2nd baloon: " + nrOfTries);
  9. }

Daniel Ribeiro's picture
Answer with validating function
Daniel Ribeiro (not verified) - Wed, 11/18/2009 - 04:20

Whole answer, testing for all floors. Would be much cleaner in Scala/Ruby, but it is not that much code:

  1. interface Building {
  2.         boolean doesItPopOn(int floor);
  3. }
  4.  
  5.  
  6. class ConcreteBuilding implements Building {
  7.         private int floorThreshold;
  8.         private int numberOfBaloons = 2;
  9.         private int totalTries = 0;
  10.        
  11.         public ConcreteBuilding(int floorThreshold) {
  12.                 this.floorThreshold = floorThreshold;
  13.         }
  14.        
  15.         public int totalTries() {
  16.                 return totalTries;
  17.         }
  18.  
  19.         @Override
  20.         public boolean doesItPopOn(int floor) {
  21.                 assertHasEnoughBaloon();
  22.                 totalTries++;
  23.                 if (floor >= floorThreshold) {
  24.                         numberOfBaloons --;
  25.                 }
  26.                 return floor >= floorThreshold;
  27.         }
  28.  
  29.         private void assertHasEnoughBaloon() {
  30.                 if (numberOfBaloons <= 0) {
  31.                         throw new IllegalStateException("No more baloons");
  32.                 }
  33.         }
  34.  
  35. }
  36.  
  37. public class BuildingPuzzle {
  38.         public static void main(String[] args) {
  39.                 new BuildingPuzzle().validateSolver();
  40.         }
  41.        
  42.         public void validateSolver() {
  43.                 for (int value = 0; value <= 100; value++) {
  44.                         ConcreteBuilding b = new ConcreteBuilding(value);
  45.                         int result = new BuildingPuzzle().solve(b, 15);
  46.                         System.out.printf("Expected %d, got %d (ok? = %s).", value, result, value == result)
  47.                                 .printf("Number of tries: %d (less than 15? = %s) ", b.totalTries(), b.totalTries() <= 15)
  48.                                 .println();
  49.                 }
  50.         }
  51.        
  52.        
  53.        
  54.         public int solve(Building building, int tries) {
  55.                 return recSolve(building, tries, 0);
  56.         }
  57.  
  58.         private int recSolve(Building building, int tries, int lowfloor) {
  59.                 int thresHold = lowfloor + tries - 1;
  60.                 if (building.doesItPopOn(thresHold)) {
  61.                         for (int currentFloor = lowfloor; currentFloor < thresHold - 1; currentFloor ++) {
  62.                                 if (building.doesItPopOn(currentFloor)) {
  63.                                         return currentFloor;
  64.                                 }
  65.                         }
  66.                         return thresHold;
  67.                 }
  68.                 return recSolve(building, tries - 1, thresHold + 1);
  69.         }
  70. }

DannyB's picture
I have an algorithm, but not a name for it.
DannyB (not verified) - Wed, 11/18/2009 - 17:29

Classical binary search is ruled out because we can not exceed two failures but will not have reached a solution.

Having only two balloons means we can only work upward.

My first thought was to start at floor 1 and work up by adding powers of two. Therefore, we will check floors 1, 3, 7, 15, 31, 63. Continuing along this line of analysis, it eventually becomes clear that we need to be more optimal early on and add more than 2 to floor 1 to take advantage of the number of available trials remaining.

If the balloon doesn't break at floor 1, then we have used 1 trial, have 14 left and 2 balloons.

Let's add the number of remaining trials to determine the next floor to check. 14 trials left means we add 14 to 1 to check floor 15 next. If the balloon breaks at floor 15, we have used 2 trials, have 13 trials left and one balloon. We incrementally check floors 2 through 14, which uses up all 13 remaining trials. We now have our answer.

If the balloon did not break at floor 15, we have used 2 trials, have 13 trials left and 2 balloons. We add the number of trials left to 15 to get floor 28 to check next. If the balloon breaks at floor 28, we have used 3 trials, have 12 left and 1 balloon. We incrementally check floors 16 through 27 and we have our answer.

If the balloon did not break at floor 28, we have used 3 trials, have 12 left, and 2 balloons. We add the number of trials left to 28 to get floor 40 to check next. If the balloon breaks at floor 40, we have used 4 trials, have 11 left and 1 balloon. We incrementally check floors 29 throu 39 and we have our answer.

If the balloon did not break at floor 40, we have used 4 trials, have 11 left, and 2 balloons. We add the number of trials left to 40 to get floor 51 to check next. If the balloon breaks at floor 51, we have used 5 trials, have 10 left and 1 balloon. We incrementally check floors 41 through 50 and we have our answer.

If the balloon did not break at floor 51, we have used 5 trials, have 10 left, and 2 balloons. We add the number of trials left to 51 to get floor 61 to check next. If the balloon breaks at floor 61, we have used 6 trials, have 9 left and 1 balloon. We incrementally check floors 52 through 60 and we have our answer.

If the balloon did not break at floor 60, we have used 6 trials, have 9 left, and 2 balloons. We add the number of trials left to 60 to get floor 69 to check next. If the balloon breaks at floor 69, we have used 7 trials, have 8 left and 1 balloon. We incrementally check floors 61 through 68 and we have our answer.

If the balloon did not break at floor 69, we have used 7 trials, have 8 left, and 2 balloons. We add the number of trials left to 69 to get floor 77 to check next. If the balloon breaks at floor 77, we have used 8 trials, have 7 left and 1 balloon. We incrementally check floors 70 through 76 and we have our answer.

If the balloon did not break at floor 77, we have used 8 trials, have 7 left, and 2 balloons. We add the number of trials left to 77 to get floor 84 to check next. If the balloon breaks at floor 84, we have used 9 trials, have 6 left and 1 balloon. We incrementally check floors 78 through 83 and we have our answer.

If the balloon did not break at floor 84, we have used 9 trials, have 6 left, and 2 balloons. We add the number of trials left to 84 to get floor 90 to check next. If the balloon breaks at floor 90, we have used 10 trials, have 5 left and 1 balloon. We incrementally check floors 85 through 89 and we have our answer.

If the balloon did not break at floor 90, we have used 10 trials, have 5 left, and 2 balloons. We add the number of trials left to 90 to get floor 95 to check next. If the balloon breaks at floor 95, we have used 11 trials, have 4 left and 1 balloon. We incrementally check floors 91 through 94 and we have our answer.

If the balloon did not break at floor 95, we have used 11 trials, have 4 left, and 2 balloons. We add the number of trials left to 95 to get floor 99 to check next. If the balloon breaks at floor 99, we have used 12 trials, have 3 left and 1 balloon. We incrementally check floors 96 through 98 and we have our answer.

If the balloon did not break at floor 99, we have used 12 trials, have 3 left, and 2 balloons. We add the number of trials left to 99 to get floor 102 to check next. Since 102 is greater than 100, we incrementally check floors above 99 up to floor 100 and we have our answer.

It took me about an hour to work this out, without using your spoiler.

It is also clear how to generalize the algorithm.

I could now trivially write the code in Java, or a dozen other languages, but I'll leave that as an exercise.

Nico Heid's picture
nice. indeed, the coding part
Nico Heid - Wed, 11/18/2009 - 21:02

nice.
indeed, the coding part is not that important. it was the puzzle that also got my attention.

coyote's picture
You must have been joking
coyote (not verified) - Thu, 11/26/2009 - 23:00

You must have been joking writing such explanation... I mean, did you manually change the numbers in your description or did you write a program to output all those sentences. :-P
This is not an algorithm - this is almost a step by step debugging.

By the way, this was one of the questions at Google job interviews. (instead of balloons they used eggs)
http://www.businessinsider.com/answers-to-15-google-interview-questions-...

Kevin's picture
Hey, it's my answer.
Kevin (not verified) - Fri, 11/20/2009 - 12:09

Hey, it's my answer.

http://blog.lckymn.com/2009/11/20/java-challenge-dropping-balloons-in-java/

Regards,
Kevin

Nico Heid's picture
very nice article
Nico Heid - Sat, 11/21/2009 - 12:06

you put some effort into it. :-) very good

Re: Java Challenge: Dropping Balloons in Java &amp;amp;laquo; Ke's picture
Pingback
Re: Java Challenge: Dropping Balloons in Java &amp;laquo; Ke (not verified) - Fri, 04/30/2010 - 20:15

[...] Java Challenge: Dropping Balloons in Java About a few days ago, I read this post, Java Challenge: Dropping Balloons in Java having an interesting [...]