一亩三分地论坛

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

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

Google電面

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

2016(1-3月) 码农类 硕士 全职@Google - 网上海投 - 技术电面 |Failfresh grad应届毕业生

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

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

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

題目是:

Given a set S of 10^6 doubles. Find a number X so that the [X, X+1) half-open real interval contains as many elements of S as possible.For example, given this 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, [...]the value X desired is 1.98 because there are 4 values in the range 1.98 to 2.97999 (1.98, 2.7, 2.75, 2.95). visit 1point3acres.com for more.



這題我的解法是先sort過一遍之後再使用two pointers找,那時面完就覺得沒有說得很順,後來結果也是掛了~~

希望可以幫我加點分!!



. 鍥磋鎴戜滑@1point 3 acres




. Waral 鍗氬鏈夋洿澶氭枃绔,


评分

3

查看全部评分

googlerr 发表于 2016-2-29 16:58:38 | 显示全部楼层
pat pat,谢谢楼主分享!sort+2p应该是最优解。他们现在电面都这么高的bar啊。。。
回复 支持 反对

使用道具 举报

yyyusa 发表于 2016-3-1 05:18:08 | 显示全部楼层
难道还有更好的解法?
回复 支持 反对

使用道具 举报

zxl9171 发表于 2016-3-4 07:04:45 | 显示全部楼层
我感觉是取整扔到一个set里。。。。存最大值就行了。。。
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-3-4 07:23:02 | 显示全部楼层
zxl9171 发表于 2016-3-4 07:04. from: 1point3acres.com/bbs
我感觉是取整扔到一个set里。。。。存最大值就行了。。。

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

使用道具 举报

 楼主| eddyclhung 发表于 2016-3-4 07:26:28 | 显示全部楼层
googlerr 发表于 2016-3-4 07:23
应该没这么简单。如果X只能是整数,你这个思路可行,但X是double,所以理论上讲有无限个Bucket / Set

是啊,如果是2.5跟3.4,他們的X是2,但是取整卻分類到不同的bucket了~
回复 支持 反对

使用道具 举报

zxl9171 发表于 2016-3-4 08:53:32 | 显示全部楼层
eddyclhung 发表于 2016-3-4 07:26
是啊,如果是2.5跟3.4,他們的X是2,但是取整卻分類到不同的bucket了~

哦。我没看清楚。。。。
回复 支持 反对

使用道具 举报

厉害的超人 发表于 2016-3-4 10:48:56 | 显示全部楼层
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());. visit 1point3acres.com for more.
    double X=subset[0];
    while(end<n) {
        ++end;
        while(subset[end]-subset[beg]>=1) ++beg;
        if(end-beg+1>len) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
            len=end-beg+1;
            X=subset[beg];
. from: 1point3acres.com/bbs         }
    }
    return X;
}

int main() {. From 1point 3acres bbs
    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;.鐣欏璁哄潧-涓浜-涓夊垎鍦
}
. 1point3acres.com/bbs
这样都会挂啊?

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

使用道具 举报

sheepmiemies 发表于 2016-3-16 09:58:05 | 显示全部楼层
确实出了sort + sliding window想不出更好的方法了。。。但是数据量比较大。。

LS上的发帖时间居然比补充内容时间还晚是啥情况。。。
回复 支持 反对

使用道具 举报

Alice0701 发表于 2016-3-31 06:13:08 | 显示全部楼层
这为啥会不过呢...面试官当时有对你的方法给些提示吗?
回复 支持 反对

使用道具 举报

 楼主| eddyclhung 发表于 2016-3-31 06:15:16 | 显示全部楼层
Alice0701 发表于 2016-3-31 06:13
这为啥会不过呢...面试官当时有对你的方法给些提示吗?
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
可能是在講述的時候沒有很流暢地講出來吧,或是我在寫code的時候,有時候一緊張變數就打錯了!
面試官感覺是個人不錯的白人大叔,也會一直提示
回复 支持 反对

使用道具 举报

Alice0701 发表于 2016-3-31 06:34:30 | 显示全部楼层
eddyclhung 发表于 2016-3-31 06:15
可能是在講述的時候沒有很流暢地講出來吧,或是我在寫code的時候,有時候一緊張變數就打錯了!
面試官感 ...

哦哦,积累经验下次肯定能过嗒
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-31 12:01:19 | 显示全部楼层
这个应该还是bucket sort那样来做吧, 就是开一个很多歌长度为1 的bucket,然后里面放上数
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-4-28 05:02:19 | 显示全部楼层
bobzhang2004 发表于 2016-3-31 12:01.鐣欏璁哄潧-涓浜-涓夊垎鍦
这个应该还是bucket sort那样来做吧, 就是开一个很多歌长度为1 的bucket,然后里面放上数

那小数怎么处理呢?
回复 支持 反对

使用道具 举报

情狠赞 发表于 3 天前 | 显示全部楼层
感觉桶排序吧,O(n) 扫一遍就结束了
回复 支持 反对

使用道具 举报

小A要当码农 发表于 前天 04:53 | 显示全部楼层
情狠赞 发表于 2016-12-4 12:33
感觉桶排序吧,O(n) 扫一遍就结束了
. 鍥磋鎴戜滑@1point 3 acres
桶排序好像不太行吧,,除非你能维持桶内部有序。
回复 支持 反对

使用道具 举报

hwu2498 发表于 前天 07:20 | 显示全部楼层
这题排什么序啊。。?直接哈希表存一下不就完事了?

[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就行.1point3acres缃

补充内容 (2016-12-5 14:21):
没自习看题。X不一定是整数。。
.鏈枃鍘熷垱鑷1point3acres璁哄潧哈哈表学我。那看来是要排序
回复 支持 反对

使用道具 举报

nautilus 发表于 前天 09:04 | 显示全部楼层
按楼上的方法的话

[2.5 3.4] 就是{2:1, 3:4}
然而实际应该输出{2.5~3.5: 2}
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 18:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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