Goldman Sachs Interview Question
Software Engineer / DevelopersIs your arrangement like this (consider just a square, instead of cube for simplicity, so that the layer becomes a row):
10 circles, 9 on top of that, 10 on top of that ...
If so, the height increase with the second layer is 5 + 5*sqrt(3)/2. How did you get 5*sqrt(2) ? We basically have a triangular arrangement of 3 circles, where top circle sits in the slot of the 2 base circles. The triangle got by joining the centers is equilateral, so we can use (cos 30) to get the height of the center of the top circle from the previous level. ( Using this, I get 10 rows in all, with 10, 9, 10, 9, 10, 9, 10, 9, 10, 9, which is 95 in all)
Seems to me that the optimal arrangement can be got by bounding a large honeycomb structure (i.e., each sphere surrounded by 6 other spheres ad infinitum), using the cube. The puzzle would then be to see how many full spheres will be in such a cube..
Each sphere sits on other four spheres like a pyramid. Then the first layer we have 10*10 = 100 spheres. The second layer we have 9*9 = 81 spheres. We can derive that the height increase for every layer is 5*sqrt(2). In addition to half of first layer's height (i.e., 5) and half of the top layer's height (5), the total height is 5 + 5 + 5*SQRT(2)*12 = 94.9 < 100. The box can hold 12+1=13 layers. Then 100*7+81*6 = 1186.
10 * 10 * 10, each layer 10 * 10 = 100 balls.
Another case,
one layer 100 ball, its upper layer 81 ball
the height of these two layers:10 + 5*sqrt(3)
therefore, 100 / (10 + 5*sqrt(3)) = 5.3 layer => 5 layer
(100 + 81) * 5 < 1000
100 spheres is the maximum possible - the arrangement being simply stacking them exactly one on top of another & side by side. Its impossible to have more than 100 spheres - for eg., 101 spheres have a volume > 10^6, which is the volume of the box. Any other arrangement will be suboptimal.
Some more insight (hopefully correct). Lets assume the sphere size will always be 10.
So we have 2 simple arrangements - one is direct one on top of another - i.e. square arrangement and the other is hexagonal. If the box length is only 100, then square beats hexagonal - because square gives 1000, while hexagonal gives 950. If however the box length were 108, then square arrangement still gives 1000,while hexagonal arrangement gives 1090 (i.e. 100+99+100+99.. - with number of layers being 12 ).
So I guess for the given problem, the correct answer is 1000, unless your solution of 1186 is correct...
An alternative f the pyramid way is that each sphere sits on another three spheres. Let's discuss about this method. First consider the bottom layer. We can put (100-10)/(5*sqrt(3)) + 1 = 11.4 = 11 rows -- six rows of 10 spheres, five rows of 9 sphere. Hence the bottom layer can hold 6*10+5*9 = 105 spheres. But the second layer can only hold 10 rows of 9 spheres, in total 90 spheres. Now consider how many layers the box can hold. Height increase for each layer is 5*sqrt(8/3). Considering 5 + 5 + 5*SQRT(8/3)*11 = 99.8 < 100, the box can hold 11+1=12 layers. In total, the number of spheres is 105*6+90*6=1170.
This method is very good, but not as good as the pyramid way which achieves the number 1186.
thanks jobseeker...
if we join the centers of the 4 spheres, we get a square pyramid. The height (h) of such a pyramid is related to the square base (b) of the pyramid & the slant length (s) of the pyramid, by the equation s^2 = h^2 + 1/2(b^2) - I got this from a website, but I guess this can be proved. In our case, with a little imagination, we can see that s = b = 2r where r is the sphere radius, giving h = r*sqrt(2). This gives the full height of 2 layers is r+h+r == r+r*sqrt(2)+r, so the increase is r+r*sqrt(2)+r - 2r = r*sqrt(2). This will give 13 layers with a total of 1186 spheres.
Well done jobseeker.
I guess this problem needed one to be able to imagine the pyramid, after figuring out that would be the optimal arrangement. Here I give a simple proof that that altitude of such a pyramid is r*sqrt(2), if the base is 2r, and slant side is 2r:
a___________
|. .|c
| . . | we need to find the height dropped from o onto the square base
|2r * o | abcd. Due to symmetry, this height will meet the base at the
| . . | intersection of diagonals of abcd. Let this intersection point
| . . | be x. Then you can imagine that triangle aox is right angled
b|__________|d and so ox^2 = oa^2 - ax^2, where ax is the semi diagonal of
the square abcd. o is the centre of the top sphere. It is
thus raised at a total height of r + ox. So the highest point
of the top sphere is raised at a height of 2r+ox => increase =
ox.
guys ,
I cant understand why dont you do simple calculation as below
total number of oranges= volume of box/volume of each sphere
this gives 1909 spheres (approximately)
plz correct me if i am wrong...
from link http://www.tiem.utk.edu/~gross/bioed/webmodules/spherepacking.htm
the maximum packing density that can be achieved is 74.05%.hence in this case the space occupied by the spheres is 1000000*.7405=740500.
Therefore,number of spheres=(740500*3)/(4*3.142*125)=1414.
It is interesting that no one can prove what answer is correct. I will give it a try.
I will start by filling the bottom layer with rows of 10 and 9, interlaced like a honeycomb pattern. The bottome layer itself is a straight "circle stacking problem", since all these balls are on the same plane, horizontally.
The height increase for each layer in a circle stacking problem is:
sqrt(3)*r = 5*sqrt(3) in our example
(see http://www.physicsforums.com/showthread.php?t=286344 for a discussion of the height of the both layers, d + sqrt(3)*r)
However, the first layer will always take up one full diameter.
Therefore, the bottom layer filled with rows of 10 and 9 will be able to hold this many rows:
((100 - 10)/(5*sqrt(3))) + 1 = 10.39 + 1 = 11.39 (which means we can have 11 rows)
Since we can have 11 rows of 10 and 9 balls in the bottom row, we can chose to fill the first row with 10, the next with 9, and so forth giving us a bottom layer of
10*6 + 9*5 = 105 balls
Now the problem increases. The bottom layer was a "Circle Packing Problem", but the next layer will become a "Sphere Packing Problem". Here I am going to use the "HCP" method of packing the spheres, Hexagonal Close-Packed. The good thing with sphere packing is that since the spheres are now packed off center, it is likely that we can pack the layers tighter than the rows in the bottom layer.
(see http://en.wikipedia.org/wiki/Close-packing for a discussion of this method)
According to the link above, the increase in height for HCP packing is:
sqrt(6)*d/3 = 0.81649658*d = 8.1649658 in our example
Using this method to pack the layers on top of each other, again realizing that the first layer will take up a full diameter of 10, the equation is:
((100 - 10)/(sqrt(6)*d/3)) + 1 = 11.022 + 1 = 12.022 (which means we can have 12 layers)
We also need to calculate exactly how many balls will fit in the second layer, this figure will naturally be lower than 105 balls. The best way to get a feeling for how the second layer will look like is to watch this animation of this packing procedure
http://en.wikipedia.org/wiki/File:Animated-HCP-Lattice.gif
Since the second layer starts between the row of 10 and 9, and the second layer has to stop between the last rows of 9 and 10, the number of rows will be one less than in the bottom layer. This means the second layer will only have 10 rows.
Watch the animation of the packing closely and you can see that the rows will consist of 9 balls not lined up with the bottom layer followed by 10 balls lined up with the bottom layer. So the balls in the second layer will be
9*5 + 10*5 = 95 balls
In HCP packing the 2 layers repeat themselves over and over, (see figure 1 in http://en.wikipedia.org/wiki/Close-packing)
Since we have 12 layers to stack the solution is:
105 * 6 + 95 * 6 = 1200 balls
I am very surprised myself that you can stack that many balls in this cube. I would very much like someone to find holes in my theory, but please back up your holes with math, or proof from other forums online, or similar.
I had to reply to my own comment :)
There is a chance that you can get even more than 1200 balls into the cube. The reason is that in reality we were able to fit 11.39 rows in the bottom row and 12.022 on the height. And when you pack these balls, it is very likely they will use the extra 0.39 space that is available on the side, which means that each layer will be able to fall down slightly more than if we fit exactly 11 rows. But since the second figure is 12.022, only giving room for another 0.022 layers, I deem it unlikely that the extra 0.39 on the side will give a 13th layer.
If someone can prove what happens with this extra space, I am impressed.
It is impossible to fit 7 layers of 10x10 and 6 layers of 9x9. That would require
6 x sqrt(3) x10 (for every 9x9) + 10 (for top and bottom halves of 10x10) ~= 113.92 units which would exceed the dimensions.
You can fit only 6 layers of 10x10 and 5 layers of 9x9 in between them which would require 5 x sqrt(3) x 10 + 10 ~= 96.60
Hence you can fit 6 x 10 x 10 + 5 x 9 x 9 = 1005 spheres in it.
Here is how you get the magic number above. Consider the basic pyramid stacking below:
O - A
O - B
O - C
Top to the mid point of A is 5 units. Likewise bottom to mid point of C is 5 units. Length between mid A to mid B is sqrt(3) x 5 - sorry I can't make this clearer using text only. Length between mid A to mid C is sqrt(3) x 10. You need to repeat the mid A to mid C part as many as you have 9x9 layers stacked between 10x10 layers. Then you need to add the mid C to bottom length for bottom layer and top to mid A length for the top layer.
If 10units diameter sphere can fit in 10x10x10units cube............................
100x100x100units cube can fit in 10x10x10 number of 10*10*10 cubes..........
so, it is 10x10x10 number of spheres.
you can set(10+9+10+9+...+10) = 105 oranges in the bottom plane.
(11 elements)
Then on the second from bottom plane, you can set (9+10+9+10 ... +9)=104 oranges.
(11 elements)
In total you can have 11 such planes to vertical directions.
so the total number will be (105+104+105+104+ ....+105)=6*105+5*104=1150 Oranges. (11 elements)
(Ans.)
I was thinking in a different way. Could this be possible? if we keep 10 rows and 10 columns throughout the depth of the cuboid we get 10*10*10 = 1000 balls. However, the spaces created by 8 adjacent balls can accommodate 1 more ball. That way, we can keep 9 more balls in between two rows and columns. Hence, in all we can keep an additional of 9*9*9 balls more which adds upto 1000+729 = 1729 in total. That's the maximum. Can someone bring a counter example?
The length and width (considering the base here) of the box is 100*100 and diameter of the orange is 10. so the base can hold 100 oranges (10*10) because the diameter of the orange is 10 and since the height is given as is 100 units, there will be 9 more layers of 100 oranges which will result in 1000 oranges total.
My answer is 1005!
- Anonymous November 27, 2008