amazon一道面试题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

amazon一道面试题

amazon一道面试题# JobHunting - 待字闺中

s*a2010-04-13 07:04

1 楼

不知道是不是旧题，在版面上没搜到。
how many different binary trees you can build with N nodes? For example, one
node: 1 tree; 2 nodes: 2 trees; 3 nodes: 5 trees...
面试的时候没想起来怎么做时间就到了，很是郁闷。

c*r2010-04-13 07:04

2 楼

你确定面的不是化学公司吧

k*k2010-04-13 07:04

3 楼

catalan number:
http://en.wikipedia.org/wiki/Catalan_number

s*92010-04-13 07:04

4 楼

面试中能给出 N(i)=sum(N(j)*N(i-1-j), j=0..i-1) 估摸着够了吧

【在 k*k 的大作中提到】

: catalan number:
: http://en.wikipedia.org/wiki/Catalan_number

k*e2010-04-13 07:04

5 楼

99.9%够了
不够只可能是你碰到一个专门搞combinatorics的对于生成函数之类的特别熟练
然后看你很不爽非要你现场推导公式

【在 s**9 的大作中提到】

: 面试中能给出 N(i)=sum(N(j)*N(i-1-j), j=0..i-1) 估摸着够了吧

w*12010-04-13 07:04

6 楼

(1/n+1) * C(n,2n)

s*92010-04-13 07:04

7 楼

你，推出来的？

【在 w******1 的大作中提到】

: (1/n+1) * C(n,2n)

w*12010-04-13 07:04

8 楼

GOOGLE 出来的， ALGORITHM 教材有总结的吧。

【在 s**9 的大作中提到】

: 你，推出来的？

s*a2010-04-13 07:04

9 楼

我问面试官是推导出一个公式吗，他说用一个公式表示可能比较困难，他还让我写code
来计算看组成的binary tree树，提示我用递归。我想了半天也也没想出来怎么用递归
。哪位牛人可以指点一下吗？

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

: 99.9%够了
: 不够只可能是你碰到一个专门搞combinatorics的对于生成函数之类的特别熟练
: 然后看你很不爽非要你现场推导公式

l*m2010-04-13 07:04

10 楼

把结果显式的写出来挺麻烦
写出递归函数很容易
你CLRS还没有吃透回去看看矩阵相乘的dp算法和书后练习

code

【在 s****a 的大作中提到】

: 我问面试官是推导出一个公式吗，他说用一个公式表示可能比较困难，他还让我写code
: 来计算看组成的binary tree树，提示我用递归。我想了半天也也没想出来怎么用递归
: 。哪位牛人可以指点一下吗？

m*g2010-04-13 07:04

11 楼

是否可以这样递归
如果n node form T(n) binary trees，
T(n+1) 便在T(n)上面加一个。
从most unbalanced binary tree, n nodes, n possible positions to add
到most balanced binary tree, n nodes, 0 possible positions to add
是不是T(n+1)=T(n)+(n-1+n-2+...+1)
这样搞？

d*i2010-04-13 07:04

12 楼

It is not hard :
def T(n):
if n == 0: return 1
if n == 1: return 1
sub_nodes_total = n - 1
combination_count = 0
for i in xrange(0, n): # i iterated from 0 to (n - 1)
left_node_count = i
right_node_count = sub_nodes_total - i
left_combination_count = T(i) # combination count of left sub tree
right_combination_count = T(right_node_count) # combination count of right sub tree
combination_count += left_combination_count * right_combination

【在 s****a 的大作中提到】

m*g2010-04-13 07:04

13 楼

没看懂
讲讲

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

: It is not hard :
: def T(n):
: if n == 0: return 1
: if n == 1: return 1
: sub_nodes_total = n - 1
: combination_count = 0
: for i in xrange(0, n): # i iterated from 0 to (n - 1)
: left_node_count = i
: right_node_count = sub_nodes_total - i
: left_combination_count = T(i) # combination count of left sub tree

w*12010-04-13 07:04

14 楼

两个node为什么只能build 2个trees??
两个node都可以当root是吧，再加上左或右child。。。。4个吧？？

l*a2010-04-13 07:04

15 楼

only 2 nodes
where did the other 2 came from？

【在 w*****1 的大作中提到】

: 两个node为什么只能build 2个trees??
: 两个node都可以当root是吧，再加上左或右child。。。。4个吧？？

t*g2010-04-13 07:04

16 楼

for 2 nodes A/B
do we differ between left tree and right tree?
i mean
A
/
B (B是left child)
or
A
\
B(B right child)
这算2个不同的tree么

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

: only 2 nodes
: where did the other 2 came from？

B*t2010-04-13 07:04

17 楼

I think the question is to ask "how many different BINARY SEARCH TREES", not
"binary trees", otherwise the answer is not Catalan number, but the answer
can also be found by DP.

one

【在 s****a 的大作中提到】

: 不知道是不是旧题，在版面上没搜到。
: how many different binary trees you can build with N nodes? For example, one
: node: 1 tree; 2 nodes: 2 trees; 3 nodes: 5 trees...
: 面试的时候没想起来怎么做时间就到了，很是郁闷。

l*a2010-04-13 07:04

18 楼

they are definitely different

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

: for 2 nodes A/B
: do we differ between left tree and right tree?
: i mean
: A
: /
: B (B是left child)
: or
: A
: \
: B(B right child)

l*a2010-04-13 07:04

19 楼

no,they just ask how many binary trees
denali's answer is right

not
answer

【在 B*****t 的大作中提到】

: I think the question is to ask "how many different BINARY SEARCH TREES", not
: "binary trees", otherwise the answer is not Catalan number, but the answer
: can also be found by DP.
:
: one