【生活质量系列】评测几款用过的咖啡机

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 3368|回复: 31
收起左侧

google电面最新挂经

[复制链接] |试试Instant~
我的人缘0
allenxn24 发表于 2016-10-26 04:19:19 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (19)
 
 
0% (0)  踩

2017(10-12月) 码农类General 硕士 实习@Google - 网上海投 - 技术电面  | Other | fresh grad应届毕业生

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

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

x
我只是想来看看大神们的思路,本渣已经被按在地上打。。。
题目: 来源一亩.三分地论坛.
        1. design 一个generator
            input:int n, double[] possibility
            output: 根据possibility, random generate 一串array
        example:
            input :10, [0.5,0.3,0.2]
            output: [1,1,1,1,1,2,2,2,3,3] or [1,1,2,2,3,3,2,1,1,1] or balabalab
            答案排序完全随机, 每次call这个method都会给不同答案,只有每个数distribution是一致的。

        2.给出一些subarray,构建出原数组,比如:
       input: [[28,2],[2,3,28,2]]
       output: [2,3,28,2]
毫无思路阿毫无思路。。自挂东南枝去了。。

评分

参与人数 3大米 +46 收起 理由
lic10 + 3 感谢分享!
1451427216 + 3 感谢分享!
阿童木 + 40 感谢分享!

查看全部评分


上一篇:DropBox OA
下一篇:求问google店面一般是旧题吗?
我的人缘0
chestnut9919 发表于 2016-10-26 04:31:15 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (20)
 
 
0% (0)  踩
第二题就是拓扑排序吧
第一题生成的array没有限制吗?1,2,3或者abc都是哪来的?
回复

使用道具 举报

我的人缘0
wangyuesong2 发表于 2016-10-26 04:59:21 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  94% (126)
 
 
5% (7)  踩
我感觉第二题没法做啊,
[12533, 3334]->那结果应该是125333334,12533334,1253334中的哪个呢。。。描述的不是很清楚啊
第一题不知道能不能根据n和possibility先generate出一个hahmap来里面存数字->剩余的次数,然后random n次每次从hashmap中取一个还有剩余的数
回复

使用道具 举报

我的人缘0
dokolo 发表于 2016-10-26 05:09:46 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (42)
 
 
12% (6)  踩
这个题目描述也是非常的醉...

第一题是要概率还是要distribution?
第二题是subarray还是subsequence?
回复

使用道具 举报

我的人缘0
 楼主| allenxn24 发表于 2016-10-26 05:11:00 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (19)
 
 
0% (0)  踩
wangyuesong2 发表于 2016-10-26 04:59
我感觉第二题没法做啊,
[12533, 3334]->那结果应该是125333334,12533334,1253334中的哪个呢。。。描述的 ...
. From 1point 3acres bbs
据他说是12533334但是他很不耐烦我也不知道我哪得罪他了……

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
 楼主| allenxn24 发表于 2016-10-26 05:14:22 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (19)
 
 
0% (0)  踩
dokolo 发表于 2016-10-26 05:09
这个题目描述也是非常的醉... 来源一亩.三分地论坛.

第一题是要概率还是要distribution?

第一题是设计个generator 根据给的每个元素概率 来输出结果,结果长度固定。.本文原创自1point3acres论坛
第二题是给的一段段在原数组中连续的序列
回复

使用道具 举报

我的人缘0
 楼主| allenxn24 发表于 2016-10-26 05:15:11 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (19)
 
 
0% (0)  踩
chestnut9919 发表于 2016-10-26 04:31-google 1point3acres
第二题就是拓扑排序吧
第一题生成的array没有限制吗?1,2,3或者abc都是哪来的?

无所谓array的元素,只要按它们的概率分配就成
回复

使用道具 举报

我的人缘0
jiajiechen0319 发表于 2016-10-26 05:21:22 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (19)
 
 
5% (1)  踩
第一题可以生成随机数 [0, 0.5) 生成1,[0.5, 0.8)生成2,[0.8,1]生成3。累计分布。
回复

使用道具 举报

我的人缘0
dokolo 发表于 2016-10-26 05:22:49 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (42)
 
 
12% (6)  踩
allenxn24 发表于 2016-10-26 05:14
第一题是设计个generator 根据给的每个元素概率 来输出结果,结果长度固定。
第二题是给的一段段在原数组 ...

第一题...
如果是要frequency满足要求,生成满足频率的数组然后洗牌
如果是要possibility满足要求,a = a/sum(a[i:]), 随机一个0到1的数,小于a的话就加到数组里,否则i+1

第二题是连续序列的话应该有各种限制条件的... 我觉得你可能没全部问出来,不然解肯定不唯一...
回复

使用道具 举报

我的人缘0
lxxxxxxx 发表于 2016-10-26 05:23:30 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  94% (37)
 
 
5% (2)  踩
第二题感觉意思拓扑排序但是看你给的例子又有重复元素,有重复元素感觉还是有点影响吧....

第一题就例如 input :10, [0.5,0.3,0.2]    你就可以确定有5个1,3个2,2个3
原始list [1,1,1,1,1,3,3,3,2,2] 然后随机一下这个数组?类似于蓄水池取样那样
回复

使用道具 举报

我的人缘0
 楼主| allenxn24 发表于 2016-10-26 05:27:07 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (19)
 
 
0% (0)  踩
jiajiechen0319 发表于 2016-10-26 05:21
第一题可以生成随机数 [0, 0.5) 生成1,[0.5, 0.8)生成2,[0.8,1]生成3。累计分布。

我擦 有道理 我撒比了……

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

我的人缘0
zzgzzm 发表于 2016-10-26 05:28:46 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (63)
 
 
1% (1)  踩
1. design 一个generator
这个可以用所给的double[] p来构造一个[0, 1]区间以及内部格点:0, p[0], p[0]+p[1], ... , 1 (=sum of all p), 这样就可以用[0, 1]均匀分布的性质了:[0, 1]均匀分布变量落在任意子区间的概率就是子区间的长度。C++中用“(double)rand() / (double)RAND_MAX” 就可以随机得到一个[0, 1]均匀分布变量X,然后用binary search找出X落在哪个子区间即可。这样时间复杂度O(n*log(p.size())) (假设生成随机变量是O(1)的)。空间复杂度O(n+p.size()).
大家还有什么做法?. from: 1point3acres
  1. vector<int> getRandomArray(const unsigned int n, const vector<double>& prob) {
  2.   vector<int> res;
  3.   // construct partial sum array: psum[i] = prob[0]+...+prob[i-1]. 留学申请论坛-一亩三分地
  4.   vector<double> psum(1, 0.0); for (auto p : prob) psum.push_back(psum.back() + p);. Waral 博客有更多文章,

  5.   for (unsigned int i = 0; i < n; ++i) {
  6.     double x = (double)rand() / (double)RAND_MAX; // random value in [0,1]
  7.     // find iterator pointing to the first value in psum greater than x
  8.     auto pos = upper_bound(psum.begin(), psum.end(), x); // binary search for sorted random access array
  9.     res.push_back(pos - psum.begin()); // set index of psum to result-google 1point3acres
  10.   }
  11.   return res;
  12. }
复制代码


. 牛人云集,一亩三分地
补充内容 (2016-10-26 05:33):
这里假设生成数组中的每个元素是int in [1, M] (M=p.size()). 但其实只要是M个任意的object都可以,不影响实现。
回复

使用道具 举报

我的人缘0
 楼主| allenxn24 发表于 2016-10-26 05:28:58 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (19)
 
 
0% (0)  踩
dokolo 发表于 2016-10-26 05:22
第一题...
如果是要frequency满足要求,生成满足频率的数组然后洗牌. 留学申请论坛-一亩三分地
如果是要possibility满足要求,a = ...

.1point3acres网第二题我也觉得我没问全…小哥态度不是很友好…你们就当参考吧…
回复

使用道具 举报

我的人缘0
chestnut9919 发表于 2016-10-26 05:30:02 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (20)
 
 
0% (0)  踩
第二题感觉没法做啊,给的条件不够,例子里的数组我拼成28,2,2,3,28,2也没毛病吧?还是要最短结果?
回复

使用道具 举报

我的人缘0
chestnut9919 发表于 2016-10-26 05:34:46 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (20)
 
 
0% (0)  踩
第一题可不可以先加和概率数组:[0.5, 0.8, 1.0], 然后自己建一个等长数组装element比如[1,2,3]。 random生成0-1.0的一个double,再去概率数组里找这个double落在哪个range,比如<0.5,就去第二个数组里找index=0的, 如果数组元素很多,可以binary search。
回复

使用道具 举报

我的人缘0
zzgzzm 发表于 2016-10-26 05:36:44 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (63)
 
 
1% (1)  踩
lxxxxxxx 发表于 2016-10-26 05:23
第二题感觉意思拓扑排序但是看你给的例子又有重复元素,有重复元素感觉还是有点影响吧....
. 1point 3acres 论坛
第一题就例如 ...
. from: 1point3acres
理论上来说如果概率比值p/p[j]是分子分母都很大的有理数的话,那么这样做的时间空间复杂度就无法控制了。我觉得这个题还得用连续分布随机变量而不是离散型的。
回复

使用道具 举报

我的人缘0
chestnut9919 发表于 2016-10-26 05:39:05 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (20)
 
 
0% (0)  踩
http://www.1point3acres.com/bbs/ ... read&tid=200588
概率题有点儿像这个面经里的国家人口那道
回复

使用道具 举报

我的人缘0
zzgzzm 发表于 2016-10-26 05:46:54 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (63)
 
 
1% (1)  踩
2.构建出原数组这道题感觉定义不是很清楚。.本文原创自1point3acres论坛
例如:[1, 2], [2, 3], 那么结果可能是 [1,2,3], [1,2,2,3], [2,3,1,2].
如果这样定义可以是一个合理的题:给定一个vector<int> a的一些consecutive subarrays vector<vector<int>> subs,求原来array a的最小长度。(注意:即使求最小长度原来array也可能不唯一,但至少这个题就well defined了).
... 但如果题真的这么出我还没想好怎么做呢,呵呵
回复

使用道具 举报

我的人缘0
rowena000 发表于 2016-10-26 07:01:49 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (2)
 
 
0% (0)  踩
dokolo 发表于 2016-10-26 05:22
第一题...
如果是要frequency满足要求,生成满足频率的数组然后洗牌
如果是要possibility满足要求,a = ...

应该是要求original array size最小吧
回复

使用道具 举报

我的人缘0
zzgzzm 发表于 2016-10-26 10:31:55 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (63)
 
 
1% (1)  踩
rowena000 发表于 2016-10-26 07:01
应该是要求original array size最小吧

我也在想这个题应该问可以恢复的原array的最小长度是多少。想了一个这个题好像就很难啊。也无法从sub-array的个数DP, 因为前n-1个sub-arrays可以构造出的最短array未必就是所有n个arrays构造出的最短array的某个sub-array.
没有什么想法。
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|一亩三分地论坛声明

GMT+8, 2018-9-21 10:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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