S*******C
发帖数: 822 | 1 given a manager find all its subordinates, given a subordinate find all its
supervisors; 应用题一样，给定问题，选用数据结构去解
follow-up 还有没有别的数据结构可以用？怎么解？比较一下这两个方法，说一下
时间和空间的big O;
我怎么感觉用RDBMS容易多了 |
S*******C
发帖数: 822 | 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*******C
发帖数: 822 | 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*******C
发帖数: 822 | |
g********a
发帖数: 3 | |
w**z
发帖数: 8232 | 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******r
发帖数: 1342 | |
S*******C
发帖数: 822 | 8 要用tree的话得用n-ary tree，而且每个node都得允许有multiple parent pointer，
这样很复杂
【在 P******r 的大作中提到】
: tree, 每个node加上parent指针
|
r*g
发帖数: 186 | 9 Linkedin 考过这个题
its
【在 S*******C 的大作中提到】
: given a manager find all its subordinates, given a subordinate find all its
: supervisors; 应用题一样，给定问题，选用数据结构去解
: follow-up 还有没有别的数据结构可以用？怎么解？比较一下这两个方法，说一下
: 时间和空间的big O;
: 我怎么感觉用RDBMS容易多了
|
x*******9
发帖数: 138 | 10 unordered_map
struct Node {
int employee_id;
vector superviser;
vector subordinates;
};
===
其实我没理解这个问题的难点在哪儿。。 |
S*******C
发帖数: 822 | 11 最佳答案是什么，时间空间复杂度多少？
【在 r*g 的大作中提到】
: Linkedin 考过这个题
:
: its
|
S*******C
发帖数: 822 | 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;
: };
: ===
: 其实我没理解这个问题的难点在哪儿。。
|
