查看: 2942|回复: 9
收起左侧

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

|只看干货 |码农类general, 找工就业, google, 求职, 工作信息

分享帖子到朋友圈
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (2)
 
 
0% (0)    👎

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

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

您需要 登录 才可以下载或查看,没有帐号?注册账号

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解法...


上一篇:请问关于opt时间的计算问题!!
下一篇:已经过了google code challenge foobar, 是否现在联系recruiters

本帖被以下淘专辑推荐:

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

使用道具 举报

singku 2016-9-28 21:26:28 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (268)
 
 
1% (5)    👎
第一题可以用list存成员+hashmap存iterator 出生就加在list之前,去世就从hashmap中找到iter 从list中删掉,年长就是list的back。空间on 其他都是o1
回复

使用道具 举报

qsort 2016-9-28 22:56:22 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎
class FamilyMember {
回复

使用道具 举报

leixiang5 2016-9-28 23:03:06 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   89% (423)
 
 
10% (50)    👎
感觉lru的data strcture的组合解决?
回复

使用道具 举报

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

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

使用道具 举报

cicean 2016-9-30 14:28:42 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   81% (49)
 
 
18% (11)    👎
为什么我考的都是棋盘类游戏,这么难……哭了快
回复

使用道具 举报

 楼主| loganecolss 2016-9-30 14:53:39 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (2)
 
 
0% (0)    👎
cicean 发表于 2016-9-30 14:28
为什么我考的都是棋盘类游戏,这么难……哭了快

题目具体说说?
回复

使用道具 举报

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

使用道具 举报

 楼主| loganecolss 2016-10-3 08:45:38 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (2)
 
 
0% (0)    👎
dokolo 发表于 2016-10-1 01:02
第一题就是LRU Cache. 1point3acres
第二题也是这个思路,一个Node里保存这个人的parent和children,当一个成员去世的时 ...

唉,我太弱了,没有反应过来,压根就没有往lru那方面想...
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

X 关闭
>
快速回复 返回顶部 返回列表