这道题要用什么数据结构？ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

这道题要用什么数据结构？

这道题要用什么数据结构？# JobHunting - 待字闺中

S*C2015-04-14 07:04

1 楼

given a manager find all its subordinates, given a subordinate find all its
supervisors; 应用题一样，给定问题，选用数据结构去解
follow-up 还有没有别的数据结构可以用？怎么解？比较一下这两个方法，说一下
时间和空间的big O;
我怎么感觉用RDBMS容易多了

S*C2015-04-14 07:04

2 楼

一种想法，用2个HashMap对象
一个是
HashMap> managerBySubordinates其中key是manager，value是
subordinates
另一个是
HashMap> subordinateByManagers其中key是subordinate，
value是managers
插入N个person的时间复杂度O(n*m),m表示每个person有多少subordinates和managers
空间复杂度是O(N）

S*C2015-04-14 07:04

3 楼

另一种想法，用directed graph和HashMap
每个Person是一个Graph node
direction是从manager 到 subordinate
然后每个subordinate有一个HashMap> subordinateByManagers
的成员变量记住本人所有的managers
插入N个person的时间复杂度O(n*m),m表示每个person有多少subordinates和managers
空间复杂度也是O(N）
这个怎么样？

S*C2015-04-14 07:04

4 楼

求教高手！

g*a2015-04-14 07:04

5 楼

inverted index?

w*z2015-04-14 07:04

6 楼

这是graph 吧。

its

【在 S*******C 的大作中提到】

: given a manager find all its subordinates, given a subordinate find all its
: supervisors; 应用题一样，给定问题，选用数据结构去解
: follow-up 还有没有别的数据结构可以用？怎么解？比较一下这两个方法，说一下
: 时间和空间的big O;
: 我怎么感觉用RDBMS容易多了

P*r2015-04-14 07:04

7 楼

tree, 每个node加上parent指针

S*C2015-04-14 07:04

8 楼

要用tree的话得用n-ary tree，而且每个node都得允许有multiple parent pointer，
这样很复杂

【在 P******r 的大作中提到】

: tree, 每个node加上parent指针

r*g2015-04-14 07:04

9 楼

Linkedin 考过这个题

its

【在 S*******C 的大作中提到】

x*92015-04-14 07:04

10 楼

unordered_map
struct Node {
int employee_id;
vector superviser;
vector subordinates;
};
===
其实我没理解这个问题的难点在哪儿。。

S*C2015-04-14 07:04

11 楼

最佳答案是什么，时间空间复杂度多少？

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

: Linkedin 考过这个题
:
: its

S*C2015-04-14 07:04

12 楼

这个答案看起来不错，
换成JAVA就是
Map
Employee{
int employee_id;
Set supervisors, subordinates;//用set可以加快查询
}
插入n个employees时间复杂度就是O(n*m),其中m是每个employee有多少个supervisors
和subordinates
插入n个employees空间复杂度也是O(n*m)
查询每个employee的所有supervisors和subordinates都是O(1) 时间
对吗？

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

: unordered_map
: struct Node {
: int employee_id;
: vector superviser;
: vector subordinates;
: };
: ===
: 其实我没理解这个问题的难点在哪儿。。