一亩三分地论坛

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

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

G家面筋

[复制链接] |试试Instant~ |关注本帖
feigou 发表于 2015-9-27 14:50:51 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 博士 全职@Google - 内推 - Onsite |Other在职跳槽

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

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

x
没有一轮国人,过程感觉也没有很亲切,看来还是要中国人多才好。九月初的onsite,
一共五轮,四轮coding一轮系统设计(第一轮)
1. billion级别的raw data,怎样村在多个节点中,实现有效率的查找。给定条件是数
据是已经在那里的,而且不会被修改。.鏈枃鍘熷垱鑷1point3acres璁哄潧
2. valid bst讨论属性,边界条件. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
3. 给一个排序的数组, 1 2 5 8 9 11 16,输出missing range比如3-4,6-7,10,
12-15
4. iterator of iterator,写一个iterator iterate所有的元素,例如
itr1   1  2   3   4
itr2   5  6   7   8
itr3   9  10 11 12
写一个iterator输出1 5 9 2 6 10 ...
5. 类似moving average,固定size不断update average,讨论多县城的情况。

本帖被以下淘专辑推荐:

wenqiang88 发表于 2015-9-27 19:45:10 | 显示全部楼层
cjlm007 发表于 2015-9-27 15:37
说一下第一题思路,每个子节点存一段sorted array然后具体范围存在master里面。这样master节点就可以维护一 ...

同意LS的思路。可以先说下怎么external merge sort
回复 支持 1 反对 0

使用道具 举报

darkwowgamer 发表于 2015-9-27 14:58:57 | 显示全部楼层
1, 5有什么思路呢?
回复 支持 1 反对 0

使用道具 举报

kelvinzhong 发表于 2015-9-27 14:59:33 | 显示全部楼层
楼主4轮coding每轮都只需要了一题吗?那空余时间都是在讨论简历吗?
回复 支持 反对

使用道具 举报

cjlm007 发表于 2015-9-27 15:37:41 | 显示全部楼层
说一下第一题思路,每个子节点存一段sorted array然后具体范围存在master里面。这样master节点就可以维护一个区间树,查询的时候用值来查询某一个机器id (logN)。到具体机器后直接binary search (logM)内容。. visit 1point3acres.com for more.

这么说还是太简单了,楼主麻烦问一下面试官又问一些其他的问题吗?谢谢
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-9-27 21:36:56 | 显示全部楼层
cjlm007 发表于 2015-9-27 15:37
说一下第一题思路,每个子节点存一段sorted array然后具体范围存在master里面。这样master节点就可以维护一 ...

楼主所谓的查询是什么查询?好像没说清....是只看某个数在不在?
回复 支持 反对

使用道具 举报

leixiang5 发表于 2015-9-27 23:22:47 | 显示全部楼层
onsite每一回合都只问一道题目吗?
回复 支持 反对

使用道具 举报

ww55201 发表于 2015-9-28 00:36:59 | 显示全部楼层
楼主能详细说下1,5题不,跪谢
回复 支持 反对

使用道具 举报

will_ym 发表于 2015-9-28 00:50:33 | 显示全部楼层
同问第一题和第五题
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-9-28 00:52:26 来自手机 | 显示全部楼层
第五题是维护一个start, 一个sum,然后for 循环。当i大于等于size的时候,就要减去A在start的值,加上现在的值。求平方存入结果array 吧?
-google 1point3acres
补充内容 (2015-9-28 05:13):
求平均
回复 支持 反对

使用道具 举报

海岸线 发表于 2015-9-28 02:03:23 | 显示全部楼层
第五题是不是用circular array。多线程下加锁。
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-9-28 05:23:34 | 显示全部楼层
bobzhang2004 发表于 2015-9-28 00:52
第五题是维护一个start, 一个sum,然后for 循环。当i大于等于size的时候,就要减去A在start的值,加上现在的 ...

第五题可以参考http://rosettacode.org/wiki/Averages/Simple_moving_average
如果是stream的话,就应该维持一个window,一个sum,超过window size的话,sum - 最前面的那个 + 现在的值
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-28 08:12:06 | 显示全部楼层
bobzhang2004 发表于 2015-9-28 05:23
第五题可以参考http://rosettacode.org/wiki/Averages/Simple_moving_average
如果是stream的话,就应该 ...

厉害!~~~
回复 支持 反对

使用道具 举报

mikegrup 发表于 2015-9-28 09:58:07 | 显示全部楼层
海岸线 发表于 2015-9-28 02:03 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
第五题是不是用circular array。多线程下加锁。
. 鍥磋鎴戜滑@1point 3 acres
恩, 用双向queue也可以,poll最前面的,add到最后面. 多线程锁怎么弄?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 02:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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