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

技能

卡尔

冰墙

火人

113 条回复 • 2019-03-20 23:46:56 +08:00

1 2

❮

❯

1

lcatt

2019-03-19 10:48:08 +08:00

3

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

2

dinjufen

2019-03-19 10:59:14 +08:00

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

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

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

3

mskf

OP

2019-03-19 11:04:48 +08:00

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

4

codeless

2019-03-19 11:10:04 +08:00

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

5

coderluan

2019-03-19 11:15:15 +08:00

3

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

6

dinjufen

2019-03-19 11:15:59 +08:00

@mskf 嗯，是的

7

yhxx

2019-03-19 11:17:55 +08:00

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

8

calpes

2019-03-19 11:23:17 +08:00

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

9

WuwuGin

2019-03-19 11:27:24 +08:00

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

10

binux

2019-03-19 11:27:40 +08:00

3

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

11

mskf

OP

2019-03-19 11:30:43 +08:00

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

12

zxcvsh

2019-03-19 11:32:48 +08:00 via iPhone

10 楼结贴

13

coderluan

2019-03-19 11:38:14 +08:00

@calpes

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

14

mxalbert1996

2019-03-19 11:42:17 +08:00 via Android

5

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

15

coderluan

2019-03-19 11:42:32 +08:00

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

16

batman2010

2019-03-19 11:42:58 +08:00

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

17

nazor

2019-03-19 11:43:48 +08:00

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

18

coderluan

2019-03-19 11:48:30 +08:00

@mxalbert1996

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

19

blackjar

2019-03-19 11:53:42 +08:00

1

就是重复组合啊

20

1KN6sAqR0a57no6s

2019-03-19 11:54:46 +08:00 via Android

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

21

CastleBUPT

2019-03-19 12:01:03 +08:00

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

22

binux

2019-03-19 12:21:18 +08:00

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

23

chenno9

2019-03-19 13:30:06 +08:00

1

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)

24

calpes

2019-03-19 13:30:54 +08:00

2

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

25

Nathanzheng

2019-03-19 13:35:19 +08:00

2

rua?

26

mscststs

2019-03-19 13:37:26 +08:00 via Android

2

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

27

calpes

2019-03-19 13:43:42 +08:00

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

28

lychnis

2019-03-19 13:45:03 +08:00 via Android

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

29

shyrock

2019-03-19 13:49:41 +08:00

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

30

polo3584

2019-03-19 13:53:09 +08:00

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

31

coderluan

2019-03-19 14:06:03 +08:00

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

32

mskf

OP

2019-03-19 14:07:41 +08:00

1

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

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

33

mskf

OP

2019-03-19 14:08:19 +08:00

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

34

mskf

OP

2019-03-19 14:08:55 +08:00

@lychnis 只算个数

35

mskf

OP

2019-03-19 14:09:15 +08:00

@Nathanzheng rua

36

mskf

OP

2019-03-19 14:10:34 +08:00

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

37

maswang

2019-03-19 14:15:35 +08:00

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

38

lxy42

2019-03-19 14:31:48 +08:00

数学推导公式：
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

39

lostberryzz

2019-03-19 14:32:20 +08:00

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

40

mandy0119

2019-03-19 14:38:15 +08:00

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

41

jetyang

2019-03-19 14:39:11 +08:00

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

42

Ncanback

2019-03-19 14:46:33 +08:00

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

43

tohert

2019-03-19 14:50:03 +08:00

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

44

Arxz

2019-03-19 14:51:37 +08:00

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

45

justfan

2019-03-19 14:53:00 +08:00

```
#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);
}
}
}
}
```

46

mskf

OP

2019-03-19 15:00:55 +08:00

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

47

lxy42

2019-03-19 15:03:25 +08:00

python 的一个解法：

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

48

justfan

2019-03-19 15:05:05 +08:00

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

49

NBGGA

2019-03-19 15:08:33 +08:00 via Android

1

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

50

across

2019-03-19 15:10:29 +08:00

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

51

across

2019-03-19 15:11:35 +08:00

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

52

isaacpei

2019-03-19 15:22:03 +08:00

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

53

Vitta

2019-03-19 15:26:54 +08:00

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

54

VoidChen

2019-03-19 15:56:31 +08:00

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

55

VoidChen

2019-03-19 15:58:20 +08:00

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

56

VoidChen

2019-03-19 16:03:31 +08:00

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

57

ccpp132

2019-03-19 16:06:33 +08:00

1

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

58

ccpp132

2019-03-19 16:10:15 +08:00

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

59

VagrantSven

2019-03-19 16:16:27 +08:00 via Android

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

60

Ginray

2019-03-19 16:17:44 +08:00

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

61

SakuraKuma

2019-03-19 16:33:40 +08:00

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

62

zqx

2019-03-19 16:37:42 +08:00 via Android

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

63

Rhonin

2019-03-19 16:59:06 +08:00

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

64

zzzzzzZ

2019-03-19 17:01:03 +08:00

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

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

65

chenno9

2019-03-19 17:02:51 +08:00

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

66

linchengzzz

2019-03-19 17:09:09 +08:00

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

67

a728976009

2019-03-19 17:11:35 +08:00

1

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

68

jk1030

2019-03-19 17:22:05 +08:00

1

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

69

KevinBu

2019-03-19 17:41:12 +08:00

python 两行代码搞定 🤩

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

70

mskf

OP

2019-03-19 18:03:13 +08:00

@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;
}
```

71

newtype0092

2019-03-19 18:15:44 +08:00

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

72

JohnSmith

2019-03-19 18:35:09 +08:00

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

73

JohnSmith

2019-03-19 18:36:08 +08:00

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

74

HeavenlyChorus

2019-03-19 18:51:32 +08:00 via Android

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

75

choice4

2019-03-19 18:59:15 +08:00 via Android

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

76

JohnSmith

2019-03-19 19:00:46 +08:00 via iPhone

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

77

liyuhang

2019-03-19 19:15:20 +08:00

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

78

jiajia94

2019-03-19 19:27:46 +08:00

别问，问就是高等级天火

79

coderluan

2019-03-19 19:33:55 +08:00

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

80

linchengzzz

2019-03-19 19:35:57 +08:00

@choice4 FiraCode 字体

81

trcnkq

2019-03-19 19:42:37 +08:00

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

82

jin5354

2019-03-19 19:53:30 +08:00

1

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

83

siyemiaokube

2019-03-19 20:16:39 +08:00 via iPhone

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

84

siyemiaokube

2019-03-19 20:23:13 +08:00 via iPhone

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

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

85

staticer

2019-03-19 20:25:35 +08:00

![Test](

)

86

HeavenlyChorus

2019-03-19 20:42:11 +08:00 via Android

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

87

atVoid

2019-03-19 21:02:06 +08:00

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

88

NullPoint

2019-03-19 21:03:25 +08:00 via Android

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

89

whi147

2019-03-19 21:13:38 +08:00 via Android

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

90

seraphv3

2019-03-19 21:32:07 +08:00

4

有 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 可以实现它

91

calpes

2019-03-19 22:06:05 +08:00

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

92

mxalbert1996

2019-03-19 22:23:01 +08:00 via Android

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

93

laydown

2019-03-20 00:40:19 +08:00

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

重复组合的概念。

94

ihciah

2019-03-20 03:12:56 +08:00 via iPhone

卡特兰数？

95

mingl0280

2019-03-20 04:07:13 +08:00

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

96

mingl0280

2019-03-20 04:11:27 +08:00

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

97

Variazioni

2019-03-20 08:40:09 +08:00

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

98

graysheeep

2019-03-20 09:17:27 +08:00

qqwrv

99

coderluan

2019-03-20 10:19:36 +08:00

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

100

coderluan

2019-03-20 10:23:54 +08:00

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

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

1 2

❮

❯