一亩三分地论坛

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

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

Google 电面 2015/03/31

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

2015(1-3月) 码农类 硕士 全职@Google - 内推 - 在线笔试 |Other在职跳槽

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

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

x
本人在I开头的IT公司工作,今年有个朋友内推MTV的youtube部门,结果说不match。。。然后一个月之后通知我有合适的在Google Japan的位置,于是就安排今天面试。
. more info on 1point3acres.com
题目貌似很简单

1.给两个数列,分别找出在第一数列中出现,而第二个没有的数,然后还有第一个没有,但是第二个有的。
naive approach说了之后说可以用两个hashmap,存储每个数出现次数。写完之后说如果出现duplicate的话,怎么处理,处理的方法就是如果containsKey的话,要做减法,那个数列的这个数出现的次数多一些,再决定要不要加入到结果集合。
这题竟然写了20+分钟,google doc实在不好用。。。。但是我觉得完全没停顿思考过久。

2.第二题说一个无序数列,把它排列成index[0]<index[1]>index[2]<index[3]>index[4].............这样. Waral 鍗氬鏈夋洿澶氭枃绔,
. from: 1point3acres.com/bbs
想到的第一个方法是先数列从小到大排序,然后第一个配最后一个,递归的加进结果集合。这题他说时间不太够了(擦明明就还有20+分钟),不用写完整代码,写点伪代码就行了

面试官说有没有优化的方法,我就说可以从第一个元素开始,递归回朔的加入元素就行了。


面试了1一个小时,比原定时间多了点点(45min)。



我个人的感觉是要跪,因为题目貌似比较简单,比论坛里其他的面经立的题目要简单很多,但是优化的方法没想出来。。。有点伤感,加上第一题浪费时间估计让他觉得有点多了。
so。。。。。不抱希望。。。


我想跳槽。。。。. from: 1point3acres.com/bbs

评分

1

查看全部评分

wrbuaa2005 发表于 2015-3-31 15:24:06 | 显示全部楼层
就算有,wiggle sort的思路也应该没有问题,永远只能排最后两个,标示最后两个是大于等于或者小于等于两种关系即可
回复 支持 1 反对 0

使用道具 举报

dhldxy 发表于 2015-3-31 12:26:08 | 显示全部楼层
第二题说一个无序数列,把它排列成index[0]<index[1]>index[2]<index[3]>index[4]
是说排完之后第一个元素要小于第二个元素,第三个元素要小于第二个元素吗?
eg. 1, 3, 2, 5, 4?

补充内容 (2015-3-31 12:28):
如果这样的话,是不是如果在上面第一个最小。就按照从小到大先排序了。
然后在比如index[1]>index[2],就把这两个在本来sorted好了的array reverse一下。
回复 支持 反对

使用道具 举报

wrbuaa2005 发表于 2015-3-31 12:39:39 | 显示全部楼层
第二题,应该有o(n)解法吧,假设倒数两个数字n1>n2, 如果新来一个数n3比n2大,就加在后面,如果比n2小,就把n3加中间,n2移到后面
回复 支持 反对

使用道具 举报

 楼主| littleric 发表于 2015-3-31 12:40:15 | 显示全部楼层
dhldxy 发表于 2015-3-31 12:26
第二题说一个无序数列,把它排列成index[0]index[2]index[4]. 1point 3acres 璁哄潧
是说排完之后第一个元素要小于第二个元素,第 ...

你的例子是对的,所以我的想法是先排序,第一个和最后一个配对,然后递归剩下的数列,这样肯定可以保证是《》《》《》这样的配对。但是答案集肯定不只这个(虽然题目要求是只用返回一个数列就行)
. Waral 鍗氬鏈夋洿澶氭枃绔,
你说的还是需要排序,排序最少也得O(logn*n)把,面试官的意思是要时间复杂小于这个。。。

我只后的想法是从第一个开始选择,先选小,再选大,然后如果不符合(数列找不到合适的),代表之前的不对,就backtrack一下,然后他说ok就面试完了。。。。我现在想想好像不太对
回复 支持 反对

使用道具 举报

 楼主| littleric 发表于 2015-3-31 12:40:46 | 显示全部楼层
dhldxy 发表于 2015-3-31 12:26
第二题说一个无序数列,把它排列成index[0]index[2]index[4]
是说排完之后第一个元素要小于第二个元素,第 ...

IB后面加个字母。。。不能再继续说了。。。怕被老板看到哈哈哈哈
回复 支持 反对

使用道具 举报

MissBless 发表于 2015-3-31 13:26:05 | 显示全部楼层
基于Quick sort partitioning思想的Quick select可以在average O(n)中找出数组中Kth largest number,我们可以利用这个方法求出median.
之后再O(n)遍历一遍数组,并维护奇偶两个指针even = 0, odd = 1。
如果x > median, 那么index[odd++] = x;
如果x <= median, 那么index[even++] = x;

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

dhldxy 发表于 2015-3-31 13:35:06 | 显示全部楼层
MissBless 发表于 2015-3-31 13:26
基于Quick sort partitioning思想的Quick select可以在average O(n)中找出数组中Kth largest number,我们 ...

哈。刚在敲。发现你的思路和我一样。
需要指正的是odd = odd+2;
                  even=even+2
回复 支持 反对

使用道具 举报

shinichish 发表于 2015-3-31 13:38:24 | 显示全部楼层
第二问用wiggle sort来解,数没有duplicate吧?
回复 支持 反对

使用道具 举报

 楼主| littleric 发表于 2015-3-31 14:57:30 | 显示全部楼层
shinichish 发表于 2015-3-31 13:38. visit 1point3acres.com for more.
第二问用wiggle sort来解,数没有duplicate吧?

额,因为当时是第一题做完他就说,第二题不用写完整的代码啦,就写伪代码加你自己的想法说出来就行了。。。。目测要跪。。。。
回复 支持 反对

使用道具 举报

 楼主| littleric 发表于 2015-3-31 14:58:05 | 显示全部楼层
shinichish 发表于 2015-3-31 13:38
第二问用wiggle sort来解,数没有duplicate吧?

所以他第二题就说了大概题目,然后问我可以怎么实现,没说有没有duplicate。。。。
回复 支持 反对

使用道具 举报

dydcfg 发表于 2015-3-31 15:34:27 | 显示全部楼层
楼上正解,K大数的方法也可以O(N)做,但估计电面一紧张就会写得比较DT
回复 支持 反对

使用道具 举报

 楼主| littleric 发表于 2015-3-31 17:25:46 | 显示全部楼层
dydcfg 发表于 2015-3-31 15:34
楼上正解,K大数的方法也可以O(N)做,但估计电面一紧张就会写得比较DT

是啊,当时真的紧张的要命。。。不过还好印度小哥还比较nice。
.1point3acres缃话说内推的时MTV的youtube,然后被转到Japan的recruiter,今天面试是澳大利亚的developer。。。这种情况多不。

啊哈哈,问一下,觉得没戏
回复 支持 反对

使用道具 举报

ototsuyume 发表于 2015-3-31 18:02:21 | 显示全部楼层
littleric 发表于 2015-3-31 17:25
是啊,当时真的紧张的要命。。。不过还好印度小哥还比较nice。
话说内推的时MTV的youtube,然后被转到Ja ...

很正常,recruiter为了迁就你的时间会找不同地方的面试官。另外私信给楼主问一些问题,麻烦楼主方便的话回一下吧
回复 支持 反对

使用道具 举报

 楼主| littleric 发表于 2015-3-31 18:51:39 | 显示全部楼层
ototsuyume 发表于 2015-3-31 18:02
很正常,recruiter为了迁就你的时间会找不同地方的面试官。另外私信给楼主问一些问题,麻烦楼主方便的话 ...

哥我等级不够,不能发短消息啊。。。。。我现在主要做的是一个移动平台的开发/支持
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
那个tokyo office 的hr叫 James Fradley,你直接上linkedin搜就搜到了,邮箱也有。
他个人简介上面写着欢迎联系。。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 23:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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