一亩三分地论坛

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

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

谷歌2.3on campus实习面经【攒人品】

[复制链接] |试试Instant~ |关注本帖
面无表情 发表于 2016-2-4 12:29:20 | 显示全部楼层 |阅读模式

2017(1-3月) 码农类 硕士 实习@Google - 校园招聘会 - 校园招聘会 |Other其他

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

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

x
两个engineers连着面。谷狗不按套路出牌。. 1point 3acres 璁哄潧
第一个是国人小哥(还是我校友),结果出题一点也不放水嘤。先问x+log2(x) = 0,如何求x(浮点数),我直接懵逼了。经提醒,range在0~1之间,用维护range的二分法做,勉强做完,期间小哥一直善意地不停提醒,可是我还是感受到了智商碾压嘤……. 鍥磋鎴戜滑@1point 3 acres
然后第二题是给一个整数n例如5,它能被分成2+3,积是6,也能被分成1+4,积是4,求这个整数的最大可能积。一开始我又懵逼了,我猜是分成两个数最大,小哥说不对,你看8就不是分为4+4而是应该分为2+3+3,我又继续懵逼卡住。小哥又善意地提醒我可以遍历n的分法,每次用递归找最大积,例如,8可以分为1+7,2+6,3+5,4+4,可以依次询问1,2,3,4,5,6,7的最大积。这个用个简单的递归迭代就行。然后我一脸懵逼地大概把码写了,小哥善意地给我改了改,然后follow up:这个查询被询问了太多次,如何用一个数据结构保存以前的结果?然后我懵了一会儿开始想DP的递推式,小哥直接指出不用这样你用map就行了,然后时间就到了我就被赶出去了……. more info on 1point3acres.com

第二个是一个温柔的印度小哥,非常善意地聊了一会儿天,问了一点我的项目,然后开始做题,非常善意地给了一道unsorted array的find duplicate,任意的就行,我给了好几个办法,小哥会叫我分析每个办法的时间复杂度和空间复杂度,最后update question,数组的所有数字都在1~N的范围内,叫我在O(1)空间限制下,找一个比sort版本O(nlogn)时间更少的方法。然后我说可以尝试modify原数组,思维仍然卡在上一个hashmap的方法上面,然后小哥说能不能不modify原数组,仍然用hash的思维做,我就想啊想我觉得应该有index mapping才对,然而怎么也想不出O(1)空间的办法,小哥就提示我注意数字都在1~N范围内噢!!!然后我们一起列了几个例子分析了一下,最后发现还是一个range二分的思想,详情如下:
假设数组是3,2,1,3,6,5,4,共7个数,N=7
开始时left = 1, right = 7, mid = 4,数在left~mid范围内的数有几个,如果没有重复的话应该有mid-left个,此时走右边,如果有重复的话就会出现多于mid-left个的情况,那么应该走左边,分别相应update left,right和mid,直到最后找到重复数3。
然后我就在懵的状态下按照这个思路写了一下代码,小哥帮我指出了几个range上的问题。

我现在仍然有点懵,希望大家多多讨论,后续我就不抱太大希望了。大家都加油!


评分

3

查看全部评分

chentz 发表于 2016-2-6 05:53:36 | 显示全部楼层
第一题对较大的数的话应该要把它拆成尽可能多的3和不超过两个2吧。
回复 支持 反对

使用道具 举报

 楼主| 面无表情 发表于 2016-2-6 06:07:46 | 显示全部楼层
chentz 发表于 2016-2-6 05:53. more info on 1point3acres.com
第一题对较大的数的话应该要把它拆成尽可能多的3和不超过两个2吧。

没错,我后来也想到了这个特性。这个也可以programming的,但不知道是不是面试官想要的答案,因为他一直跟我强调这个不是数学问题= =
回复 支持 反对

使用道具 举报

pigeyes 发表于 2016-2-13 11:42:59 | 显示全部楼层
lz, 第二题的解法时间复杂度是多少?
我怎么觉得还是O(lng)呢?因为每次数某个range有几个的时候要遍利一遍: O(n), 二分法又要遍历lgn次, 这不还是O(nlgn)吗?
回复 支持 反对

使用道具 举报

 楼主| 面无表情 发表于 2016-2-13 14:08:47 | 显示全部楼层
pigeyes 发表于 2016-2-13 11:42
lz, 第二题的解法时间复杂度是多少?
我怎么觉得还是O(lng)呢?因为每次数某个range有几个的时候要遍利一 ...

对,还是O(nlogn),我也觉得很囧,明明他叫我优化的,最后还是和sort一样= =不过那个O(n)的算法也太难了,反正我是做不出来的……
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-2-13 15:33:26 | 显示全部楼层
除了quick select 还有一个更tricky 的方法就是找环路的intersection
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-2-13 15:36:50 | 显示全部楼层
Quick select 也能 o(n) 每步需要partition 这样下一回只要处理一半 我试过写 bug太多 放弃了
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-2-13 15:54:30 | 显示全部楼层
如果不能改数组就不能partition 了
回复 支持 反对

使用道具 举报

 楼主| 面无表情 发表于 2016-2-13 15:55:30 | 显示全部楼层
kinggarden2001 发表于 2016-2-13 15:36. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
Quick select 也能 o(n) 每步需要partition 这样下一回只要处理一半 我试过写 bug太多 放弃了

诶?处理一半不也是logn吗?不太明白你的思路
回复 支持 反对

使用道具 举报

 楼主| 面无表情 发表于 2016-2-13 16:14:01 | 显示全部楼层
kinggarden2001 发表于 2016-2-13 15:54
如果不能改数组就不能partition 了

恩对,要求不能改数组
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-2-14 09:18:31 | 显示全部楼层
处理一半是o(n) 想想quick sort 处理全部才是 nlgn 。
回复 支持 反对

使用道具 举报

sheepmiemies 发表于 2016-2-15 10:08:10 | 显示全部楼层
请问LZ那道找duplicate的题,一共有多少个duplicate啊?如果是unsorted怎么能用数量就确定在哪呢?是不是我题目没理解清楚。。。。
回复 支持 反对

使用道具 举报

lxxxxxxx 发表于 2016-2-15 10:56:43 | 显示全部楼层
第2轮不知道是不是leetcode上这道 287. Find the Duplicate Number
回复 支持 反对

使用道具 举报

 楼主| 面无表情 发表于 2016-2-15 13:18:44 | 显示全部楼层
sheepmiemies 发表于 2016-2-15 10:08
请问LZ那道找duplicate的题,一共有多少个duplicate啊?如果是unsorted怎么能用数量就确定在哪呢?是不是我 ...

可能有多个duplicates,具体可以查看leetcode一道hard难度的原题,搜duplicate就有了~那个方法挺神奇的我觉得哈哈哈
回复 支持 反对

使用道具 举报

 楼主| 面无表情 发表于 2016-2-15 13:19:00 | 显示全部楼层
lxxxxxxx 发表于 2016-2-15 10:56
第2轮不知道是不是leetcode上这道 287. Find the Duplicate Number

对的!就是287这道
回复 支持 反对

使用道具 举报

sheepmiemies 发表于 2016-2-18 00:40:19 | 显示全部楼层
面无表情 发表于 2016-2-15 13:18
可能有多个duplicates,具体可以查看leetcode一道hard难度的原题,搜duplicate就有了~那个方法挺神奇的我 ...

好的谢谢!
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-6 06:16:26 | 显示全部楼层
楼主"求这个整数的最大可能积"是怎么求呢?如果是递归检测每一个的话时间复杂度太高了吧?面试官说的map,应该是把每一个数的最大值放在map中吧,如8 分为4, 4只要计算一个4就行了
回复 支持 反对

使用道具 举报

 楼主| 面无表情 发表于 2016-3-8 05:16:52 | 显示全部楼层
bobzhang2004 发表于 2016-3-6 06:16
楼主"求这个整数的最大可能积"是怎么求呢?如果是递归检测每一个的话时间复杂度太高了吧?面试官说的map, ...

就是这样,子问题memoization
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 06:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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