|
Given a rectangle with known width and height, design an algorithms to fill ....
Microsoft Interview Questions and Answers
(Continued from previous question...)
75. Given a rectangle with known width and height, design an algorithms to fill ....
Question:
Given a rectangle with known width and height, design an algorithms to fill the rectangle using n squares(n is integer, also given) and make sure in the result the wasting area is minimized. Length of square doesn't have to be integer.
I.e, given width=3,height=2,n=5, one solution is that rectangle can be filled with five 1x1 squares and the wasting area is 1. Another solution could be filled with five 0.9x0.9 squares, but the wasting area is more than first solution.
maybe an answer:
using binary search on square's dimension which is bounded by the range(0, min(W,H)] .
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)]
maybe an answer2:
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)
Minimum from above 3 conditions should give the answer, in case no other condition is being missed out.
Decreasing the length beyond this minimum value will increase the wasted space.
(Continued on next question...)
Other Interview Questions
| 