我是如何肉身翻墙,从国内直接来美国工作的?

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
查看: 2364|回复: 9
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
我的人缘0
loganecolss 发表于 2016-9-28 17:31:16 | 显示全部楼层 |阅读模式
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】

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

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

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

x
已跪,求大牛分析一下。
问了1个题目,讲思路,然后code,然后问了个follow-up。

类似family tree一样的东西,有如下几个接口函数要实现,大概意思是这样的:
class Family:
  init(name)   # 初始化一个family, name是第一个出生的成员的名称, btw 所有成员的name不会重
  birth(name) # 一个成员出生,name是名字
  die(name)   # 一个成员去世
  getRoot()    # 后去family中最年长的成员name. visit 1point3acres for more.

我弱渣了,开始想了个基于数组的解法 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()    # 首先看最年长的成员是否还有孩子活着(一定要是孩子,不是孙子,重孙子...), 若是 返回最年长的孩子, 若否 返回自己就可以。.1point3acres网
. visit 1point3acres for more.
我就着上面heap的思路想了想,说还是做一个heap保存活着的所有成员,然后再做个map,以parent 做key, value是个链表依次是最年长的孩子到最年幼的孩子blabla

以上了,求各位大牛分析分析更好的解法
p.s. 感觉自己太弱,第一问居然没有瞬间想到heap解法.... 1point 3acres 论坛


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

本帖被以下淘专辑推荐:

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

使用道具 举报

我的人缘0
singku 发表于 2016-9-28 21:26:28 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
第一题可以用list存成员+hashmap存iterator 出生就加在list之前,去世就从hashmap中找到iter 从list中删掉,年长就是list的back。空间on 其他都是o1
回复 支持 反对

使用道具 举报

我的人缘0
qsort 发表于 2016-9-28 22:56:22 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
class FamilyMember {
回复 支持 反对

使用道具 举报

我的人缘0
leixiang5 发表于 2016-9-28 23:03:06 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
感觉lru的data strcture的组合解决?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| loganecolss 发表于 2016-9-29 10:36:09 来自手机 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
hxtang 发表于 2016-9-28 23:24
第一题只要按照年龄排序的有序结构,加可以任意按name删元素。所以基本上就是LRU cache。只是evict的elemen ...

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

使用道具 举报

我的人缘0
cicean 发表于 2016-9-30 14:28:42 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
为什么我考的都是棋盘类游戏,这么难……哭了快
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| loganecolss 发表于 2016-9-30 14:53:39 来自手机 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
cicean 发表于 2016-9-30 14:28
为什么我考的都是棋盘类游戏,这么难……哭了快

题目具体说说?
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

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

使用道具 举报

我的人缘0
 楼主| loganecolss 发表于 2016-10-3 08:45:38 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
dokolo 发表于 2016-10-1 01:02
第一题就是LRU Cache
第二题也是这个思路,一个Node里保存这个人的parent和children,当一个成员去世的时 ...

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

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-28 18:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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