一亩三分地论坛

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

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

Google电面

[复制链接] |试试Instant~ |关注本帖
wwjk2003 发表于 2015-11-13 06:54:50 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Google - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
刚面的google电面,面的应该是国人,不知道是信号不好还是什么原因听的都不是很清楚,但是把我名字念准了,可能是免提?看了下简历,没有问什么,问了一下情况,选的SDE还是SETI,然后做题。
第一题 ADD ONE。 简单讲了一下写了一下程序就过了。
第二题,说给一个array,然后调一些加到新的array,头尾必须要,然后给你个条件,新的array里的2个元素之间差别尽可能接近10。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
LZ之前都在看其他题一看这题傻了,感觉只能brute force啊。。然后就写了个程序,时间也差不多到了,随便问了2个问题就结束了。
求RP,求ONSITE。
lcl3356897 发表于 2015-11-13 07:30:23 | 显示全部楼层
楼主加油
. from: 1point3acres.com/bbs
两个元素之间差别接近10是大小接近10么?
回复 支持 反对

使用道具 举报

SophieCheng 发表于 2015-11-13 07:36:14 | 显示全部楼层
lz,第二道题中,是在一个sorted array 挑给定数目的元素?新的array里面是相邻两个之间满足接近10么?
回复 支持 反对

使用道具 举报

天空无语 发表于 2015-11-13 08:00:44 | 显示全部楼层
楼主你电面前有没有收到一封邮件要做short survey and coding sample?
回复 支持 反对

使用道具 举报

swly 发表于 2015-11-13 08:04:28 | 显示全部楼层
第二题没看懂,是说重新排一遍还是挑一些出来,lz可以讲讲么
回复 支持 反对

使用道具 举报

 楼主| wwjk2003 发表于 2015-11-13 14:03:55 | 显示全部楼层
lcl3356897 发表于 2015-11-13 07:30
楼主加油. 1point 3acres 璁哄潧

两个元素之间差别接近10是大小接近10么?

对 就是第一个数组里挑出来的元素放到新数组里 并且使他们的差值减10的绝对值最小
回复 支持 反对

使用道具 举报

 楼主| wwjk2003 发表于 2015-11-13 14:04:47 | 显示全部楼层
SophieCheng 发表于 2015-11-13 07:36
lz,第二道题中,是在一个sorted array 挑给定数目的元素?新的array里面是相邻两个之间满足接近10么?
. more info on 1point3acres.com
对 给一个sorted array 比如[0 9 15 20 30]
那你新数组就返回[0 9 20 30]就行了
回复 支持 反对

使用道具 举报

 楼主| wwjk2003 发表于 2015-11-13 14:05:20 | 显示全部楼层
天空无语 发表于 2015-11-13 08:00
楼主你电面前有没有收到一封邮件要做short survey and coding sample?

有做过一个short survey 之前还有一个non-technical phone interview 问问简历什么的。
回复 支持 反对

使用道具 举报

 楼主| wwjk2003 发表于 2015-11-13 14:06:00 | 显示全部楼层
swly 发表于 2015-11-13 08:04. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
第二题没看懂,是说重新排一遍还是挑一些出来,lz可以讲讲么

是挑出来比如给你[0 9 15 21 30]
你返回[0 9 21 30]
回复 支持 反对

使用道具 举报

maomaoxiong 发表于 2015-11-13 14:38:35 | 显示全部楼层
最后一题:s[i]为包含i的最小sum。检查之前0-》i-1的序列的最后一个值和A[i]的差。选最小的。. From 1point 3acres bbs
类似DP题。

.1point3acres缃

回复 支持 反对

使用道具 举报

肖邦的眼泪 发表于 2015-11-13 14:50:44 | 显示全部楼层
大概是这么个意思吧,首先确定首尾,这是给定的。
然后按照需要的数目,找出边界点,比如首尾是[0,  30], say 我们需要总长度是4, 那么也就是还差两个数,那么完美的情况就是:[0,10,20,30]-google 1point3acres
然后binary search 10 和20找出最接近的数。
回复 支持 反对

使用道具 举报

xiaoniuona 发表于 2015-11-14 10:12:39 | 显示全部楼层
楼主第二题返回数组的长度是给定的嚒?
回复 支持 反对

使用道具 举报

 楼主| wwjk2003 发表于 2015-11-14 14:21:57 | 显示全部楼层
xiaoniuona 发表于 2015-11-14 10:12
楼主第二题返回数组的长度是给定的嚒?

没给定 只要满足相邻相差接近10就行 收尾给定了
回复 支持 反对

使用道具 举报

liranxixi 发表于 2015-11-15 07:48:17 | 显示全部楼层
天空无语 发表于 2015-11-13 08:00
楼主你电面前有没有收到一封邮件要做short survey and coding sample?
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
我有收到那个还纳闷呢!
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-8 08:44:56 | 显示全部楼层
第二题是用dp吗?每次看加入或者或者不加入一个数,然后哪个更小?
回复 支持 反对

使用道具 举报

cx00001 发表于 2016-3-16 02:20:18 | 显示全部楼层
第二题的暴力解是2^n次方吧
dp的思路是 用dp数组纪录当前之前的最小差值和,用一个memo去记录从哪儿来,状态转移方程:
dp[i]=min(dp[i-k]+abs(abs(nums[i]-nums[i-k])-10)) k<=i
memo = argsmin(dp[i-k]+abs(abs(nums[i]-nums[i-k])-10)) k<=10
这是n^2的复杂度

应该有地方可以优化状态转移方程 初步想法是加多一个数组,记录每一步用了的多少个元素, k最多到比i-1记录的个数小一的位置,但这样做并没有降低复杂度
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-4-1 03:32:11 | 显示全部楼层
第二题面试官有给什么hint吗?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 18:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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