问一道data structure的面试题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

问一道data structure的面试题

问一道data structure的面试题# JobHunting - 待字闺中

g*22010-07-20 07:07

1 楼

不过俺做的有点失败啊，那个皮太散了，包不住馅儿啊，大家说说什么原因。

p*72010-07-20 07:07

2 楼

A graph is given. You need to design a data structure with minimum space
complexity such that it does the follows

E*A2010-07-20 07:07

3 楼

漂亮

j*w2010-07-20 07:07

4 楼

Adjacent matrix.
http://en.wikipedia.org/wiki/Adjacency_matrix
If A is the matrix. A * A can give info about a path of length 2, if my
memory is right.

m*m2010-07-20 07:07

5 楼

hao kan.

p*72010-07-20 07:07

6 楼

问题是怎么在O（N）找到是否有length为N 的path，Adj matrix 能work？

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

: Adjacent matrix.
: http://en.wikipedia.org/wiki/Adjacency_matrix
: If A is the matrix. A * A can give info about a path of length 2, if my
: memory is right.

i*h2010-07-20 07:07

7 楼

真好看，疯狂的嫉妒你们

p*72010-07-20 07:07

8 楼

我想的是create a table，把所有可能的路径都放进table里面，如果a－c有多个路径
，就用linked list放并且按路径长度排序，需要查是否有路径N的就遍历linked list
，这样就复杂度就刚好是N了。出这个题的人真变态，当场想能想出来真不容易。

l*32010-07-20 07:07

9 楼

很漂亮呀，你说皮太散了，是不是面有点干？再放点油或者水？
我只做过一次，实在经验不足。

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

: 不过俺做的有点失败啊，那个皮太散了，包不住馅儿啊，大家说说什么原因。

g*e2010-07-20 07:07

10 楼

这空间复杂度太大了

list

【在 p********7 的大作中提到】

: 我想的是create a table，把所有可能的路径都放进table里面，如果a－c有多个路径
: ，就用linked list放并且按路径长度排序，需要查是否有路径N的就遍历linked list
: ，这样就复杂度就刚好是N了。出这个题的人真变态，当场想能想出来真不容易。

g*22010-07-20 07:07

11 楼

面不干，还准备做抹茶皮的，现在有点不敢做了，害怕馅儿又漏出来。
你做馅儿那个方子很赞啊，绿豆馅儿特别香。

p*72010-07-20 07:07

12 楼

你有更好的办法？

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

: 这空间复杂度太大了
:
: list

l*32010-07-20 07:07

13 楼

谢谢
你可以把皮稍微做厚一点，我看人家的冰皮月饼面和陷的比例面大于陷，比如40:30
把冰皮味道做好一点，厚一点皮也好吃。

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

: 面不干，还准备做抹茶皮的，现在有点不敢做了，害怕馅儿又漏出来。
: 你做馅儿那个方子很赞啊，绿豆馅儿特别香。

i*e2010-07-20 07:07

14 楼

楼上已经说邻接矩阵了
这个是稍微浪费时间但是很省空间的一种方法
因为在社交网络里面计算的时候，k也不会特别大，所以可以接受
A = [a(i,j)]
where a(i,j) = a(j,i)
a(i,*) X a(*,j) = min(a(i,1)*a(1,j), a(i,2)*a(2,j), ...)
其中*运算重定义一下就好了

【在 p********7 的大作中提到】

: 你有更好的办法？

l*32010-07-20 07:07

15 楼

我发现你的月饼模子很漂亮，三个还都不相同呢，是塑料的还是木头的？