前两天看到一道小米的面试题

mskf · 2019-03-19T02:33:27Z

是这样的，如果你玩过 dota2 的话，很简单一句话，n 个球的卡尔有多少个技能没玩过的话，大概介绍一下，卡尔有三个球，冰球 Q，雷球 W，火球 E，不同的组合对应不同的技能 QQQ （极冷）,QQW （峰哥漫步）,QQE （冰墙）,WWW （磁暴）,WWQ （吹风）,WWE （灵动迅捷）,EEQ （火人）,EEW （陨石）,EEE （天火）,QWE （推波）一共十个技能（不算天赋）所以说如果卡尔有 4 个球，或者 n 个球，他会有几个技能呢

技能

卡尔

冰墙

火人

113 replies • 2019-03-20 23:46:56 +08:00

1 2

❮

❯

lcatt

Mar 19, 2019

3

1

高中排列组合。。。怎么可能有这么简单的面试题

dinjufen

Mar 19, 2019

2

玩过 dota2.试着答一下：
假如卡尔只能有三个框，n 个球（即一个技能含且只含三个球），那么他的技能数等于：
n （一个技能由同一种球构成，如 QQQ ） + 2n （一个技能由两种球构成，如 QQW ） + A3n （排列公式，一个技能由三种球构成，如 QWE ）

当然有另一种情况就是有 n 个球，并且有 n 个框：
结果应该是 C1n + C2n + ... + Cnn （组合公式）

若有问题，欢迎指出。。。

mskf

OP

Mar 19, 2019

3

@dinjufen 一种组合有不同的排列方式，比如 n=4，C2,4=6 但这六种组合每种对应的技能并不止一种：
QQWW,QQQW,WWWQ 这就三种了

codeless

Mar 19, 2019

4

emm，想象了一下 n （ n>104 ）个键的键盘。。。

coderluan

Mar 19, 2019

3

5

这题肯定是高中数学题，但是如果你想到的是高中算法，而不是递归树或者二进制的话，对程序员来说，这题你就算不回。

dinjufen

Mar 19, 2019

6

@mskf 嗯，是的

yhxx

Mar 19, 2019

7

@mskf 可是 WWQ 和 QWW 确实是同一个技能啊（逃

calpes

Mar 19, 2019

8

@coderluan 这是什么说法。。。有更高级的数学证明不能用还非得用递归了？

WuwuGin

Mar 19, 2019

9

我就提醒一句组合相同排列不同算同一种技能哦。

binux

Mar 19, 2019

3

10

看回复这题还真的能筛选候选人

mskf

OP

Mar 19, 2019

11

@coderluan 我一开始也是这么想的，想了好久硬是没有想到怎么用 dp 做，后来尝试了一下用纯数学，很简单就搞定了

zxcvsh

Mar 19, 2019 via iPhone

12

10 楼结贴

coderluan

Mar 19, 2019

13

@calpes

第一，你要理解面试官的意图，你认为对方是想考你高中数学，还是更想考你编程技巧？
第二，算法很大程度是在解决数学的性能问题，相辅相成的东西，何来的”更高级“？，你随便找一个常用的库，你看看里面的实现是用算法，还是用公式？

mxalbert1996

Mar 19, 2019 via Android

5

14

@coderluan 我觉得你根本就没理解算法是个什么东西。

coderluan

Mar 19, 2019

15

PS：有兴趣的同学，可以看看 STL 里面的 permutation 实现，按这个答基本大部分面试官自己就跪了。

batman2010

Mar 19, 2019

16

@coderluan #13 用排列组合的方法也只是用到简单的乘除法。

nazor

Mar 19, 2019

17

1*n + 2*(n-1) + 3*(n-2) + ... + n*1

coderluan

Mar 19, 2019

18

@mxalbert1996

我只是表面自己观点，给出自己的证据，如果你认为有问题，也可以表面观点和证据，然后咱们交流和讨论。但是你发的这句话，我只能说我觉你根本没理解沟通是个什么东西。

blackjar

Mar 19, 2019

1

19

就是重复组合啊

1KN6sAqR0a57no6s

Mar 19, 2019 via Android

20

想起了七年前的夏天我在家里的凉席上用纸笔算卡尔有多少技能。

CastleBUPT

Mar 19, 2019

21

是从 n 个球选 3 个排技能吗，是的话，C1n + 2*C2n + C3n

binux

Mar 19, 2019

22

@mskf #11 dp 就是 f = lambda m, n: sum(f(i+1, n-1) for i in range(m)) if n > 1 else m

chenno9

Mar 19, 2019

1

23

f(4)=c(1,4)*c(3,3)+c(2,4)*c(2,3)+c(3,4)*c(1,3)+c(4,4)*c(0,3)=35

f(n)=c(1,n)*c(n-1,n-1)+c(2,n)*c(n-2,n-1)+c(3,n)*c(n-3,n-1)+...+c(n,n)*c(n-n,n-1)

calpes

Mar 19, 2019

2

24

@coderluan 不是这个说法吧。。。很多库的实现里都直接用了 magic number，这显然是数学范围的优化啊，在有更高级数学模型的情况下还强行上递归，这并不是明智的行为，你不能因为通常情况下可能找不到更简洁的数学模型，就在能找到的时候不用啊，更何况大多数情况下只是由于工程师的数学水平不够，而不是没有相关的数学模型。

Nathanzheng

Mar 19, 2019

2

25

rua?

mscststs

Mar 19, 2019 via Android

2

26

算法不就是为了更高效地解决问题吗？递归全排有数学公式来得高效？

calpes

Mar 19, 2019

27

@coderluan 就比如一个穷举素数的算法，一般来说实现中对素数的判断条件都是如果除数大于结果就认为这是一个素数，这明显是数学理论的支持啊

lychnis

Mar 19, 2019 via Android

28

只算个数还是输出所有这可不一样

shyrock

Mar 19, 2019

29

说实话题没理解清楚，为啥 3 个球只有 10 种技能？ EWQ 这种为啥没有？

polo3584

Mar 19, 2019

30

@shyrock EWQ 就是 QWE，这个不算排序的

coderluan

Mar 19, 2019

31

@calpes 我说那个只是反驳数学证明就高级，实际上哪个性能好用哪个，随便找个库肯定也有公式的，这个点我不严谨。而且我也并没有强行上递归，而是说面试程序员出这题，面试官应该是想要递归之类的算法相关的回答，而不是高中数学。

mskf

OP

Mar 19, 2019

1

32

@chenno9 正解，f(x)=∑C(i,x)*C(i-1,x-1)(0<i<x)

这题用 dp 做简直没法做，偏偏还挺容易想歪的

mskf

OP

Mar 19, 2019

33

@shyrock EWQ=QWE，如果不考虑顺序的话就太简单了，直接 n^n

mskf

OP

Mar 19, 2019

34

@lychnis 只算个数

mskf

OP

Mar 19, 2019

35

@Nathanzheng rua

mskf

OP

Mar 19, 2019

36

@mscststs 这题如果想用数学公式以外的方式去解决，很容易想歪，如果现场写代码的话排列组合的优化还是有地方可以写的

maswang

Mar 19, 2019

37

我不知道是多少，但是我知道怎么写个程序帮我算出来

lxy42

Mar 19, 2019

38

数学推导公式：
f(n) = 1 + n * [C(1, n-1) + C(2, n-1) + ... + C(n-1, n-1)]

f(3) = 1 + 3 * [C(1, 2) + C(2, 2)] = 1 + 3 * [2 + 1] = 10
f(4) = 1 + 4 * [C(1, 3) + C(2, 3) + C(3, 3)] = 1 + 4 * [3 + 3 + 1] = 29

lostberryzz

Mar 19, 2019

39

肯定是推公式效率高啊。。

mandy0119

Mar 19, 2019

40

1234 => 0 空位，1 空位（ 2 种球），2 空位（ 2 种球），3 空位（ 2 种球）。虽然规律出来了，但是我没总结出来公式

jetyang

Mar 19, 2019

41

说写程序的可以歇歇了，这是笔试里的一道选择题。正解 @chenno9 已经给出来了，当然还有更简洁的通项表达，多看看组合数学和概率论呗

Ncanback

Mar 19, 2019

42

排列组合的典型为什么会想到用回调递归？

tohert

Mar 19, 2019

43

我怎么想到的是笛卡尔乘积。。。

Arxz

Mar 19, 2019

44

只会用 dp...排列组合想了半天没想出来

justfan

Mar 19, 2019

45

```
#include "stdio.h"
void main()
{
char a[3] = {'q', 'w', 'e'};
int i,j,k;
char tmp1, tmp2, tmp3;
for(i=0;i<3;i++)
{
tmp1 = a[i];
for(j=i;j<3;j++)
{
tmp2 = a[j];
for(k=j;k<3;k++)
{
tmp3 = a[k];
printf("%c%c%c\n", tmp1, tmp2, tmp3);
}
}
}
}
```

mskf

OP

Mar 19, 2019

46

@justfan 3^3=27>10，所以有重复的，面试题一般不会考这么简单的三重循环

lxy42

Mar 19, 2019

47

python 的一个解法：

https://gist.github.com/ausaki/4219b54eb54654216008103c30d93f72

justfan

Mar 19, 2019

48

@mskf 不是三重循环 for(j=i;j<3;j++) for(k=j;k<3;k++)

NBGGA

Mar 19, 2019 via Android

1

49

你以为他们想考你算法，其实他们只想招个 DotAer🤣

across

Mar 19, 2019

50

https://leetcode-cn.com/problems/combinations/

across

Mar 19, 2019

51

@across 啊，我忘了，卡尔技能是没有顺序关系的

isaacpei

Mar 19, 2019

52

居然没人发 oeis??? 我来补上 http://oeis.org/A001700

Vitta

Mar 19, 2019

53

1 技能加攻击，2 技能加速度，3 技能加回血

VoidChen

Mar 19, 2019

54

那啥，我没玩过 dota，但是我看你们的描述，你们可能搞错了一点东西，n 个球，有没有限制球能不能重复用，另外就是 n 个球都是什么球，比如 n 个都是冰球，当 n > 2 的时候 1 个技能。我觉得这道题有点问题吧，跟 N 的关系好像就只是是不是＞ 2 了？

VoidChen

Mar 19, 2019

55

@VoidChen 或者说 n/3 个技能。。。。。。。。

VoidChen

Mar 19, 2019

56

不好意思，，就是排列组合。。我把这道题的意思想成 LOL 的波珠妹了，以为一共就 3 种球。。。。。

ccpp132

Mar 19, 2019

1

57

n 种球每次 m 个就是 C(n + m -1, n)....
高中组合数学知识其实够用了
相当于 x1 + x2 + ... + xn = m 的正整数解的个数，把 m - 1 个隔板和 n 个球放到一起排

ccpp132

Mar 19, 2019

58

@mskf @chenno9 帮你们化简了，比较好手算，滑稽

VagrantSven

Mar 19, 2019 via Android

59

7C3=35，七个球涂黑三个球当分割

Ginray

Mar 19, 2019

60

@chenno9 请问 c(n-n,n-1) 这个是代表什么意思，谢谢

SakuraKuma

Mar 19, 2019

61

#57+1
H(n,n)..

zqx

Mar 19, 2019 via Android

62

像是 100 只老鼠用最少几次可以试出毒的那个题吧？二进制串来表示，最后取并集？

Rhonin

Mar 19, 2019

63

@NBGGA #49 你这才是正解哈哈哈

zzzzzzZ

Mar 19, 2019

64

@coderluan #13
面试官的意图这一道题我是没看出来，但是做道题都舔的面试者的意图我看得很明显

是闹哪样，立直要当上面试王的男人吗

chenno9

Mar 19, 2019

65

@Ginray n 种颜色的取法*这 n 种颜色的组合我这里写反了应该是 32 楼的公式

linchengzzz

Mar 19, 2019

66

23 正解啊 , 我不信还手算了一遍

a728976009

Mar 19, 2019

1

67

https://baike.baidu.com/item/%E9%87%8D%E5%A4%8D%E7%BB%84%E5%90%88/6774375

jk1030

Mar 19, 2019

1

68

你们啊 naive 点完天赋还有一个毁天灭地这个东西考察得不是算法而且对公司产品得服从度

KevinBu

Mar 19, 2019

69

python 两行代码搞定 🤩

for i in itertools.permutations('qwer', 4):
print(''.join(i))

mskf

OP

Mar 19, 2019

70

@justfan 哦哦，不好意思没注意，感谢你给了我一点启发，不使用递归也是可以实现的：
```java
public int solution2(int n){
int res = 0;
int x=n-1,y=0,level = 0;
int prev[] = new int[n];
while (true){
if(x==0 && y==n) {
prev[x] = ++level;
if (level==n) break;
} else if(x<n-1) {
if(y==n)
y=++prev[--x];
else {prev[x+1] = prev[x];x++;}
} else if(x==n-1) {
res++;
if(y<n-1) y++;
else y=++prev[--x];
}
}
return res;
}
```

newtype0092

Mar 19, 2019

71

@coderluan 算法题不懂数学原理，只会用数据结构低效的模拟，难道不是水平 low 的表现么？程序员思维是用高效的方法解决问题，而不是只会用固定的套路。。。

JohnSmith

Mar 19, 2019

72

@KevinBu #69 你这个完美的把有重复部分的技能去掉了，e.g. wwww

JohnSmith

Mar 19, 2019

73

@KevinBu #69 还把同样字母的不同顺序的也算进去了

a1rchrysalis

Mar 19, 2019 via Android

74

只想说一句 r-combination 的 r 应该是写在后面的，如此:C(n,r),楼上几位都写反了

JohnZorn

Mar 19, 2019 via Android

75

@linchengzzz 你这个等号是什么科技？

JohnSmith

Mar 19, 2019 via iPhone

76

n = 球种类 k = 组合长度
C(n,1)+c(n,2)+...+c(n,k)

liyuhang

Mar 19, 2019

77

@choice4 #75 https://github.com/tonsky/FiraCode

jiajia94

Mar 19, 2019

78

别问，问就是高等级天火

coderluan

Mar 19, 2019

79

@newtype0092 我说的是只是高中水平的数学是没办法让面试官满意的，你怎么推理出“不懂数学原理，只会数据结构”的？喵喵喵？

linchengzzz

Mar 19, 2019

80

@choice4 FiraCode 字体

trcnkq

Mar 19, 2019

81

(n+2)*(n+1)/2

jin5354

Mar 19, 2019

1

82

f(n) = C(n-1, 2n-1)
查了下资料，这种解法真是太巧了，f(4) = C(3, 7) = 35

siyemiaokube

Mar 19, 2019 via iPhone

83

高中 oi 选手让各位再感受一些压力吧(◐‿◑)
上面说到的 C(n-1, 2n-1)，其实可以再展开说好多，不妨从“生成函数”入手查一些资料

siyemiaokube

Mar 19, 2019 via iPhone

84

@HeavenlyChorus
>只想说一句 r-combination 的 r 应该是写在后面的，如此:C(n,r),楼上几位都写反了

“ C ”这种苏式组合数记法，一般默认上标在前下标在后。美式的括号记法，确实是(n,r)

staticer

Mar 19, 2019

85

![Test](

)

a1rchrysalis

Mar 19, 2019 via Android

86

@siyemiaokube 学习了我学校教的是我说的那样

atVoid

Mar 19, 2019

87

有放回组合问题，推导挺有意思的。https://zhuanlan.zhihu.com/p/33841038 C(n+m-1,n-1) n 个球 m 个框(盒子)

NullPoint

Mar 19, 2019 via Android

88

没太懂，QQE EQQ QEQ EEQ EQE QEE，算俩技能

whi147

Mar 19, 2019 via Android

89

(r+n-1)!/r!(n-1)! r=4 n=4

seraphv3

Mar 19, 2019

4

90

有 3 个按键，QWE，需要按 3 次，相当于把 3 个球（ 3 次按键的动作）放到 3 个盒子（ QWE ）中，找出可区分的排布数。
3 个盒子有 2 个隔板，这 2 个隔板和 3 个球一起就有 5 个位置，5 个位置中任选 2 个放隔板，其他的就是球，所以就是 C(2,5)
Q W E
|x |x |x |
|xx |x | |
|x |xx | |
...
|xxx| | |
| |xxx| |

PS:盒子中放球的模型不像想象的那么简单，统计力学里面有 Maxwell-Boltzmann 统计（比如气体分子）、Fermi-Dirac 统计（比如电子）、Bose-Einstein 统计（比如光子），用这道题的统计方式来统计样本空间（不同的排布是可区分的）就对应于 Bose-Einstein 统计，有一个简单的 Polya ’ s urn model 可以实现它

calpes

Mar 19, 2019

91

@coderluan 其实我是这么理解的，一定的数学基础是合格程序员的先决条件，如果你没有高中水平的数学知识，你根本不可能是一个合格的程序员，如果我是面试官(事实上我确实是)，我一定不会给一个没有数学常识的人任何机会。

mxalbert1996

Mar 19, 2019 via Android

92

@coderluan 因为你让我觉得没有跟你沟通的必要。一个对算法稍微有点理解的人也至少不会把算法和公式对立起来。

laydown

Mar 20, 2019

93

如果 4 个球的话，按 1 个键就是 4 种，按 2 个键，就是 10 种，按 3 个键就是 20 种，按 4 个键就是 35 种，合起来就是 4+10+20+35，共 69 种。

重复组合的概念。

ihciah

Mar 20, 2019 via iPhone

94

卡特兰数？

mingl0280

Mar 20, 2019

95

@lxy42 O(n^4)的算法和数学的 O(1)的算法，是正常人都知道该用啥……

mingl0280

Mar 20, 2019

96

@coderluan 这道题只需要高中水平的数学知识，如果你连这点知识都没有，最好别称自己为程序员，笑掉大牙的。

Variazioni

Mar 20, 2019

97

这年头没玩过 dota2 都不能去小米了？

graysheeep

Mar 20, 2019

98

qqwrv

coderluan

Mar 20, 2019

99

@calpes 是啊，所以我说的一直都加上了， “更” “不能满足”“没谁高级”“相辅相成” ，不知道你们咋理解的成我吹算法捧数学的。

coderluan

Mar 20, 2019

100

@mxalbert1996 是有人先说的数学更高级，我反驳他时明确用了“相辅相成的东西，何来的”更高级“？”#13

你还能理解成我把“算法和公式对立”。我也不知道咋和你沟通了。再送你句 “我只能说我觉你根本没理解语文是个什么东西”。

1 2

❮

❯