Google 电面 2015/03/31

本人在I开头的IT公司工作，今年有个朋友内推MTV的youtube部门，结果说不match。。。然后一个月之后通知我有合适的在Google Japan的位置,于是就安排今天面试。

题目貌似很简单

1.给两个数列，分别找出在第一数列中出现，而第二个没有的数，然后还有第一个没有，但是第二个有的。
naive approach说了之后说可以用两个hashma

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

觉得有点多了。
so。。。。。不抱希望。。。


我想跳槽。。。。

就算有，wiggle sort的思路也应该没有问题，永远只能排最后两个，标示最后两个是大于等于或者小于等于两种关系即可

dhldxy 发表于 2015-3-31 12:26
第二题说一个无序数列，把它排列成index[0]index[2]index[4]
是说排完之后第一个元素要小于第二个元素，第 ...

你的例子是对的，所以我的想法是先排序，第一个和最后一个配对，然后递归剩下的数列，这样肯定可以保证是《》《》《》这样的配对。但是答案集肯定不只这个（虽然题目要求是只用返回一个数列就行）

你说的还是需要排序，排序最少也得O(logn*n)把，面试官的意思是要时间复杂小于这个。。。

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

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

哥我等级不够，不能发短消息啊。。。。。我现在主要做的是一个移动平台的开发/支持

那个tokyo office 的hr叫 James Fradley,你直接上linkedin搜就搜到了，邮箱也有。
他个人简介上面写着欢迎联系。。。

第二题说一个无序数列，把它排列成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一下。

第二题，应该有o（n）解法吧，假设倒数两个数字n1>n2, 如果新来一个数n3比n2大，就加在后面，如果比n2小，就把n3加中间，n2移到后面

dhldxy 发表于 2015-3-31 12:26
第二题说一个无序数列，把它排列成index[0]index[2]index[4]
是说排完之后第一个元素要小于第二个元素，第 ...

IB后面加个字母。。。不能再继续说了。。。怕被老板看到哈哈哈哈

基于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;

MissBless 发表于 2015-3-31 13:26
基于Quick sort partitioning思想的Quick select可以在average O(n)中找出数组中Kth largest number，我们 ...

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

第二问用wiggle sort来解，数没有duplicate吧？

shinichish 发表于 2015-3-31 13:38
第二问用wiggle sort来解，数没有duplicate吧？

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

shinichish 发表于 2015-3-31 13:38
第二问用wiggle sort来解，数没有duplicate吧？

所以他第二题就说了大概题目，然后问我可以怎么实现，没说有没有duplicate。。。。