美本CS文理学院和工程院的区别

一亩三分地

 找回密码 注册账号

扫描二维码登录本站

最近看过此主题的会员


码农求职神器Triplebyte
不用海投
内推多家公司面试

Total Comp Calculator
输入offer信息
系统自动计算每年收入

科技公司如何
用数据分析驱动产品开发
coupon code: 20%off 打八折

深入浅出AB Test
从入门到精通
coupon code: 20%off 打八折
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
查看: 5113|回复: 24
收起左侧

G 面经+加面

[复制链接] |试试Instant~
我的人缘0

分享帖子到朋友圈
fubu 发表于 2016-12-2 16:14:34 | 显示全部楼层 |阅读模式
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (14)
 
 
0% (0)    👎

2016(10-12月) 码农类General 硕士 全职@Google - 内推 - Onsite  | Other | 在职跳槽

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

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

x
1.      Inbox team的年轻白人
类似LC361, enemy变成light,求光线最强值;
follow up1:light的光有范围,e.g.超过两格会消失. Solution:分别算出left,right,up,down,用queue store行列上的光照范围
follow up2:每盏light范围不一样肿么办,用PriorityQueue代替Queue
2.      Design 年轻白人
Telescope system on moon, 有100 telescopes, 天文学家可以用它们拍照观测,每个观测任务可能会要couple hours
和地球通信只能用radio signal,latency会很高;设计系统manage Telescopes, 要fault tolerant,任务调度,deploy update
思路:类似long distance data center的manage, moon上多台app server负责控制telescope,每台server会与地球的master用radio作为heartbeat通信;
如何deployupdate时,选一台active server发送file,然后分chunk,在moon上peer to peer的用gossip传播update
3.      很nice的中国大哥
给一个矩阵,起点左上角,终点右下角,只能上下左右,要求返回一条由起点至终点的随机路径,每一步的方向选择必须随机;不能走重复的
思路:dfs,每一步拿到ava
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
licate id是取average,而且输出还是要sorted by value,
思路:用map,给出two pass NlgN做法,不满意要求onepass;
用binary search的话,因为arraylist 会移动elements,复杂度不理想; linkedlist需要scan才能拿到对应index的element 还是不理想;最后面试官说他是有one-pass NlgN做法的


回报地里,跪求G的offer~~



补充内容 (2016-12-10 15:20):
收到offer了

评分

参与人数 2大米 +73 收起 理由
mmliu + 3 感谢分享!
candy_shmily + 70

查看全部评分


上一篇:Quora OA 跪经 Changing Managers
下一篇:今天收到亚麻的oa1

本帖被以下淘专辑推荐:

我的人缘0
 楼主| fubu 发表于 2016-12-3 01:52:07 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (14)
 
 
0% (0)    👎
zyoppy008 发表于 2016-12-2 16:44
不懂你第一题follow up的做法 为啥那样做 直接拿个count计左边的长度 知道左右加起来的和 就可以求右边的长 ...

followup1:你说的很接近,不过细节上,例如算left光亮值时,从左到右scan,每遇到light时,把colulmn Index + 光照range 塞入Queue中,每移动一格,倒要check 当前col index > queue.peek() ,如果是的话,要pop,之后left 光照强度 就等于queue.size()了;然后right up down都一样的做法

followup2:每盏灯range不同,就不能塞到queue里面了,因为后面来的灯有可能先弹出;需要把colulmn Index + 光照range 塞到priority queue里
回复

使用道具 举报

我的人缘0
zyoppy008 发表于 2016-12-2 16:44:52 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   91% (61)
 
 
8% (6)    👎
不懂你第一题follow up的做法 为啥那样做 直接拿个count计左边的
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
follow up 2呢
回复

使用道具 举报

我的人缘0
zyoppy008 发表于 2016-12-2 17:25:28 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   91% (61)
 
 
8% (6)    👎
Treemap
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
ap啊
回复

使用道具 举报

我的人缘0
2008 发表于 2016-12-2 21:25:12 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (4)
 
 
0% (0)    👎
2.      在工作10多年的老白男
一个class Node {int id, int val},
两个Node list, List<Node> n1, List<Node> n2, n1,n2是按val 排序的,且n1,n2各自id没有duplicate, 但n1 n2 之间可能存在duplicate
写merge(n1, n2) 类似merge two sorted list, 但是发现id duplicate就只取其中一个,用Set就搞定了
Followup:这才是真正的题目,duplicate id是取average,而且输出还是要sorted by value,
思路:用map,给出two pass NlgN做法,不满意要求onepass;
用binary search的话,因为arraylist 会移动elements,复杂度不理想; linkedlist需要scan才能拿到对应index的element 还是不理想;最后面试官说他是有one-pass NlgN做法的


这题用map+list可解,类似lru cache,如果有dup  id,找到list节点,一路冒泡swap过去就好了。
回复

使用道具 举报

我的人缘0
mmliu 发表于 2016-12-2 22:19:25 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   87% (21)
 
 
12% (3)    👎
同问第一题 没太 get 到用 queue 和 PriorityQueue 的原因在哪儿,我的理解,不是建一个 matrix,然后遍历每个元素,对 每个发光的点的四周做 +1 操作不就 OK 了么,不知道我理解的对不对
-baidu 1point3acres
<
游客,本帖隐藏的内容需要积分高于 10 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
1也不需要了,直接利用Queue中的元素size,即可获知当前的光照址,O(1)
回复

使用道具 举报

我的人缘0
mmliu 发表于 2016-12-2 22:44:46 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   87% (21)
 
 
12% (3)    👎
2008 发表于 2016-12-2 21:25
这题用map+list可解,类似lru cache,如果有dup  id,找到list节点,一路冒泡swap过去就好了。
. 1point3acres
双向链表 + Map ?
回复

使用道具 举报

我的人缘0
2008 发表于 2016-12-2 23:47:47 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (4)
 
 
0% (0)    👎
mmliu 发表于 2016-12-2 22:44
双向链表 + Map ?

对,
map: id=>list iterator
doubly linked list: struct(id, value, count)

when add new <id, value> check map first,
if does not have, append list, then insert map;
if has, find list node, update value, (count*oldValue+ newValue)/(count+1), then swap with left node or right node until the value are sorted again.
回复

使用道具 举报

我的人缘0
zyoppy008 发表于 2016-12-3 01:18:42 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   91% (61)
 
 
8% (6)    👎
2008 发表于 2016-12-2 23:47
对,. 1point3acres
map: id=&gt;list iterator
doubly linked list: struct(id, value, count)

你这复杂度根本就不行 楼主说了
回复

使用道具 举报

我的人缘0
 楼主| fubu 发表于 2016-12-3 01:59:39 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (14)
 
 
0% (0)    👎
2008 发表于 2016-12-2 23:47
对,
map: id=>list iterator
doubly linked list: struct(id, value, count)

我当时也试图用LRU类似做法,然而lru,每个node都是插入到tail,每次操作可以O(1); 这个要先判断插入位置,无论用arraylist还是linkedlist都比较蛋疼
也试图维护一个binary search tree(treemap类似的),不过因为输入merge为list,这样还是算two-pass吧,不清楚
回复

使用道具 举报

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

本版积分规则

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

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

手机版|小黑屋|一亩三分地

GMT+8, 2019-6-24 16:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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