求問一題G家面經 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

求問一題G家面經

求問一題G家面經# JobHunting - 待字闺中

n*e2016-01-29 08:01

1 楼

输入为List，string的格式类似于： (peer,Bob,David), (peer,David,
Christina),(manager,Tina,Bob) 表示Bob和David是同事，David和Christina是同事，
Tina是Bob的manager
让你设计一种数据结构储存这些关系，并且implement以下function：
boolean is_peer(某个员工,某个员工)
boolean is_manager(某个员工，某个员工)
peer的意思是他们有共同的direct manager才算peer，如果他们的manager的manager相
同，不算peer
is_manager返回时，不需要是直接的manager，例如假设Jessica 是 Eric的manager的
manager的manager，这种情况也返回true.
这题是版上某位大牛的面试题, 我想了很久不确定怎麽做最好, 请各位大牛开释

t*r2016-01-29 08:01

2 楼

这题是我发的嘛，但我不是大牛,我只是一个还没工作的学生。。。
面挂了以后我本来是已经感累不爱了不想参加任何google的题的讨论了，看你这么执着
发了3个地方的问，我还是说一下我那会的做法
加油！你会拿下google的！
这个题不难，就是有一点点绕
我最直接的想法是并查集，很容易返回is_manager。但是并查集无法给出is_peer
所以设计一个
class Employee{
List peer;
Employee manager;
Employee(){
peer = new ArrayList();
manager = null;
}
}
总共实现三五个函数
boolean is_manager(employee a, employee b){
while(b != null){
if(a == b.manager) return true;
b = b.manager;
}
return false;
}
void add_peer(employee a, employee b){
a.peer.add(b)且a的peer里的每一个元素的peer都要add b
对b做同样的操作
把a和b的manager设为相同（面官当时已经说了给出的信息假设是正确的，不
用考虑互相违背的信息)
}
void add_manager(emploee a, employee b){
b.manager = a;
}
boolean is_peer(employee a, employee b){
return a.peer.contains(b);
}
大概是这样，加油啦

c*m2016-01-29 08:01

3 楼

楼主题目没有描述清楚，看完你的解答才明白完整的题意是什么。我感觉更好的答案是
并查集和树的结合。peer用并查集表示（一个集合里面的都是peer），manager关系用
树的结构表示。构建过程中先用(manager,A,B)先构建树结构;然后再用(peer,A,C)构建
并查集结构（在树中有父结点的是并查集的root）。is_peer(a,b)要么a,b在一个并查
集中，要么两个所属的并查集有相同的manager。is_manager(a,b)就递归地找了。自己
写的测试用例过了，如有不对请指正
class People:
def __init__(self, name):
self.name = name
#parent in tree to represent employee-manager info,
#tree_parent is manager of this person
self.tree_parent = None
#parent in union-find group
self.uf_parent = None
class RelationManager:
def __init__(self):
self.name_people_map = {}
def constructManagerTree(self, relations):
#1. sort relations to make (manager, a, b) relations before (peer, a
, b) relations
relations.sort()
#2. construct relations
for relation in relations:
if relation[0] == 'manager':
#1. use (manager, a, b) to construct employee-manager tree
manager_name = relation[1]
if manager_name not in self.name_people_map:
self.name_people_map[manager_name] = People(manager_name)
employee_name = relation[2]
if employee_name not in self.name_people_map:
self.name_people_map[employee_name] = People(employee_
name)
manager = self.name_people_map[manager_name]
employee = self.name_people_map[employee_name]
employee.tree_parent = manager
else:
#2. use (peer, a, b) to contruct union-find group
name1 = relation[1]
name2 = relation[2]
if name1 not in self.name_people_map:
self.name_people_map[name1] = People(name1)
if name2 not in self.name_people_map:
self.name_people_map[name2] = People(name2)
p1 = self.name_people_map[name1]
p2 = self.name_people_map[name2]
#union find
p1_uf_parent = self.find(p1)
p2_uf_parent = self.find(p2)
self.union(p1_uf_parent, p2_uf_parent)

def find(self, p1):
while p1.uf_parent:
p1 = p1.uf_parent
return p1
def union(self, p1, p2):
if p1 == p2:
return
#set p1 as that with not-None tree_parent if possible
if p2.tree_parent != None:
p1, p2 = p2, p1
#union
p2.uf_parent = p1
def is_peer(self, name1, name2):
#find parent of the union-find groups for name1, name2, compare
if name1 not in self.name_people_map or name2 not in self.name_
people_map:
return False
p1 = self.name_people_map[name1]
p2 = self.name_people_map[name2]
#find peer root
p1_uf_parent = self.find(p1)
p2_uf_parent = self.find(p2)
if p1_uf_parent == p2_uf_parent:
#same peer group
return True
else:
#two different peer groups but the two groups have the same
parent
if not p1_uf_parent.tree_parent or not p2_uf_parent.tree_parent:
return False
return p1_uf_parent.tree_parent == p2_uf_parent.tree_parent
def is_manager(self, manager_name, employee_name):
if manager_name not in self.name_people_map or employee_name not in
self.name_people_map:
return False
employee = self.name_people_map[employee_name]
manager = self.name_people_map[manager_name]
#recursive find all manager for employee, and return True if manager
is found in the way
p = employee
while p:
#find root to peers
peer_root = self.find(p)
#get manager for the peer group
if peer_root.tree_parent == manager:
return True
#recursively to find higher level manager
p = peer_root.tree_parent
#return False
return False

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

: 这题是我发的嘛，但我不是大牛,我只是一个还没工作的学生。。。
: 面挂了以后我本来是已经感累不爱了不想参加任何google的题的讨论了，看你这么执着
: 发了3个地方的问，我还是说一下我那会的做法
: 加油！你会拿下google的！
: 这个题不难，就是有一点点绕
: 我最直接的想法是并查集，很容易返回is_manager。但是并查集无法给出is_peer
: 所以设计一个
: class Employee{
: List peer;
: Employee manager;

n*n2016-01-29 08:01

4 楼

is_peer(a,b)要么a,b在一个并查集中，要么两个所属的并查集有相同的manager。
<<find那种找root。

【在 c*****m 的大作中提到】

: 楼主题目没有描述清楚，看完你的解答才明白完整的题意是什么。我感觉更好的答案是
: 并查集和树的结合。peer用并查集表示（一个集合里面的都是peer），manager关系用
: 树的结构表示。构建过程中先用(manager,A,B)先构建树结构;然后再用(peer,A,C)构建
: 并查集结构（在树中有父结点的是并查集的root）。is_peer(a,b)要么a,b在一个并查
: 集中，要么两个所属的并查集有相同的manager。is_manager(a,b)就递归地找了。自己
: 写的测试用例过了，如有不对请指正
: class People:
: def __init__(self, name):
: self.name = name
: #parent in tree to represent employee-manager info,

n*n2016-01-29 08:01

5 楼

如果我们先处理manager关系，这个list就不需要了，所以的peer这个list都一样，是
冗余。处理peer关系的时候用peer的manager更新自己的manager。

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

c*m2016-01-29 08:01

6 楼

我这里同一个集合都是peers,union-find找到的root是一个peer group中的root

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

:
: 如果我们先处理manager关系，这个list就不需要了，所以的peer这个list都一样，是
: 冗余。处理peer关系的时候用peer的manager更新自己的manager。