|
Given a rectangle with known width and height, design an algorithms to ......
Software QA/Tests Interview Questions from Microsoft
(Continued from previous question...)
Given a rectangle with known width and height, design an algorithms to ......
Q:
Microsoft Interview Question for Software Engineer in Tests about Algorithm
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.
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)]
(Continued on next question...)
Other Interview Questions
| 