Goldman Sachs Interview Question Software Engineer / Developers




Comment hidden because of low score. Click to expand.
2
of 4 vote

My answer is 1005!

- Anonymous on November 27, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

According to my previous post, the optimum is
10*10*7 + 9*9*6 = 1186.

- jobseeker on November 02, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- acoader on November 02, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- jobseeker on November 02, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@acoader: let me correct u... triangle joined by connecting the three spheres is not an equilateral trianle since some additional space would be thr between the bottom-sphere and the top-sphere. So the height increase with the second layer is 5+5*sqrt(2).

- abhishek on September 04, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous on November 01, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 0 votes

Actually for each level, the height increase is 5*sqrt(2), except first level and last level. So # of levels should be
(100-10) / (5*sqrt(2)) + 1 = 13.2 > 13.
Then we have 7 levels of 10*10 and 6 levels of 9*9.

- jobseeker on November 01, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- acoader@gmail.com on November 02, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

oops, take that back. I meant 1000 is maximum possible using the direct arrangement. But volume wise, one should be able to accommodate over 2000 spheres! (i.e. 10^6/(4/3)*pi*125 ). How do we prove that 1000 is optimum ?

- acoader on November 02, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- acoader on November 02, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Anonymous on November 02, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This one is correct!

- ygfster on July 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I am just wondering, why don't you people who says 1000 is optimal, try at least look around the Internet?

http://en.wikipedia.org/wiki/Close-packing

- Schultz on November 03, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- acoader@gmail.com on November 03, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The height isn't sqrt(2)*d/2. It's sqrt(3)*d/2.

- wiwi on November 07, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think the right answer is 1086

- Anonymous on November 27, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

100 + (100+81) X 5 = 1005

- try4fun on December 11, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1 layer: 10*6+9*5=105
2 layer: 9*6+10*5=104
...

105*6+104*5=1150

- Anonymous on January 08, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- Ganesh.Deo on February 17, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yeah, I'm not sure either. Sounds right.

- Anon on February 18, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

because u r an idiot !
next thing u will say is that u can fit two squares of size 2x2 in a rectangle of size 1x8 just because
total area of rectangle/area of square= 2..
idiot !

- Anonymous on July 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

you can not do volume of box divided by volume of each sphere as there will be small empty pockets where you can not fit anything. Your reasoning might work for liquids/gasses but not for solid spheres.

- ikonos on February 23, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In each horizantal layer we can keep 105.(10,9,10,9,10,9,10,9,10,9,10).And we have 12 layers vertically............ so 105*12=1260. I think it is the max......................

- surya teja guptha on March 08, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In each horizantal layer we can keep 105.(10,9,10,9,10,9,10,9,10,9,10).And we have 12 layers vertically............ so 105*12=1260. I think it is the max......................

- surya teja guptha on March 08, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

shouldnt the height increment be 5*sqrt(3), then the max is 1005?

- anonymous on March 16, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

http://www.tiem.utk.edu/~gross/bioed/webmodules/spherepacking.htm

- Addy on May 26, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

even i think so..

- abh007 on July 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why doesn't someone just try it?

- Experiment on April 15, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

cuz no one's got the balls.

- cacci on May 06, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

LOL cacci... i'm still laughing at ur comment.. good one!

- VK on July 07, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- mayank on June 03, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This seems to be correct

- pavan on December 02, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

i think it should be right.

- Anonymous on September 18, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

That should be where packing exactly fits but here 100 is not a figure for that

- Trying on May 26, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Monsu on June 07, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Monsu on June 07, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I got the same answer through the same reasoning.

- ss on February 11, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

6*10*10+6*9*9+10*10=1186

- Anonymous on June 17, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

one layer: 10x6+9x5=105
vertically: 1000/(2sqrt(2)/sqrt(3))=12
total =12*105=1260

- Anonymous on June 17, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- oa on October 09, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1027 is the answer

- J on January 22, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- nagabhushana.s on July 02, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In simple packing format your answer is right.

- braj on August 07, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Mathteacher on October 19, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

- Anagha on July 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

One sphere can be fitted in a box with dimensions 10x10x10.
So, required number of spheres is 1000.

- john.matheus on July 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

640 * sqrt(5) answer use face centred cubic packing

- xx_x on February 04, 2013 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More