一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1522|回复: 9
收起左侧

[找工就业] G家 phone面 求大牛分析

[复制链接] |试试Instant~ |关注本帖
loganecolss 发表于 2016-9-28 17:31:16 | 显示全部楼层 |阅读模式

2016(10-12月)-[]CS硕士+3-5年 - 网上海投| 码农类全职@Google其他

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
已跪,求大牛分析一下。
问了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解法...
. 1point 3acres 璁哄潧

本帖被以下淘专辑推荐:

hxtang 发表于 2016-9-28 23:24:09 | 显示全部楼层
第一题只要按照年龄排序的有序结构,加可以任意按name删元素。所以基本上就是LRU cache。只是evict的element不会添加到队尾。这个问题的插入是有序的(晚插入的年龄小),如果用heap太慢了。
第二题可以为每个parent存一个local的LRU状的孩子列表,为每个孩子存一下parent的name。
回复 支持 2 反对 0

使用道具 举报

singku 发表于 2016-9-28 21:26:28 | 显示全部楼层
第一题可以用list存成员+hashmap存iterator 出生就加在list之前,去世就从hashmap中找到iter 从list中删掉,年长就是list的back。空间on 其他都是o1
回复 支持 反对

使用道具 举报

qsort 发表于 2016-9-28 22:56:22 | 显示全部楼层
class FamilyMember {
回复 支持 反对

使用道具 举报

leixiang5 发表于 2016-9-28 23:03:06 | 显示全部楼层
感觉lru的data strcture的组合解决?
回复 支持 反对

使用道具 举报

 楼主| loganecolss 发表于 2016-9-29 10:36:09 来自手机 | 显示全部楼层
hxtang 发表于 2016-9-28 23:24
第一题只要按照年龄排序的有序结构,加可以任意按name删元素。所以基本上就是LRU cache。只是evict的elemen ...

确实,谢大牛。
实在太弱了,滚一边去复习了
回复 支持 反对

使用道具 举报

cicean 发表于 2016-9-30 14:28:42 | 显示全部楼层
为什么我考的都是棋盘类游戏,这么难……哭了快
回复 支持 反对

使用道具 举报

 楼主| loganecolss 发表于 2016-9-30 14:53:39 来自手机 | 显示全部楼层
cicean 发表于 2016-9-30 14:28
为什么我考的都是棋盘类游戏,这么难……哭了快
. From 1point 3acres bbs
题目具体说说?
回复 支持 反对

使用道具 举报

dokolo 发表于 2016-10-1 01:02:39 | 显示全部楼层
第一题就是LRU Cache
第二题也是这个思路,一个Node里保存这个人的parent和children,当一个成员去世的时候,从hashtable和双向链表里删除这个节点,同时在其parent节点里删除自己...
感觉难点在Node的parent结构... 要做到返回长子和popChild都是O(1),不知道有没有LinkedHashmap以外的结构可以做到...
回复 支持 反对

使用道具 举报

 楼主| loganecolss 发表于 2016-10-3 08:45:38 | 显示全部楼层
dokolo 发表于 2016-10-1 01:02
第一题就是LRU Cache
第二题也是这个思路,一个Node里保存这个人的parent和children,当一个成员去世的时 ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
唉,我太弱了,没有反应过来,压根就没有往lru那方面想...
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 23:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表