一亩三分地论坛

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

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

Google 电面面经,一结束马上来发,求爆人品!

[复制链接] |试试Instant~ |关注本帖
chenyy0527 发表于 2015-7-8 05:58:53 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Google - 猎头 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
新鲜Google面经来啦!. Waral 鍗氬鏈夋洿澶氭枃绔,
. 1point3acres.com/bbs
电面, 三个问题:
1. array, 找一个point,两边总和相等, 很简单,要注意负数情况
2. 要从server A 到 server B 备份很大的文件,网速很慢,文件改动很小
              我开始说用 log 反更新,面试官说OK,然后又说如果不能用log呢?然后我就不懂了
3. multi thread 的程序,基本能理解程序(不是我熟悉的语言,但我觉得是GO),但是因为没学过这个领域,还是有卡住的地方,如果拿分的话算30-40%吧.1point3acres缃

面试官人挺好的

评分

6

查看全部评分

dmsehuang 发表于 2015-7-9 01:03:41 | 显示全部楼层
chenyy0527 发表于 2015-7-8 07:16
Two passes 是什么?
我是检测第一个element,然后遍历剩下的,每次对比一加一减就可以。都是O(n)

哦哦,原来是给test cases看输出结果啊,那还是看你对于代码的理解。谢谢楼主
回复 支持 1 反对 0

使用道具 举报

adiggo 发表于 2015-7-8 07:08:16 | 显示全部楼层
楼主 第二题感觉是使用rsync。
回复 支持 反对

使用道具 举报

dmsehuang 发表于 2015-7-8 07:09:39 | 显示全部楼层
谢谢楼主,第一题o(n)解法two passes可以吗?
回复 支持 反对

使用道具 举报

dmsehuang 发表于 2015-7-8 07:11:08 | 显示全部楼层
还有就是multi-thread那个是给你一段代码,然后让你理解程序要做什么?
回复 支持 反对

使用道具 举报

 楼主| chenyy0527 发表于 2015-7-8 07:16:35 来自手机 | 显示全部楼层
dmsehuang 发表于 2015-7-8 07:09. more info on 1point3acres.com
谢谢楼主,第一题o(n)解法two passes可以吗?

Two passes 是什么?
我是检测第一个element,然后遍历剩下的,每次对比一加一减就可以。都是O(n)

后面那题要我理解程序是问我test case ,看会出现哪几种情况,会输出什么东西

主要是我对平行运算完全不熟所以。。。
. visit 1point3acres.com for more.
不知道他们对于这种只能写代码的怎么评定
回复 支持 反对

使用道具 举报

 楼主| chenyy0527 发表于 2015-7-8 07:17:45 来自手机 | 显示全部楼层
adiggo 发表于 2015-7-8 07:08
楼主 第二题感觉是使用rsync。

T.T 那是哪个领域的知识?我该去哪里补类?
回复 支持 反对

使用道具 举报

 楼主| chenyy0527 发表于 2015-7-8 07:18:46 来自手机 | 显示全部楼层
adiggo 发表于 2015-7-8 07:08. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
楼主 第二题感觉是使用rsync。

T.T 那是哪个领域的知识?我该去哪里补类?
回复 支持 反对

使用道具 举报

adiggo 发表于 2015-7-8 07:31:05 | 显示全部楼层
chenyy0527 发表于 2015-7-8 07:17
T.T 那是哪个领域的知识?我该去哪里补类?

rsync 是一个unix command, 很多backup是基于它的。他使用了delta-transfer algorithm, 因为两个file 差别很少, 所以使用它比较合适。
回复 支持 反对

使用道具 举报

handsomecool 发表于 2015-7-8 09:08:53 | 显示全部楼层
第一题two pointers最简单吧,前后逐渐往中心靠近,两边各一个sum, 每次哪边小就哪边前进一位,直到两边见面。
回复 支持 反对

使用道具 举报

larry_cn 发表于 2015-7-8 09:53:06 | 显示全部楼层
第二个问题 主要思想 应该是 对文件 partition(partition的 办法可以有 很多种) 分成多个fragment
因为 改动较小 所有 大部分 fragment 就没有改变 然后 处理 改动的 部分就好了
回复 支持 反对

使用道具 举报

 楼主| chenyy0527 发表于 2015-7-8 10:27:48 来自手机 | 显示全部楼层
handsomecool 发表于 2015-7-8 09:08
第一题two pointers最简单吧,前后逐渐往中心靠近,两边各一个sum, 每次哪边小就哪边前进一位,直到两边见 ...

我刚开始也是想到这个。但是这个负数的情况是用不了的
回复 支持 反对

使用道具 举报

maxnima 发表于 2015-7-8 10:35:09 | 显示全部楼层
赞,祝楼主拿到onsite
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-8 12:00:09 | 显示全部楼层
chenyy0527 发表于 2015-7-8 07:16.1point3acres缃
Two passes 是什么?. visit 1point3acres.com for more.
我是检测第一个element,然后遍历剩下的,每次对比一加一减就可以。都是O(n)

我想楼上说的Two passes可能是指:第一遍先得到所有的元素的和S;第二遍过的时候,如果某个元素A的左边的和S[0, i-1]恰好等于总和(S-A)/2,则 i 就是所求的切分点(希望没有理解错题意)。

楼主说的这段:“检测第一个element,遍历剩下的,每次对比一加一减”我没太看懂。能否说得再详细一点?
. 鍥磋鎴戜滑@1point 3 acres
补充内容 (2015-7-8 12:01):
原文中的A是A[ i ]. 万恶的斜体格式控制符……
回复 支持 反对

使用道具 举报

 楼主| chenyy0527 发表于 2015-7-8 12:24:24 来自手机 | 显示全部楼层
maxnima 发表于 2015-7-8 10:35
赞,祝楼主拿到onsite

谢谢哦!!感动
回复 支持 反对

使用道具 举报

 楼主| chenyy0527 发表于 2015-7-8 12:28:13 来自手机 | 显示全部楼层
stellari 发表于 2015-7-8 12:00
我想楼上说的Two passes可能是指:第一遍先得到所有的元素的和S;第二遍过的时候,如果某个元素A的左边的 ...
. 1point3acres.com/bbs
哦,可以的!
我的方法也是类似。就是对于A[0]检测所有两边的和(当然左边没东西),然后不等的话,检测下一个,左边的和是加上之前的元素,右边的和是减去右边的元素。(这是我所谓的一加一减)

然后一直对比直到找到
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-8 12:33:01 | 显示全部楼层
chenyy0527 发表于 2015-7-8 12:28
哦,可以的!
我的方法也是类似。就是对于A[0]检测所有两边的和(当然左边没东西),然后不等的话,检测 ...

明白了。不过这样的话不也是需要预先算出右边元素的和么?那最后其实也是two pass吧?
回复 支持 反对

使用道具 举报

 楼主| chenyy0527 发表于 2015-7-8 12:35:06 来自手机 | 显示全部楼层
stellari 发表于 2015-7-8 12:33
明白了。不过这样的话不也是需要预先算出右边元素的和么?那最后其实也是two pass吧?

是的,所以很类似的。我一开始没理解two passes o.o
回复 支持 反对

使用道具 举报

 楼主| chenyy0527 发表于 2015-7-8 12:37:22 来自手机 | 显示全部楼层
stellari 发表于 2015-7-8 12:33. 1point 3acres 璁哄潧
明白了。不过这样的话不也是需要预先算出右边元素的和么?那最后其实也是two pass吧?

不过,你那个方法直接对比会有一点点问题,因为他要求【1,2,3】这种case不可以的,因为返回的坐标对应的元素要求两边都算,所以对比前要先把当前坐标再加一遍
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-8 13:49:36 | 显示全部楼层
chenyy0527 发表于 2015-7-8 12:37. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
不过,你那个方法直接对比会有一点点问题,因为他要求【1,2,3】这种case不可以的,因为返回的坐标对应 ...

我理解你的意思。但是不一定要“再加一遍”;“减一遍”也是可以的。因为“返回的坐标上的元素必须包含在左右两边”和“返回的元素必须不包含在任意一边”这两者无论是哪种情况,均不会影响本题的结果。我选择的是后者,即“把返回的元素从S中减掉”。所以,我说的那种方法也是不认可[1,2,3]的。
回复 支持 反对

使用道具 举报

handsomecool 发表于 2015-7-8 14:07:20 | 显示全部楼层
chenyy0527 发表于 2015-7-8 10:27
我刚开始也是想到这个。但是这个负数的情况是用不了的

还有负数哦,那改一下还是可以吧,依旧two pointers,两边哪边挪动的判定方式改一下:

这回不记左右两个sum了,两边加起来变一个sum, 但是把右边的正负号颠倒。 然后根据sum来看两边下一位取哪边的, 比如:   -5, -3, -1, -3, -7, -2

一开始sum = -5 + -(-2) = -3, 下一位两边一边是-3,一边是-(-7) = 7,那就右边挪。
现在sum = -3+7 = 4, 左边挪。. from: 1point3acres.com/bbs
sum = 4 - 3 = 1
继续左边挪,sum = 1-1 = 0, 停止。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 05:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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