一亩三分地论坛

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

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

google电面最新挂经

[复制链接] |试试Instant~ |关注本帖
allenxn24 发表于 2016-10-26 04:19:19 | 显示全部楼层 |阅读模式

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

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

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

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]. more info on 1point3acres.com
毫无思路阿毫无思路。。自挂东南枝去了。。

评分

3

查看全部评分

本帖被以下淘专辑推荐:

chestnut9919 发表于 2016-10-26 04:31:15 | 显示全部楼层
第二题就是拓扑排序吧
第一题生成的array没有限制吗?1,2,3或者abc都是哪来的?
回复 支持 反对

使用道具 举报

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

使用道具 举报

dokolo 发表于 2016-10-26 05:09:46 | 显示全部楼层
这个题目描述也是非常的醉...

第一题是要概率还是要distribution?
第二题是subarray还是subsequence?
回复 支持 反对

使用道具 举报

 楼主| allenxn24 发表于 2016-10-26 05:11:00 | 显示全部楼层
wangyuesong2 发表于 2016-10-26 04:59
我感觉第二题没法做啊,
[12533, 3334]->那结果应该是125333334,12533334,1253334中的哪个呢。。。描述的 ...

据他说是12533334但是他很不耐烦我也不知道我哪得罪他了……
回复 支持 反对

使用道具 举报

 楼主| allenxn24 发表于 2016-10-26 05:14:22 | 显示全部楼层
dokolo 发表于 2016-10-26 05:09. 1point3acres.com/bbs
这个题目描述也是非常的醉...

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

第一题是设计个generator 根据给的每个元素概率 来输出结果,结果长度固定。
第二题是给的一段段在原数组中连续的序列
回复 支持 反对

使用道具 举报

 楼主| allenxn24 发表于 2016-10-26 05:15:11 | 显示全部楼层
chestnut9919 发表于 2016-10-26 04:31
第二题就是拓扑排序吧
第一题生成的array没有限制吗?1,2,3或者abc都是哪来的?

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

使用道具 举报

jiajiechen0319 发表于 2016-10-26 05:21:22 | 显示全部楼层
第一题可以生成随机数 [0, 0.5) 生成1,[0.5, 0.8)生成2,[0.8,1]生成3。累计分布。
回复 支持 反对

使用道具 举报

dokolo 发表于 2016-10-26 05:22:49 | 显示全部楼层
allenxn24 发表于 2016-10-26 05:14
. 1point 3acres 璁哄潧第一题是设计个generator 根据给的每个元素概率 来输出结果,结果长度固定。
第二题是给的一段段在原数组 ...

第一题...
如果是要frequency满足要求,生成满足频率的数组然后洗牌. 鍥磋鎴戜滑@1point 3 acres
如果是要possibility满足要求,a = a/sum(a[i:]), 随机一个0到1的数,小于a的话就加到数组里,否则i+1
. From 1point 3acres bbs
第二题是连续序列的话应该有各种限制条件的... 我觉得你可能没全部问出来,不然解肯定不唯一...
回复 支持 反对

使用道具 举报

lxxxxxxx 发表于 2016-10-26 05:23:30 | 显示全部楼层
第二题感觉意思拓扑排序但是看你给的例子又有重复元素,有重复元素感觉还是有点影响吧....

第一题就例如 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] 然后随机一下这个数组?类似于蓄水池取样那样
回复 支持 反对

使用道具 举报

 楼主| allenxn24 发表于 2016-10-26 05:27:07 | 显示全部楼层
jiajiechen0319 发表于 2016-10-26 05:21
第一题可以生成随机数 [0, 0.5) 生成1,[0.5, 0.8)生成2,[0.8,1]生成3。累计分布。

我擦 有道理 我撒比了……
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-26 05:28:46 | 显示全部楼层
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()).
大家还有什么做法?
  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]. 鍥磋鎴戜滑@1point 3 acres
  4.   vector<double> psum(1, 0.0); for (auto p : prob) psum.push_back(psum.back() + p);
  5. . 1point3acres.com/bbs
  6.   for (unsigned int i = 0; i < n; ++i) {
  7.     double x = (double)rand() / (double)RAND_MAX; // random value in [0,1]
  8.     // find iterator pointing to the first value in psum greater than x
  9.     auto pos = upper_bound(psum.begin(), psum.end(), x); // binary search for sorted random access array
  10.     res.push_back(pos - psum.begin()); // set index of psum to result
  11.   }
  12.   return res;
  13. }
复制代码


. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
补充内容 (2016-10-26 05:33):. 1point 3acres 璁哄潧
这里假设生成数组中的每个元素是int in [1, M] (M=p.size()). 但其实只要是M个任意的object都可以,不影响实现。
回复 支持 反对

使用道具 举报

 楼主| allenxn24 发表于 2016-10-26 05:28:58 | 显示全部楼层
dokolo 发表于 2016-10-26 05:22. 鍥磋鎴戜滑@1point 3 acres
第一题...-google 1point3acres
如果是要frequency满足要求,生成满足频率的数组然后洗牌
如果是要possibility满足要求,a = ...

第二题我也觉得我没问全…小哥态度不是很友好…你们就当参考吧…
回复 支持 反对

使用道具 举报

chestnut9919 发表于 2016-10-26 05:30:02 | 显示全部楼层
第二题感觉没法做啊,给的条件不够,例子里的数组我拼成28,2,2,3,28,2也没毛病吧?还是要最短结果?
回复 支持 反对

使用道具 举报

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

使用道具 举报

zzgzzm 发表于 2016-10-26 05:36:44 | 显示全部楼层
lxxxxxxx 发表于 2016-10-26 05:23
第二题感觉意思拓扑排序但是看你给的例子又有重复元素,有重复元素感觉还是有点影响吧....

第一题就例如 ...
.1point3acres缃
理论上来说如果概率比值p/p[j]是分子分母都很大的有理数的话,那么这样做的时间空间复杂度就无法控制了。我觉得这个题还得用连续分布随机变量而不是离散型的。
回复 支持 反对

使用道具 举报

chestnut9919 发表于 2016-10-26 05:39:05 | 显示全部楼层
http://www.1point3acres.com/bbs/ ... read&tid=200588
概率题有点儿像这个面经里的国家人口那道
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-26 05:46:54 | 显示全部楼层
2.构建出原数组这道题感觉定义不是很清楚。
例如:[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了).
... 但如果题真的这么出我还没想好怎么做呢,呵呵
回复 支持 反对

使用道具 举报

rowena000 发表于 2016-10-26 07:01:49 | 显示全部楼层
dokolo 发表于 2016-10-26 05:22
第一题...
如果是要frequency满足要求,生成满足频率的数组然后洗牌
如果是要possibility满足要求,a = ...

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴应该是要求original array size最小吧
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-26 10:31:55 | 显示全部楼层
rowena000 发表于 2016-10-26 07:01
应该是要求original array size最小吧

我也在想这个题应该问可以恢复的原array的最小长度是多少。想了一个这个题好像就很难啊。也无法从sub-array的个数DP, 因为前n-1个sub-arrays可以构造出的最短array未必就是所有n个arrays构造出的最短array的某个sub-array.. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
没有什么想法。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 01:44

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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