一亩三分地论坛

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

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

Google 6.6电面 感觉药丸

[复制链接] |试试Instant~ |关注本帖
qofferad 发表于 2016-6-7 11:46:56 | 显示全部楼层 |阅读模式

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

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

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

x
本来投的是EE方向,后来recruiter主动联系说你投的已经满了,想不想面SDE,我说当然好了,然后五月初写完了OA,题目很稳定,地里面两道题答案都有今天下午电面,面试官听口音应该是个美国本地大叔,声音很和蔼,是总部的site reliability engineer, 先跟我聊了下简历,然后就开始做题。. from: 1point3acres.com/bbs
第一题:打印所有的质数(print all prime numbers),我已开始没理解清楚范围,设了个i <Integer.MAX_VALUE,为了第一题秒时间,我没多想就用了俩for loop写出来了,他说可以,这样能保证小范围的质数短时间打出来
第二题:follow up, what if keep printing to the number that greater than the biginteger by using java, 没想明白,我说java里面有biginteger的library,大于long的长度,他说这样用第一题的方法的话越到最后时间越长,两个数间隔好很久(假设n到正无穷..)
因为是个O(N*N)的解法,有没有更好的解法,大叔很有耐心,一直在等我想,也给了些hint,我最后没想出来,后来时间到了,感觉药丸。
后来他推荐说经常上project euler上面刷刷题,我说好的,估计是暗示我刷的不够吧,本来专业就不一样,EE出身半路出家转CS,最后一学期发现EE工作很难找于是赚了CS,还是挺吃力的,anyway,先写出来给地里的兄弟姐妹们看看面经吧,攒个人品

评分

2

查看全部评分

本帖被以下淘专辑推荐:

  • · Google|主题: 54, 订阅: 45
handsomecool 发表于 2016-6-7 12:20:39 | 显示全部楼层
可以O(n) space, linear time,从小到大用当前的质数乘以常数得到合数, wikipedia有,自己想不太容易
回复 支持 反对

使用道具 举报

robinali 发表于 2016-6-7 12:56:47 | 显示全部楼层
查了下project euler 上面全是逻辑题目啊

这个是wiki:
https://en.wikipedia.org/wiki/Primality_test
回复 支持 反对

使用道具 举报

jjustc 发表于 2016-6-11 01:49:11 | 显示全部楼层
robinali 发表于 2016-6-7 12:56
查了下project euler 上面全是逻辑题目啊

这个是wiki:
.鐣欏璁哄潧-涓浜-涓夊垎鍦
这个是检测某个数是不是质数吧,不是print出 某个范围内的所有质数.鏈枃鍘熷垱鑷1point3acres璁哄潧

补充内容 (2016-6-11 01:51):
我只知道有O(NloglogN)的方法,就是leetcode 204,应该也足够应付数越来越大的情况了吧 = =
回复 支持 反对

使用道具 举报

robinali 发表于 2016-6-11 11:32:20 | 显示全部楼层
jjustc 发表于 2016-6-11 01:49
这个是检测某个数是不是质数吧,不是print出 某个范围内的所有质数
. more info on 1point3acres.com 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
补充内容 (2016-6-11 01:51):

收到, 明天刷204. ^_^

补充内容 (2016-6-13 16:04):
发下我当初204的答案(C++):.鐣欏璁哄潧-涓浜-涓夊垎鍦
class Solution {
public:. 1point 3acres 璁哄潧
    int countPrimes(int n) {. from: 1point3acres.com/bbs
         bool *tag = new bool[n];
         int *prime = new int[n];
         int cnt = 0;
         memset(tag, tru...
回复 支持 反对

使用道具 举报

hakase 发表于 2016-6-11 12:12:44 | 显示全部楼层
两年前看欧拉上的题目均是数论相关的,数学好的话据说可以手撕。当时做着就很头疼。后来发现和大多数公司算法+数据结构这种面试的主流风格有些不同,于是就没再碰了。

想起又是两年前看某博客,一个数学系博士面Google,面的题目是开平方。博主给面试官当场写了四五种算法,于是offer了。。
回复 支持 反对

使用道具 举报

robinali 发表于 2016-6-13 16:04:52 | 显示全部楼层
robinali 发表于 2016-6-11 11:32
收到, 明天刷204. ^_^. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

补充内容 (2016-6-13 16:04):

答案完整版:
class Solution {
public:
    int countPrimes(int n) {
         bool *tag = new bool[n];
         int *prime = new int[n]; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
         int cnt = 0;.1point3acres缃
         memset(tag, true, sizeof(bool) * n);
         for (int i = 2; i < n; ++i) {
             if (tag) prime[cnt++] = i;
             for (int j = 0; j < cnt && i * prime[j] < n; ++j) {
                 tag[i * prime[j]] = false;
                 if (i % prime[j] == 0) break;
             }.鏈枃鍘熷垱鑷1point3acres璁哄潧
         }
         delete [] tag;. from: 1point3acres.com/bbs
         delete [] prime;-google 1point3acres
         return cnt;
     }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
};

补充内容 (2016-6-13 16:35):
三月前的答案, 不确定参考了哪里
回复 支持 反对

使用道具 举报

readman 发表于 2016-6-13 21:21:53 | 显示全部楼层
先用素数的某个公式, 能算出n个素数在的区间。。然后一个个测试。。。。。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
忘了什么公式了 找到再补充
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 14:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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