由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 问一道题
相关主题
求一道 概率题返回字符串所有的 combination
问一道老题求offer比较
问一道题伪O(1) space的O(n)时间重新排列a1a2a3...b1b2b3...算法
狗的host match是怎么match的问个算法题9
Two sigma的online code test有人做吗one interview question, very difficult, smart people can do
2 Sigma的onsite面经Jane Street 面经
[合集] 贡献一道it面试题一个来源于生活的简单数学题
求助 字符串交叉生成的问题报个T家的电面据
相关话题的讨论汇总
话题: a1话题: a1a2a3话题: a1a2话题: 1a话题: a2
进入JobHunting版参与讨论
1 (共1页)
l***r
发帖数: 241
1
给一个字符串 A1A2A3..An how may key combinations
for example:
N = 1:
A1 -> A1
N = 2:
A1 -> A1
A2 -> A2
A1A2 -> A1
A1A2 -> A2
A1A2 -> A1A2
证明如果字符串长度是N。 组合的数目是3^n - 2^n
f*******4
发帖数: 64
2
g(A_1A_2..A_kA_k+1) = g(A_1A_2..A_k)+g(A_k+1)+g(A_1A_2..A_k).(A_k+1)
= 2*g(A_1..A_k)+1
=> g(A_1..A_k)=2^k-1,记作g(k)
f(A_1..A_k)= g(1)*C(k,1)+..g(i)*C(k,i)+g(k)*C(k,k)
= sigma(2^i * C(k,i)) - sigma(C(k, i))
= (1+2)^k-(1+1)^k
f*****h
发帖数: 10
3
a[n+1] = a[n] + 2a[n] + 2^n
c***d
发帖数: 26
4
这题啥意思呀?没看懂。什么是key combinations?
没从N=2的例子里看出规律猜出题意。
能不能给个N=3的例子?
底下两位回复也没看懂。

【在 l***r 的大作中提到】
: 给一个字符串 A1A2A3..An how may key combinations
: for example:
: N = 1:
: A1 -> A1
: N = 2:
: A1 -> A1
: A2 -> A2
: A1A2 -> A1
: A1A2 -> A2
: A1A2 -> A1A2

d****n
发帖数: 233
5
看了半天, 原来是在考高中(还是初中, 忘了)数学 二项式展开公式。
(m+n)^k = sigma(C(k,i)*m^i*n^(k-i) i = 0… k
g(A_1..A_k)=2^k-1, 可以这样理解:
A1…A_k中每一个要么被选中, 要么不被选, 所以总共是2^k种组合, 需要减去一个
也没有选中的情况。 So。g(A_1..A_k)=2^k-1
比如k = 3:
A1A2A3=> A1
A1A2A3=> A2
A1A2A3=> A3
A1A2A3=> A1A2
A1A2A3=> A1A3
A1A2A3=> A2A3
A1A2A3=> A1A2A3
假设原数组有n个, 那么从n个中选出k个有C(n, k)种可能。 So, 总数是:
f(A_1..A_n)= g(1)*C(n,1)+..g(i)*C(n,i)+g(n)*C(n,n)
= sigma(2^i * C(n,i)) - sigma(C(n, i))
= (1+2)^n-(1+1)^n

【在 c***d 的大作中提到】
: 这题啥意思呀?没看懂。什么是key combinations?
: 没从N=2的例子里看出规律猜出题意。
: 能不能给个N=3的例子?
: 底下两位回复也没看懂。

1 (共1页)
进入JobHunting版参与讨论
相关主题
报个T家的电面据Two sigma的online code test有人做吗
G : 抛硬币问题2 Sigma的onsite面经
G家onsite面经(感谢放水的国人大哥)[合集] 贡献一道it面试题
谈谈面试技巧求助 字符串交叉生成的问题
求一道 概率题返回字符串所有的 combination
问一道老题求offer比较
问一道题伪O(1) space的O(n)时间重新排列a1a2a3...b1b2b3...算法
狗的host match是怎么match的问个算法题9
相关话题的讨论汇总
话题: a1话题: a1a2a3话题: a1a2话题: 1a话题: a2