一亩三分地论坛

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

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

Google 15 Fall SDE Intern Phone Interview (Additional Interview)

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

2015(7-9月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Other其他

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

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

x
上周二和Google Phone Interview的, 一共两轮,面经在这里。 当时第二轮被问了一道Reservoir Sampling的变种题,所有时间基本上花在确认问题上,答得很不好,思来想去觉得还想再搏一下试一试,于是第二天直接给HR发信说明情况,表明确定题目花时间太久感觉影响了technical skills' evaluation希望重新面一次, 极其幸运的是,HR很爽快的reschedule了这周的一轮additional interview。
之前两轮都是中国人,这次一个三哥,个人觉得很不错,很和善也很愿意说话之类的。 问了两道题。
第一题是 Given an array of integers, remove all the duplicates from it.
这题我比较瞎的一点是忘记和他确认sorted or not了,但是感觉三哥自己也没察觉或者,我第一次就是原数组两个pointer直接消除duplicates,我刚写玩pseudo code说要convert into real code,他就直接说觉得是work的,然后问我time complexity,然后说能不能比 O(n^2) 更好, 于是initiate a new array, 接着两个pointer比较。这次写完了的时候,惊觉忘记确认sorted了,于是还没跑test case之前马上问,然后三哥貌似也突然意识到然后顺势说unsorted, 我就说iterate之前先sort,三哥又表示希望keep original order。于是用了hashmap。写完这题大概还剩15分钟。


第二题是Given a list of integers, sort them in a way that if output is s1, s2, s3 .. sN then s1 <= s2 >=s3 <=s4 ... sN.. from: 1point3acres.com/bbs
因为时间不多了,看到题的时候有点着急,于是直接说了最开始的idea,说先写这个algorithm然后我再optimize,三哥很nice,说怕我时间来不及,尽量在结束前写完,直接real code吧。最开始想法是说直接merge sort然后头尾依次输出,三哥问了time complexity,然后说希望更快,于是边说边写了 iterate 的方法,就是每个元素和后一个元素比较看是不是希望的次序,如果不是的话互换就好。写完之后三说 he thinks this won't work for every case. 然后让我想一个not working case 最开始有点蒙,但是我一直没想到,于是小哥自己写了一个case,说你看这个是不是不work,我给他跑了一遍,发现是work的,此时小哥自己有点蒙说give me a second, 然后说觉得code goes well,后时间刚刚好到,相互客套结束interview。

总体感觉没有上次那么紧张,然后一定注意细节,多沟通确认方向,也会有hints。以及鼓励大家如果觉得面的不好且感觉自己没有发挥到准备的水平的话,不妨及时给HR写信反映,说不定就会additional interview的机会。

Anyway,希望大家面试顺利,一起加油。. 鍥磋鎴戜滑@1point 3 acres

评分

3

查看全部评分

jiebour 发表于 2015-8-14 09:03:01 | 显示全部楼层
楼主,第二题你复杂度是多少?是O(N)嘛?
回复 支持 反对

使用道具 举报

baobozo 发表于 2015-8-14 11:18:03 | 显示全部楼层
我昨天貌似在地里看到了第二题的面经~~
回复 支持 反对

使用道具 举报

catinclay 发表于 2015-8-14 11:43:53 | 显示全部楼层
第二題是Wiggle sort, 網上有答案可找
回复 支持 反对

使用道具 举报

glaciersilent 发表于 2015-8-14 12:01:05 | 显示全部楼层
有个思路不知如何 用quick select选出前(n+1)/2个最小的元素 然后按照题述的顺序把后一半比较大的元素逐个插入前一半元素之间 时间O(n)
回复 支持 反对

使用道具 举报

Williamslg 发表于 2015-8-17 14:31:17 | 显示全部楼层
LZ, 第一题能具体说下要求嘛?如果原数组是sorted的话不是O(n)就可以处理嘛?怎么会有O(n^2)呢?
回复 支持 反对

使用道具 举报

chen6145 发表于 2015-8-18 06:41:39 | 显示全部楼层
第二题直接sort之后按第二大,第一大,第三大,第四大。。。这个顺序输出貌似就可以了?
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-8-26 14:44:08 | 显示全部楼层
楼主你第二题互换次序不行吧,换了之后不一定满足前面的呀。。
回复 支持 反对

使用道具 举报

flamen 发表于 2015-9-1 23:12:40 | 显示全部楼层
第二题wiggle sort复杂度是O(n)不?
回复 支持 反对

使用道具 举报

flyaway25 发表于 2015-9-1 23:46:41 | 显示全部楼层
hj867955629 发表于 2015-8-26 14:44
楼主你第二题互换次序不行吧,换了之后不一定满足前面的呀。。

先跟前面一个元素比,然后再跟后面一个元素比,每次都是加2的往后走。当前一个元素满足要求后,但是后一个元素不满足要求,这个时候三个数字是递增关系,所以把后面一个数字和中间数字互换就可以了。所以还是线性复杂度。
回复 支持 反对

使用道具 举报

luzhuzeng 发表于 2015-9-9 05:12:48 | 显示全部楼层
hj867955629 发表于 2015-8-26 00:44
楼主你第二题互换次序不行吧,换了之后不一定满足前面的呀。。
. more info on 1point3acres.com
void wiggle_sort(std::vector<int>& v) {
        // v[0] <= v[1] ?= v[2] <= v[3] >= ..
        for (int i = 1; i < v.size(); ++i) {
                if (  ( (i&1)&&(v<v[i-1]) )  || ( !(i&1)&&(v>v[i-1]) ) )
                        swap(v,v[i-1]);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        }
}
回复 支持 反对

使用道具 举报

atlas1017 发表于 2015-9-14 09:10:54 | 显示全部楼层
flamen 发表于 2015-9-1 23:12. From 1point 3acres bbs
第二题wiggle sort复杂度是O(n)不?

握手 我觉得是可行的 : )
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 10:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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