微软近期高频面试题分享 + 分析（八）

最近来巨硬面试的小朋友通过概率实在太低了，代码老是写不对，我们组已经十连拒了，不得不感叹，现在出的面试题越来越难了，我决定还是上来地里透透题，说点最近我们组面试常考高频题和解析（毕竟岗位机会也不能都让三锅霸占了对不）。招人艰难，看微软机会的小伙伴，也欢迎LinkedIn勾搭：
https://www.linkedin.com/in/andy-yongjian-deng-212977200/


注意打招呼的时候备注一下，方便识别友军，hhhh。

带娃有压力，尽量保持一周两更，大家海涵。


往期链接：

微软近期高频面试题分享 + 分析（一）


微软近期高频面试题分享 + 分析（二）

微软近期高频面试题分享 + 分析（三）

微软近期高频面试题分享 + 分析（四）

微软近期高频面试题分享 + 分析（五）

微软近期高频面试题分享 + 分析（六）

微软近期高频面试题分享 + 分析（七）

超级洗衣机解析

1、记总的衣服为sum，那么显然sum不能整除n的情况下无解。最后相等的数量为average = sum / n。
2、先从最简单的情况入手，[3,2,1]应该怎么选？当然是选择[3,2]，3传递一个给2,2传递一个给1，只需一次操作就平衡了。我们发现，这是一个水往低处流的过程，虽然我们的目标是从3里面给一个给1，但是中间已经平衡的2也被迫选上。这说明一旦一个洗衣机已经平衡，那么如果有衣服想经过它，就必须把这台洗衣机选上。否则只会花费更多的步骤让它重新平衡。

3、想明白上面一点， 我们就能进一步发现，所有洗衣机平衡的方法只有两种情况： 第一种，多、少衣服的洗衣机在两边：

第二种，少衣服的洗衣机在两边，最多衣服的洗衣机在中间

先看第一种情况。在5将两件衣服传递到右边之前，4是不会改变的，这需要两步。然后4将一件衣服传递到右边，总的步骤是3步。所以它等价于：

当我们考察第二个洗衣机时，可以将1、2两个洗衣机合并，左边一共多了3件衣服(最后平均每个为3件，所以是5+4-3*2=3)，这3件都要传递到右边去。更进一步，我们在任意位置画一条虚线，假设它左边有$left$件衣服，右边有$right$件衣服，平衡状态下左边应该是$left'$件衣服，那么左边多了$left-left'$件衣服，这些衣服需要流动到右边去。当我们遍历所有的虚线位置，其中最大的一个$max(left-left')$就是答案。这个答案必要性是显而易见的，每次只能流动一件衣服，而左边多了$left-left'$件，所以至少需要这么多次流动步骤。那么这些衣服流动到右边以后，就可以将右边变平衡。如下图：

然后假设右边有一个$Y$大于average，那么它必然不能紧挨着左边的X，因为紧挨的情况下，Y位置的$left-left'$必然大于X位置的$left-left'$，这样$max(left-left')$就是$Y$了。

那么X和Y之间如果有小于average的Z呢？我们肯定要先从X流动衣服到Z，于此同时，为了减少操作步骤，我们要从Y流动衣服到更右边的地方。关键是，当Z平衡的时候，Y一定已经先平衡了，否则就变成了Y紧挨着X的情况，又矛盾了。而Y平衡以后，就变成了X往右分发的情况，一定能够完成。

搞清楚第一种情况以后，第二种情况就更容易理解了，把最多衣服的洗衣机想象成一个真正的超级洗衣机，左右两边的洗衣机都等着它分发衣服就可以了。

1. class Solution {
   
2. public:
   
3.     int findMinMoves(vector<int>& machines) {
   
4.         int i, size = machines.size(), sum = getSum(machines), average = sum / size;
   
5.         if (average * size != sum) {
   
6.             return -1;
   
7.         }
   
8. 
   
9.         int left = machines[0], wantedLeft = average, right, wantedRight = average * (size - 2);
   
10.         int minMoves = max(abs(machines[0] - average), abs(machines[size - 1] - average));
    
11. 
    
12.         for (i = 1; i < size - 1; ++i) {
    
13.             int num = machines[i];
    
14.             right = sum - num - left;
    
15. 
    
16.             if (num >= average) {
    
17.                 int moves = num - average;
    
18.                 if (left > wantedLeft) {
    
19.                     moves += (left - wantedLeft);
    
20.                 }
    
21.                 if (right > wantedRight) {
    
22.                     moves += (right - wantedRight);
    
23.                 }
    
24.                 minMoves = max(minMoves, moves);
    
25. 
    
26.             }
    
27. 
    
28.             left += num;
    
29.             wantedLeft += average;
    
30.             wantedRight -= average;
    
31.         }
    
32. 
    
33.         return minMoves;
    
34.     }
    
35. 
    
36.     int getSum(vector<int>& machines) {
    
37.         int sum = 0;
    
38. 
    
39.         for (int num : machines) {
    
40.             sum += num;
    
41.         }
    
42. 
    
43.         return sum;
    
44.     }
    
45. };
    

复制代码

复杂度分析
时间复杂度：O(N)。
空间复杂度：O(1)。

1、回溯算法
先想出暴力解法，即以每个箱子为最底下的箱子。然后在余下的箱子中寻找下一个箱子，下一个箱子自然是比前一个要小的，而后再寻找更小的。这就是一个 dfs 的过程。

选择一个箱子作为作为底之后，可以把问题转换为在约束条件下，求其余箱子能叠出的最大高度。可以把子问题的解（以每个箱子为底所能得到的最大高度）缓存下来，以加速计算。另外，可以在维度上进行升序排列，这样当前箱子后面的所有箱子都不可能处于该箱子之上。 所以操作如下：
    排序（升序）
    遍历，将各个箱子作为底
    在剩下的箱子中，以2步骤的箱子为底和约束条件下，寻找合适的箱子，递归重复2，直到所有箱子。计算高度和。
    在高度和中取最大值。

1. class Solution {
   
2. public:
   
3.     int pileBox(vector<vector<int>>& box) {
   
4.         sort(box.begin(), box.end(), [](auto& a, auto& b){
   
5.             return a[0] < b[0];
   
6.         });
   
7.         vector<int> cache(box.size(), -1);
   
8.         int max_height = 0;
   
9.         for(int i = 0; i < box.size(); i++){
   
10.             max_height = max(max_height, dfs(box, i, cache));
    
11.         }
    
12.         return max_height;
    
13.     }
    
14. 
    
15.     int dfs(vector<vector<int>>& box, int bottom_box_i, vector<int>& cache){
    
16.         if(cache[bottom_box_i] != -1){
    
17.             return cache[bottom_box_i];
    
18.         }
    
19.         int ret = 0;
    
20.         vector<int> &bottom_box = box[bottom_box_i];
    
21.         for(int i = 0; i < bottom_box_i; i++){
    
22.             if(small(box[i], bottom_box)){
    
23.                 ret = max(ret, dfs(box, i, cache));
    
24.             }
    
25.         }
    
26.         ret = ret + bottom_box[2];
    
27.         cache[bottom_box_i] = ret;
    
28.         return ret;
    
29.     }
    
30.    
    
31.     bool small(const vector<int> &box1, const vector<int> &box2){
    
32.         for(int i = 0;i<box1.size();i++){
    
33.             if(box1[i] >= box2[i]){
    
34.                 return false;
    
35.             }
    
36.         }
    
37.         return true;
    
38.     }
    
39. };

复制代码

堆箱子问题

给你一堆n个箱子，箱子宽 $w_i$、深 $d_i$、高 $h_i$。箱子不能翻转，将箱子堆起来时，下面箱子的宽度、高度和深度必须大于上面的箱子。实现一种方法，搭出最高的一堆箱子。箱堆的高度为每个箱子高度的总和。

输入使用数组$[w_i, d_i, h_i]$表示每个箱子。

示例1:
输入：box = [[1, 1, 1], [2, 2, 2], [3, 3, 3]]
输出：6
示例2:
输入：box = [[1, 1, 1], [2, 3, 4], [2, 6, 7], [3, 4, 5]]
输出：10

谢谢楼主的分享，感觉很受益

只能想到O(n^2)。。

1. box.sort()
   
2. n = len(box)
   
3. dp = [x[-1] for x in box]
   
4. for i in range(n):
   
5.     for j in range(i):
   
6.         if all(a > b for a, b in zip(box[i], box[j])):
   
7.             dp[i] = max(dp[i], box[i][-1]+dp[j])
   
8. 
   
9. return dp[-1]

复制代码

[i][i][i][/i][/i][/i]

微软职业招个人一般要多久呢？

2、动态规划

本题类似于俄罗斯套娃，都属于最长递增子串问题。也就是在一维的数组中找到该数列的递增次序，如下图所示：

最终紫色的序列1,2,3就是最后的最长递增子串。放到这道题来讲，我们先要将三维的排序，对于第一维相同的，就采用第二维的子串递增，如果第二维也相同，那么就找第三维的子串递增序列。下图是一个二维的示例：

所以对于该题的算法操作如下：
先将数组按照任何一条边降序重排，目的是为了降低里层循环次数。
使用dp一维数组记录以序号$i$箱子为顶时的最大高度。
计算每个箱子$i$时，在约束条件下，找到所有箱子$k$（$i$可以放在$k$的上面），并计算以k为顶最大高度与$i$的高度之和，取最大值。
所有箱子都操作完后，取dp数组元素的最大值

1. class Solution {
   
2. public:
   
3.     int pileBox(vector<vector<int>>& box) {
   
4.         sort(box.begin(), box.end(), [](auto& a, auto& b){
   
5.             return a[0] < b[0];
   
6.         });
   
7.         vector<int> dp(box.size(), 0);
   
8.         dp[0] = box[0][2];
   
9.         int ret = dp[0];
   
10.         for(int i = 1; i < box.size(); i++){
    
11.             int max_height = 0;
    
12.             for(int j = 0; j < i; j++){
    
13.                 if(small(box[j], box[i])){
    
14.                     max_height = max(max_height, dp[j]);
    
15.                 }
    
16.             }
    
17.             dp[i] = max_height + box[i][2];
    
18.             ret = max(ret, dp[i]);
    
19.         }
    
20.         return ret;
    
21.     }
    
22.    
    
23.     bool small(const vector<int> &box1, const vector<int> &box2){
    
24.         for(int i = 0;i<box1.size();i++){
    
25.             if(box1[i] >= box2[i]){
    
26.                 return false;
    
27.             }
    
28.         }
    
29.         return true;
    
30.     }
    
31. };

复制代码

超级洗衣机

假设有 n 台超级洗衣机放在同一排上。开始的时候，每台洗衣机内可能有一定量的衣服，也可能是空的。 在每一步操作中，你可以选择任意 $m （1 ≤ m ≤ n）$ 台洗衣机，与此同时将每台洗衣机的一件衣服送到相邻的一台洗衣机。 给定一个非负整数数组代表从左至右每台洗衣机中的衣物数量，请给出能让所有洗衣机中剩下的衣物的数量相等的最少的操作步数。如果不能使每台洗衣机中衣物的数量相等，则返回 -1。

示例 1：
输入: [1,0,5]
输出: 3
解释:
第一步:    1     0 <-- 5    =>    1     1     4
第二步:    1 <-- 1 <-- 4    =>    2     1     3   
第三步:    2     1 <-- 3    =>    2     2     2   

示例 2：
输入: [0,3,0]
输出: 2
解释:
第一步:    0 <-- 3     0    =>    1     2     0   
第二步:    1     2 --> 0    =>    1     1     1     

示例 3:
输入: [0,2,0]
输出: -1
解释:
不可能让所有三个洗衣机同时剩下相同数量的衣物。

mark，想不出来，等洗衣机的答案😂