Microsoft Interview Question Software Engineer in Tests
i too worked out a simlar soln as ANON
for 2,2,3 i get around 3.95
is there a better soln for this problem??
Mr23: is it too hard for u to understand ANON's solution is absolutely wrong. Draw a rectangle of size 2 by 2 on paper, now try to pack 3 squares inside it. You can't pack more than 3 squares of size 1x1 - means output should be 1.00 (with remaining space 2x2 - 3x1x1 = 1).
I could solve it using binary search on rectangle dimension. Here's the idea:
Let, x = size of each square
f(x) = # of squares of size x that can be packed in given W x H rectange
f(x) can be computed as floor(W/x) * floor (H/x)
binary search works, because
[x1 <= x2] => [f(x1) >= f(x2)]
let me know if you find any catch there.
I dont understand the last line "Length of square doesn't have to be integer"
if length of square is not i integer then answer would go towards infinity bcoz we take the size of square very very small in decimals .
Am i going in right direction?
@rohit That is correct mathematically but in your programming language you have a limit on the precision of floating point number and after that limit you wont be able to improve the solution.
For example if the answer is 2.343423235233242344....mathematically
and your floating point precision is upto 5 digit after decimal point then
your solution will be
~2.34342
since we have to fit in N squares in b*h with length l
1st condition is l < max(b/N, h/N) since we can always put all squares in one line . it gives you max possible size of square for cases where either b > Nh or h > bN.
2nd condition is l < sqrt (b*h/N)
3rd condition is l < min(b, h)
#include<stdio.h>
- ANON June 24, 2011#include<math.h>
int main()
{
double l,b,x;
int n;
scanf("%lf%lf%d",&l,&b,&n);
x = (l*b)/n;
x = sqrt(x);
printf("required length of square is:%lf\n",x);
return 0;
}
will this work....plz verify...