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

2019-03-19 10:33:27 +08:00
 mskf

是这样的,如果你玩过 dota2 的话,很简单一句话,n 个球的卡尔有多少个技能

没玩过的话,大概介绍一下,卡尔有三个球,冰球 Q,雷球 W,火球 E,不同的组合对应不同的技能 QQQ (极冷),QQW (峰哥漫步),QQE (冰墙),WWW (磁暴),WWQ (吹风),WWE (灵动迅捷),EEQ (火人),EEW (陨石),EEE (天火),QWE (推波)一共十个技能(不算天赋)

所以说如果卡尔有 4 个球,或者 n 个球,他会有几个技能呢

16221 次点击
所在节点    职场话题
113 条回复
lcatt
2019-03-19 10:48:08 +08:00
高中排列组合。。。怎么可能有这么简单的面试题
dinjufen
2019-03-19 10:59:14 +08:00
玩过 dota2.试着答一下:
假如卡尔只能有三个框,n 个球(即一个技能含且只含三个球),那么他的技能数等于:
n (一个技能由同一种球构成,如 QQQ ) + 2n (一个技能由两种球构成,如 QQW ) + A3n (排列公式,一个技能由三种球构成,如 QWE )

当然有另一种情况就是有 n 个球,并且有 n 个框:
结果应该是 C1n + C2n + ... + Cnn (组合公式)

若有问题,欢迎指出。。。
mskf
2019-03-19 11:04:48 +08:00
@dinjufen 一种组合有不同的排列方式,比如 n=4,C2,4=6 但这六种组合每种对应的技能并不止一种:
QQWW,QQQW,WWWQ 这就三种了
codeless
2019-03-19 11:10:04 +08:00
emm,想象了一下 n ( n>104 )个键的键盘。。。
coderluan
2019-03-19 11:15:15 +08:00
这题肯定是高中数学题,但是如果你想到的是高中算法,而不是递归树或者二进制的话,对程序员来说,这题你就算不回。
dinjufen
2019-03-19 11:15:59 +08:00
@mskf 嗯,是的
yhxx
2019-03-19 11:17:55 +08:00
@mskf 可是 WWQ 和 QWW 确实是同一个技能啊(逃
calpes
2019-03-19 11:23:17 +08:00
@coderluan 这是什么说法。。。有更高级的数学证明不能用还非得用递归了?
WuwuGin
2019-03-19 11:27:24 +08:00
我就提醒一句组合相同排列不同算同一种技能哦。
binux
2019-03-19 11:27:40 +08:00
看回复这题还真的能筛选候选人
mskf
2019-03-19 11:30:43 +08:00
@coderluan 我一开始也是这么想的,想了好久硬是没有想到怎么用 dp 做,后来尝试了一下用纯数学,很简单就搞定了
zxcvsh
2019-03-19 11:32:48 +08:00
10 楼 结贴
coderluan
2019-03-19 11:38:14 +08:00
@calpes

第一,你要理解面试官的意图,你认为对方是想考你高中数学,还是更想考你编程技巧?
第二,算法很大程度是在解决数学的性能问题,相辅相成的东西,何来的”更高级“?,你随便找一个常用的库,你看看里面的实现是用算法,还是用公式?
mxalbert1996
2019-03-19 11:42:17 +08:00
@coderluan 我觉得你根本就没理解算法是个什么东西。
coderluan
2019-03-19 11:42:32 +08:00
PS:有兴趣的同学,可以看看 STL 里面的 permutation 实现,按这个答基本大部分面试官自己就跪了。
batman2010
2019-03-19 11:42:58 +08:00
@coderluan #13 用排列组合的方法也只是用到简单的乘除法。
nazor
2019-03-19 11:43:48 +08:00
1*n + 2*(n-1) + 3*(n-2) + ... + n*1
coderluan
2019-03-19 11:48:30 +08:00
@mxalbert1996

我只是表面自己观点,给出自己的证据,如果你认为有问题,也可以表面观点和证据,然后咱们交流和讨论。但是你发的这句话,我只能说我觉你根本没理解沟通是个什么东西。
blackjar
2019-03-19 11:53:42 +08:00
就是重复组合啊
1KN6sAqR0a57no6s
2019-03-19 11:54:46 +08:00
想起了七年前的夏天我在家里的凉席上用纸笔算卡尔有多少技能。

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/546059

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX