Google電面

發一下之前一月底Google的電面，一開始打來就是簡單的自我介紹聊聊project之後就開始給題了，

題目是：

Given a set S of 10^6 d

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

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

4444">

sort+2pointers我觉得已经是最优解了：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

double maxLenSub(vector<double> & subset) {
    int beg=0, end=0, len=1, n=subset.size();
    if(n==0) return 0.0;
    sort(subset.begin(), subset.end());
    double X=subset[0];
    while(end<n) {
        ++end;
        while(subset[end]-subset[beg]>=1) ++beg;
        if(end-beg+1>len) {
            len=end-beg+1;
            X=subset[beg];
        }
    }
    return X;
}

int main() {
    vector<double> subset={2.7, 0.23, 8.32, 9.65, -6.55, 1.55, 1.98, 7.11, 0.49, 2.75, 2.95, -96.023, 0.14, 8.60};
    cout <<maxLenSub(subset) << endl;
}

这样都会挂啊？

补充内容 (2016-3-3 18:53):
除非是要考虑Given a set S of 10^6 doubles， 然后这个subset会不停的变，希望时间能做到O(n)，还没有想出来。

小A要当码农 发表于 2016-12-30 05:50
他这个X不一定是整数啊

整数桶计数，然后扫描一遍获取最大值的桶，所以答案一定至少是这个值。叫这个最大值为max1，然后扫描桶，当碰到i和i+1桶数目和大于max1的时候，只排序这两个桶的内容就可以了。这个做法只是优化，并不会降低时间复杂度

这题排什么序啊。。？直接哈希表存一下不就完事了？

[0.1, 7.5, 5.63, 4.13, 1.2, 3.4, 4.2, 4.5]

哈希表的key是数字的整数部分。value是整数部分是这个数的 数字出现的次数。
比如如上数组，哈希表应该是 {0: 1, 1: 1, 3: 1, 4: 3, 5: 1, 7: 1}
然后哈希表走一遍输出value最大的key就行

补充内容 (2016-12-5 14:21):
没自习看题。X不一定是整数。。
哈哈表学我。那看来是要排序

pat pat，谢谢楼主分享！sort+2p应该是最优解。他们现在电面都这么高的bar啊。。。

难道还有更好的解法？

我感觉是取整扔到一个set里。。。。存最大值就行了。。。

zxl9171 发表于 2016-3-4 07:04
我感觉是取整扔到一个set里。。。。存最大值就行了。。。

应该没这么简单。如果X只能是整数，你这个思路可行，但X是double，所以理论上讲有无限个Bucket / Set

googlerr 发表于 2016-3-4 07:23
应该没这么简单。如果X只能是整数，你这个思路可行，但X是double，所以理论上讲有无限个Bucket / Set

是啊，如果是2.5跟3.4，他們的Ｘ是2，但是取整卻分類到不同的bucket了～

eddyclhung 发表于 2016-3-4 07:26
是啊，如果是2.5跟3.4，他們的Ｘ是2，但是取整卻分類到不同的bucket了～

哦。我没看清楚。。。。