字节跳动面试真题——史莱姆变形计

转自知乎：老钱

本文的主人公叫「苟史韵」，他最近参与了字节跳动面试，遭遇了一道非常困惑的面试题

面试官出题

------------------------------------------------

有三种形状的史莱姆，分别是三角形、四边形和圆形，它们各有 10、14、15只。这些史莱姆有一个奇怪的特性，那就是两种不同形状的史莱姆碰到一起将会变身成第三种形状。比如一个三角形的史莱姆和一个四边形的史莱姆配对在一起会变成两只圆形的史莱姆。请设计出一套配对方法让这些史莱姆变身成一种形状。

苟史韵看了这道题后，开始陷入了沉思，但是时间不等人，很快 10 分钟过去了，完全找不到思路，脑子里各种形状在变来变去就是变不出最终的目标形状。虽然很捉急但是没有办法于只好叹气作罢对面试官回道：解不出来。这一声叹气仿佛便秘了很久，最终还是不得不借助于开塞露。

面试官面露喜色，似乎满脸都是一副鄙夷的神色。小白心想：这下完蛋了。但是接下来面试官说到：恭喜你，答对了，此题没有解。因为时间有限，我们就不继续讨论这道题了，下面我们看下一道题。。。

只见小白的表情从失望变化到愕然，但是很快又恢复到了愉悦平静。面试结束后，他依旧蒙在鼓里：我到底是怎么搞定这道题的？

------------------------------------------------------------

本题的关键在于寻找到一个特别的「不变量」来求解。我们注意到在史莱姆配对时，两种形状的数量会减一，第三种形状的数量会加二。那么这两个数量减一的史莱姆之间的数量变化差值会保持不变（因为同时减一）。同时这第三种形状和前两种形状之间的数量变化差值会是三的倍数（一个减一，一个加二）。再进一步讲，经过多轮配对之后，这三个形状之间的数量变化差值 对 3 取余，结果将会保持为「零」。这就是本题的关键「不变量」，这种「不变量」自始至终都在制约着三种形状之间的变化关系。

再回到本题的三个数字，10、14、15，它们之间的差值对 3 取余并不是「零」。但是目标状态0、0、39，它们之间的差值对 3 取余却是「零」。所以本题显然无解。

聪明的小伙伴们，你们的答案是这样吗？