Amazon Interview Question
SDE-2sCountry: India
Interview Type: In-Person
bool can_fit(int x, int a, int b, int c) {
#define re(x) (x-(x%2)) /* round down to even */
int n_choc = (re(a)*re(b)*re(c))/8;
return x <= n_choc;
}
Isn't this a simple math problem? Compute total volume of box - as a*b*c. Then find out how many chocolates can fit in to the box by division.
VolBox = a*b*c
VolChoc = 2
X = VolBox / VolChoc
If X >= 1 - return X and say atlteast X chocolates can fit into the box.
else. return 0 and say no chocolates of 2cm3 can fit into the box.
Unless the question is incomplete, this should be the solution
Because they're cuboids, the chocolates can be any shape. Max volume of chocolate equals volume of box. Max count of chocolates equals half the volume of chocolate (in cm^3) or half the volume of the box. Am I missing something?
static int howManyFit(float length, float width, float height) {
return (int)(length * width * height) / 2;
}
static boolean canFit(int count, float length, float width, float height) {
return count <= howManyFit(length, width, height);
}
public void testHowManyFit() {
assertEquals(1, howManyFit(1,1,2));
assertEquals(true, canFit(1, 1,1,2));
assertEquals(false, canFit(2, 1,1,2));
assertEquals(2, howManyFit(1,2,2));
assertEquals(true, canFit(2, 1,2,2));
assertEquals(false, canFit(3, 1,2,2));
}
1. What is the individual dimension on each chocolate ? L x b x h? It can 1x1x2 or cuberoot(2) ^3. All solutions discussed are assuming each side is of dimension 2 which is not the case from the question atleast.
2. Are all chocolates are of same dimension or different dimension ? [they could still have same volume]
You have to take into account the fact that cuboids might not fit directly into the bigger cuboid- the volumes might be divisible, but physically, it might not be viable.
For example, if we take rectangles of size 4x3, our area would be 12. If we try to fit squares of 2x2 into that area, at first we might think just to divide 12 by 4 to get 3 squares that fit, but if you actually draw it out, you can only really get 2 squares to fit.
So, we need to break this down based on how many ways we can divide each dimension by 2, and take the floor of that, since anything above that would just be extra space.
- SK July 08, 2015