最近参加了联想AI研究院的面试（岗位自然语言处理），除了问到简历中项目以及简单的机器学习问题外，还问了3道算法题，并且都不是拿到马上就能反应出来解法的题目（也可能是本人经验尚缺）。特记录面试过程和题目分析如下，由于没有标答，我想到的解法仅是抛砖引玉，欢迎大家一起探讨。
短暂的简历讨论后，面试官抛出题目1：
题目1：一个矩形边长为x、y，都是正整数（但其大小关系未知），将其分割成若干小正方形，每个小正方形边长可互不相等但需要都为正整数。如何划分使得这些小正方形的边长之和最小？
面试思路：首先想到既然是考算法题，那么不外乎分治法、动态规划、贪心、回溯等等几种。如果要把一个矩形切分成正方形，并且恰好全部切分干净，那么最差的一种方法是全部分解成边长为1的小正方形，这样由于共有xy个正方形，则边长和为xy。
再考虑是否有更好的解法。考虑一个2x2的正方形，若作为一个整体，则边长为2；若分解成4个1x1的小正方形，边长和变成4。这提示我们分割时尽量分出更大的正方形。
由此想到贪心法：分解方法为：程序每次分出当前能分割的边长最大的正方形，若已全部分完，则程序结束；若还有剩余的部分，则对剩余部分再继续按这个方法分解。向面试官描述该思路后，面试官肯定了该思路并又提出如下两个问题：
题目1.1：求出边长之和的最小值
题目1.2：证明贪心策略的正确性
对于这两个子问题，面试官大概分别给出5分钟的时间，面试现场都没有做出来，回来后经过思考总结如下：
1) 由于面试时考虑复杂了，一直在研究x和y之间数量关系。回来后发现对于1.1这类题目要在短时间内做出来最好的方法是进行试探法。例如我先考虑1xn的情况，那么当然是只能分成n个1x1的正方形，这种情况下边长和为n。再考虑2xn的情况，这时需要考虑n为奇数或偶数。若n为偶数，则分成n/2个2x2的正方形，边长和为n；若n为奇数，分成(n-1)/2个2x2加2个1x1，边长和为n+1。最后考虑原始形状就是nxn的正方形，当然是不分割，边长和为n。将这些特殊情况整理如下：
| 矩形边长 |
分割小正方形边长和 |
| 1xn |
n |
| 2xn(n为偶数) |
n |
| 2xn(n为奇数) |
n+1 |
| nxn |
n |
若对数据敏感马上可以发现，边长和与x和y的最大公约数有关。设最大公约数位m，则边长和为 x + y - m
在面试时给出这个结果相信已经足够了，如果面试官要求证明，则可以由上表中把n分成奇数和偶数的思路用数学归纳法证明。例如：继续控制某一条边为n不变，另一条边从2变成3，则有n%3 == 0, n%3 == 1, n%3 == 2三种情况，经过计算可以发现，对n%3==0是最大公约数为3，后两种情况是最大公约数为1，都满足猜测的公式。可继续由数学归纳法推广到 mxn 的情况。
2) 证明贪心法的正确性，贪心的证明一般都采用数学归纳法，并且最不好想的地方是需要先叙述一个可以用数学归纳法证明的命题。记得教材中给出的常用论证方法有替代论证和交换论证，但面试时实在是绞尽脑汁也想不出如何证明。
回来后突然想到了经典的贪心问题：找零钱问题（即用几种面值的钱币组成一定的金额，怎样能用最少的钱数），按照生活常识即可知道优先使用大额的钱币，从大到小即可。这个分割矩形的题目有点像是找零钱问题的二维版本，即每个币值的钱数具有不同的重量，并非要使得钱币的数量最少而是使得重量最轻。这个题目的解法是先对价值/重量进行排序，优先选择单位重量价值最大的，但并不保证能适用贪心策略，只有满足一定条件时才能使用。
对于这个题目来说，正方形的面积可以理解为价值，边长可以理解为重量，需要找的是总重量最小的解。直观上可以按照面积/边长进行排序，当然是边长越大的正方形这个值越大，所以优先分解最大的正方形。但严格的证明过程还没想出。
题目1的解决并不完美，面试官追加了题目2。
题目2：已知 ∑xi = M为已知正整数，请求出∏xi 的最大值。
面试思路：拿到这题后先是懵了几秒，理清思路后由于面试前刷过《剑指offer》，发现该题与该书上面试题14：剪绳子十分相似（对一根长度为n的绳子，把绳子剪成若干段，使每段长度乘积最大）。绳子剪成若干段等价于∑xi = M，求每段长度乘积等价于∏xi ，于是直接说出思路如下：
当M小于或等于4时，不进行分解，乘积即为自身。当M大于4时，全部分解成2和3，且尽量分解为3，仅当M%3 == 1的时候，由于会剩余一个1，就把一个1和一个3替换成两个2。按该种方法分解乘积最大。
此时面试官要求说出证明过程，简要阐述如下：（这部分过程其实《剑指offer》上讲的并不清晰完备）
1) 首先证明对于小于等于4的情况任何分解均不会产生更好的结果，这部分证明很简单
2) 证明对于M大于4时，应该优先分解为2和3。假设有一个4，这时可以分解成2+2，并且乘积结果是相同的，不会比原情况更糟。对于有一个5的情况，当分解为2+3时，可以有更好的乘积（2x3 > 5），因此全部分解为2和3是最好的选择
3) 再研究2和3谁更好的问题。当M大于4时，分解一个2出来得到的乘积是2(M-2)，分解一个3出来得到的乘积是3(M-3)，经过简单的不等式比较可以发现3(M-3) >= 2(M-2)，可以得知应该优先分解为3。但有一种特殊情况需要处理，即最后剩一个1的情况。由于1x3 < 2x2，应该更换成两个2
向面试官描述上述思路后，面试官提出一个问题：
3(M-3) >= 2(M-2)当然是对的，但你怎么知道剩余的两个子结构中M-3的最优解一定不会比M-2的最优解差？换句话说有没有可能M-2的最优解大于M-3最优解的1.5倍？
由于《剑指offer》看的比较粗糙，没有深入思考，这个问题没有回答出来。面试官提示说：你自底向上考虑一下，分解结果中最多有几个2？
我说：最多两个2
面试官问：为什么？如果有三个2会发生什么情况？
我马上想到了，说：如果有三个2就可以分解成两个3，这样会得到更大的结果。
到这里这个题目才完整结束。之所以优先分解为3是因为最多只有两个2，并且只发生在一种情况下，就是M%3 ==1的情况。这个题目教会了我要灵活运用自顶向下和自底向上的思维，而且不要机械的去刷题。
原以为这个题目完成的还算ok，结果面试官又抛出了题目3：
题目3：假设有2000个任务和5个人，1个任务会同时给3个不同的人做并且1个人会完成1200个任务(2000x3 = 1200x5)，并且要满足如下条件：每两个人之间都共享相同的任务数量，请提供一个解决方案。
面试思路：拿到这题后，光弄懂题意理清思路都花了几分钟时间。完全不知道这道题究竟是考算法还是智力题？经过一番思考后，我给出了如下思路：5个人两两共享相同的任务数量，则一共有C(5,2)=10种两两组合方式，设每两个人之间的共享任务数为x，则所有共享任务数为10x个，总共的任务数为6000个（2000x3含重复），由此可以列出方程6000-10x = 2000 得出每两个人之间共享的任务是400个。面试官听了我的思路指出是错误的，因为没有考虑到3个以上人之间的交集情况。
正确解法：回来后经过和面试官邮件讨论，终于知道了这道题的正确解法，原来是一道非常简单的题目。其核心思路是保证2000个任务均匀的分配到5个人。由于每个任务分配给3个人，5个人中选择3个人共有C(5,3)=10种选法，因此把2000个任务平均分成10份即可。具体解法如下：
将2000个任务平均分成10份，每份200个任务，再按如下方式分配
Slice 1: P1, P2, P3
Slice 2: P1, P2, P4
Slice 3: P1, P2, P5
Slice 4: P1, P3, P4
Slice 5: P1, P3, P5
Slice 6: P1, P4, P5
Slice 7: P2, P3, P4
Slice 8: P2, P3, P5
Slice 9: P2, P4, P5
Slice 10: P3, P4, P5
下图可直观看出每两个人之间共享任务数相同为200x3=600个
