上一道G家题# JobHunting - 待字闺中
g*y
1 楼
Given a decision tree, and lower & upper bounds for each dimension of a d-
dimension space. Find the maximum volume of the d-dimension space and its
lower and upper bounds. 大家有没有优于O(n)的解法?
这题有点绕. 举个两维的例子:
initial range for d0 is (0,10), d1 is (0,10)
Decision tree
idx=1,split=4
/ \
/ \
null idx=0,split=2
d1
10 | |
| |
| |
4 |___|_______________
|
|
|___________________
0 2 10 d0
dimension space. Find the maximum volume of the d-dimension space and its
lower and upper bounds. 大家有没有优于O(n)的解法?
这题有点绕. 举个两维的例子:
initial range for d0 is (0,10), d1 is (0,10)
Decision tree
idx=1,split=4
/ \
/ \
null idx=0,split=2
d1
10 | |
| |
| |
4 |___|_______________
|
|
|___________________
0 2 10 d0