非典型面试题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

非典型面试题

非典型面试题# JobHunting - 待字闺中

l*i2012-06-07 07:06

1 楼

one step in classification using decision tree: find an optimal split for a
set of one-dimensional example-label pairs such that the misclassifications
are minimized
findOptimalSplit(double* example, bool *label, int num)
I answered with a linear search solution, but the interviewer was not happy
with it. Should it be DP?

l*82012-06-07 07:06

2 楼

不是每个人都熟悉decision tree classification, 给个例子吧。

a
misclassifications
happy

【在 l****i 的大作中提到】

: one step in classification using decision tree: find an optimal split for a
: set of one-dimensional example-label pairs such that the misclassifications
: are minimized
: findOptimalSplit(double* example, bool *label, int num)
: I answered with a linear search solution, but the interviewer was not happy
: with it. Should it be DP?

l*82012-06-07 07:06

3 楼

What is your linear algorithm?
If example is already sorted, I think we still need O(N) time to find
optimal split, which is linear.

g*e2012-06-07 07:06

4 楼

llyod max algo

l*82012-06-07 07:06

5 楼

what is the time complexity?

【在 g*********e 的大作中提到】

: llyod max algo

g*e2012-06-07 07:06

6 楼

polynomial， should be fine.

【在 l*********8 的大作中提到】

: what is the time complexity?

l*i2012-06-07 07:06

7 楼

Yes, assume the examples are already sorted. We can search through the set
to find the optimal split point t:
rmin = INFINITY
for z = x_i
calculate r = misclassification rate
if (r < rmin) rmin = r, z = x_i
return x_i

【在 l*********8 的大作中提到】

: What is your linear algorithm?
: If example is already sorted, I think we still need O(N) time to find
: optimal split, which is linear.

l*82012-06-07 07:06

8 楼

How do you calculate r = misclassification rate ?
If it's O(n), then the overall time complexity is o(n^2)

【在 l****i 的大作中提到】

: Yes, assume the examples are already sorted. We can search through the set
: to find the optimal split point t:
: rmin = INFINITY
: for z = x_i
: calculate r = misclassification rate
: if (r < rmin) rmin = r, z = x_i
: return x_i
:

l*82012-06-07 07:06

9 楼

I think llyod max algo is a more general algorithm. For this question, we
can have linear algorithm if "examples" are already sorted.

【在 g*********e 的大作中提到】

:
: polynomial， should be fine.