登录
  • #码农类general
  • #google
  • #工作信息
  • #求职
  • #找工就业

G家 phone面 求大牛分析

loganecolss
2837
9
已跪,求大牛分析一下。

问了1个题目,讲思路,然后code,然后问了个follow-up。

类似family tree一样的东西,有如下几个接口函数要实现,大概意思是这样的:

class Family:

init(name) # 初始化一个family, name是第一个出生的成员的名称, btw 所有成员的name不会重

birth(name) # 一个成员出生,name是名字

die(name) # 一个成员去世

getRoot() # 后去family中最年长的成员name

我弱渣了,开始想了个基于数组的解法 birth/die O(1), 但是getRoot O(n); 不满意,继续想,给了个基于heap的解法 birth/die O(logn), getRoot O(1)。至此已过去10min~~(弱成🐶了...)

小哥说,是否还有更好的解法,想了下,说没了,然后开始code了。

看还有时间,问了个follow-up:

将上面的birth改一下,成了这样,

birth(parent, name); # 每个birth都会给parent的名字(parent一定是还没有die的)

getRoot() # 首先看最年长的成员是否还有孩子活着(一定要是孩子,不是孙子,重孙子...), 若是 返回最年长的孩子, 若否 返回自己就可以。

我就着上面heap的思路想了想,说还是做一个heap保存活着的所有成员,然后再做个map,以parent 做key, value是个链表依次是最年长的孩子到最年幼的孩子blabla

以上了,求各位大牛分析分析更好的解法

p.s. 感觉自己太弱,第一问居然没有瞬间想到heap解法...
9条回复
热度排序

发表回复