boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 问一道brainteaser
相关主题
问几个brain teaser
问个小题
讨论CAIWU那道矩阵DP题的思路?
今早google电面报告
怎么判断一个数的二进制是不是回文数
Facebook interview questions
Citibank 第二轮
那1000道题我其实说的是...
如何判断一个数是不是回文?
几年前G家onsite的一道题
相关话题的讨论汇总
话题: 卷积话题: 数字话题: fft话题: 55252
进入JobHunting版参与讨论
1 (共1页)
t*******e
发帖数: 1633
1
1. 6 digits number, each changes from 0 to 9. Find the odds that sum of
first three is the same as the sum of last three.
大牛han6曾给出如下解答, 无奈小弟实在看不懂,哪位高人能出来详细解答一下
另小弟明早Bloomberg onsite, 请各位等我面经
发信人: han6 (周瑜), 信区: JobHunting
标 题: Re: 问几个brain teaser
发信站: BBS 未名空间站 (Tue Sep 28 14:46:27 2010, 美东)
每一个数字都是0~9的iid
一个数字的情况,总和为0~9的方法分别为
1, 1, 1, 1, 1, 1, 1, 1, 1, 1
两个数字的情况,总和为0~18的方法为以上的卷积
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
三个数字的情况,总和为0~27的方法为以上的卷积
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 63, 69, 73, 75, 75, 73, 69, 63, 55,
45,
36, 28, 21, 15, 10, 6, 3, 1
然后计算平方和为:55252
则概率为 55252/1000000
如果考官要你推广到m进制的n个数字相等(前后共2n个数字)
那么,可以告诉他,或者她:
利用 FFT 进行 logn 次卷积,其中最长的一次长度为 mn/2
总复杂度为:mnlog(mn)logn
不用FFT的话,由于卷积的特殊性,可以达到mn^2,考虑 FFT 的额外开销,实际速度可
能相差不
大。
如果这是一个二进制的问题,即每个数字只能是 0 或 1。那么无论多少个数
字都可以很容易的求出结果,因为其历次卷积得到了杨辉三角。
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
s*******r
发帖数: 47
2
我的理解是: 6位数总的排列是1000000(10^6)
两头相等的可能排列就是:
三个数字的情况,总和为0~27的方法为以上的卷积
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 63, 69, 73, 75, 75, 73, 69, 63, 55,
45,
36, 28, 21, 15, 10, 6, 3, 1
每种和的情况的排列有: x*x, 比如和为4,那么就有10x10种排列,
总的排列就是他说的“计算平方和为:55252”
t*******e
发帖数: 1633
3

我再看看,多谢

【在 s*******r 的大作中提到】
: 我的理解是: 6位数总的排列是1000000(10^6)
: 两头相等的可能排列就是:
: 三个数字的情况,总和为0~27的方法为以上的卷积
: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 63, 69, 73, 75, 75, 73, 69, 63, 55,
: 45,
: 36, 28, 21, 15, 10, 6, 3, 1
: 每种和的情况的排列有: x*x, 比如和为4,那么就有10x10种排列,
: 总的排列就是他说的“计算平方和为:55252”

1 (共1页)
进入JobHunting版参与讨论
相关主题
几年前G家onsite的一道题
被问到一个题目
三星面经
给你们出道中学数学题 (转载)
a question about combination
Google on campus 面经
题都感觉做对了,面试的人也满意,为什么二面过后还是直接悲剧呢……顺便上P面经
一道面试碰到的概率题
twitter intern面经
DP感受 (高手请绕行)
相关话题的讨论汇总
话题: 卷积话题: 数字话题: fft话题: 55252