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

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


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

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

往期链接：

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


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


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


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


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

YankeeDoodle 发表于 2021-5-27 10:33
逃脱阻碍

你在进行一个简化版的吃豆人游戏。你从 [0, 0] 点开始出发，你的目的地是 $target = [x_target ...

对于这道题，可能有部分人会先建图，然后广搜、深搜啥的，其实这道题就是一个数学问题。阻碍者最好的抓住你的办法就是在终点等你。数学证明如下： 如果鬼魂要在中间拦截 AC上必须有一点D 使得AD = DB ，通过三角不等式 AC = AD + DC = DB + DC >= BC 。 如果鬼魂可以拦截到，那么鬼魂最好的做法就是在终点等着而不是去中间拦截。上面选择的是最短路径，乱走的话，相信鬼魂会笑的更开心！！！

/** A表示起点 ，B表示鬼魂的位置 ，目的地为C 。
*
*          C
*         /  \
*        /    \
*       /      \
*      /        \
*     /   \D     \
*    /      \     \
*   /         \    \
*  /            \   \
* A               \
*                     B
*
* */
而你到达target的最短距离就是abs(target[0]) + abs(target[1])，每个阻碍者到达终点的最短距离就是 abs(ghost[0]-target[0])+abs(ghost[1]-target[1])，因此我们只要比较两者的大小即可。

class Solution {
public:
    bool escapeGhosts(vector<vector<int>>& ghosts, vector<int>& target) {
        int myMindistance = abs(target[0]) + abs(target[1]);//我到达终点的最短距离
        for (auto &ghost : ghosts){//判断是否有ghost比我先到达终点
            if (myMindistance >= abs(ghost[0]-target[0])+abs(ghost[1]-target[1])){
                return false;
            }
        }
        return true;
    }
};
复杂度分析

时间复杂度：$O(\text{ghosts}.\text{length})$
空间复杂度：$O(1)$

YankeeDoodle 发表于 2021-5-25 10:57
公交路线问题
给你一个数组 routes ，表示一系列公交线路，其中每个 routes 表示一条公交线路，第 i 辆公 ...

本题首先不要管车站(station)，我们只在乎公交路线(route)。我们可以将每一条线路视作一个点，对于任意两条线路，如果它们经过的车站有交集，那么就在两点之间连一条边，这样就构成了一张图。这是否会让人联想到DFS或者BFS呢？

图中有些点（路线）是包含起点 $S$ 的，我们把它们都作为起点。而有些点（路线）是包含终点 $T$ 的，我们把它们都作为终点。

那么问题就转化为了求起点到终点的最短路径。因为起点和终点数量可能有多个，所以我们新建两个结点，一个起点用来指向所有包含 $S$ 的点，一个终点用来指向所有包含 $T$ 的点。接下来问题就变成了单源最短路径问题了。

由于是求最短距离，我们首先应该考虑BFS，伪码如下

int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
    queue<Node> q;
    vector<bool> visited;
    q.push(起点路线);
    while (!q.empty()) {
        取出一个节点；
        判断是否访问过；
        设置访问；
        判断是否是终点，如果是就返回答案。
        for (所有和这个节点关联的节点) {
            if(这个节点还没访问过) {
                q.push(这个节点);
            }
        }
    }
    return -1;
}
我们应该要找到经过某一站点的所有的路线，只要经过同一个站点，那这些路线就是相连接的。因此，用unordered_map<int, vector<int>> stationToRoute来存储经过站点的所有路线的数据，key代表站点,value代表经过此站点所有的路线。遍历所有的routes，把经过同一站点的路线们都记录下来。

unordered_map<int, vector<int> > stationToRoute;
for (int i = 0; i < routes.size(); i++) {
    for (int j = 0; j < routes[i].size(); j++) {
        stationToRoute[routes[i][j]].push_back(i);
    }
}
接下来，通过这一数据结构，我们来构建我们的图。遍历哈希表中所有的key，把一个value中所有的路线相连接。

for (auto &p : stationToRoute) {
    for (auto &route : p.second) {
        for (auto &secondRoute : p.second) {
            if (secondRoute != route) {
                routeToRoutes[route].push_back(secondRoute);
            }   
        }
    }
}
我们同样可以通过stationToRoute[source]以及stationToRoute[target]来找到所有的起始路线以及终止路线。最后，我们可以通过queue<pair<int, int>>的方法，来同时记录路线以及之前所经过的路线数量。

YankeeDoodle 发表于 2021-5-25 10:57
公交路线问题
给你一个数组 routes ，表示一系列公交线路，其中每个 routes 表示一条公交线路，第 i 辆公 ...

本题首先不要管车站(station)，我们只在乎公交路线(route)。我们可以将每一条线路视作一个点，对于任意两条线路，如果它们经过的车站有交集，那么就在两点之间连一条边，这样就构成了一张图。这是否会让人联想到DFS或者BFS呢？

图中有些点（路线）是包含起点 $S$ 的，我们把它们都作为起点。而有些点（路线）是包含终点 $T$ 的，我们把它们都作为终点。
那么问题就转化为了求起点到终点的最短路径。因为起点和终点数量可能有多个，所以我们新建两个结点，一个起点用来指向所有包含 $S$ 的点，一个终点用来指向所有包含 $T$ 的点。接下来问题就变成了单源最短路径问题了。
由于是求最短距离，我们首先应该考虑BFS，伪码如下
int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
    queue<Node> q;
    vector<bool> visited;
    q.push(起点路线);
    while (!q.empty()) {
        取出一个节点；
        判断是否访问过；
        设置访问；
        判断是否是终点，如果是就返回答案。
        for (所有和这个节点关联的节点) {
            if(这个节点还没访问过) {
                q.push(这个节点);
            }
        }
    }
    return -1;
}
我们应该要找到经过某一站点的所有的路线，只要经过同一个站点，那这些路线就是相连接的。因此，用unordered_map<int, vector<int>> stationToRoute来存储经过站点的所有路线的数据，key代表站点,value代表经过此站点所有的路线。遍历所有的routes，把经过同一站点的路线们都记录下来。
unordered_map<int, vector<int> > stationToRoute;
for (int i = 0; i < routes.size(); i++) {
    for (int j = 0; j < routes[i].size(); j++) {
        stationToRoute[routes[i][j]].push_back(i);
    }
}
接下来，通过这一数据结构，我们来构建我们的图。遍历哈希表中所有的key，把一个value中所有的路线相连接。
for (auto &p : stationToRoute) {
    for (auto &route : p.second) {
        for (auto &secondRoute : p.second) {
            if (secondRoute != route) {
                routeToRoutes[route].push_back(secondRoute);
            }   
        }
    }
}
我们同样可以通过stationToRoute[source]以及stationToRoute[target]来找到所有的起始路线以及终止路线。最后，我们可以通过queue<pair<int, int>>的方法，来同时记录路线以及之前所经过的路线数量。
综上，代码如下：
class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
        // 会有XX不上公交车...起点就是终点...
        if (source == target) {return 0;}
        // 先遍历所有的路线中的站台，把每个站台所能路过的路线都记录下来
        unordered_map<int, vector<int> > stationToRoute;
        for (int i = 0; i < routes.size(); i++) {
            for (int j = 0; j < routes[i].size(); j++) {
                stationToRoute[routes[i][j]].push_back(i);
            }
        }
        // 再遍历所有站台，根据站台经过的路线，来建立路线之间的关系
        vector<vector<int> > routeToRoutes(500, vector<int>(0));
        for (auto &p : stationToRoute) {
            for (auto &route : p.second) {
                for (auto &secondRoute : p.second) {
                    if (secondRoute != route) {
                        routeToRoutes[route].push_back(secondRoute);
                    }   
                }
            }
        }
        unordered_set<int> endRoutes;
        for (auto &route : stationToRoute[target]) {
            endRoutes.insert(route);
        }
        vector<bool> visited(500, false);
        // 首先得有一个queue可以存档node和一些信息
        // <第几个route, 上过几辆车了>
        queue<pair<int, int> > q;
        for (auto &route : stationToRoute[source]) {
            q.push({route, 0});
        }
        while (!q.empty()) {
        // 取出queue元素
            auto tmp = q.front();
            q.pop();
        // 如果访问过了，就continue;
        // 再设置一下visited
            if(visited[tmp.first]) {
                continue;
            }
        // 没访问过，就看看是不是终点
            visited[tmp.first] = true;
            if (endRoutes.find(tmp.first) != endRoutes.end()) {
                return tmp.second + 1;
            }
            for (auto &route : routeToRoutes[tmp.first]) {
                // 对于所所有下个可能，入queue
                if (!visited[route]) {
                    q.push({route, tmp.second + 1});
                }
            }
        }
        return -1;
    }
};
复杂度分析：
时间复杂度：假设路线数量是 $N$，每条路线最多有 $M$ 个车站。那么排序复杂度为 $O(NMlogM)$，建图复杂度为 $O(N^2M)$，BFS 复杂度为 O(N^2)。因此总的时间复杂度忽略低阶项之后为 $O(N^2M)$。
空间复杂度：$O(N^2)$

感谢楼主！最近过了微软面试，在team match,求打捞～ 刚刚加了LinkedIn。谢谢！

谢谢，不知道巨硬题国内是共享的吗

感谢楼主！!!!

公交路线问题
给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。
例如，路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... 这样的车站路线行驶。 现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。 期间仅可乘坐公交车。
求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -1 。
示例 1：
输入：routes = [[1,2,7],[3,6,7]], source = 1, target = 6
输出：2
解释：最优策略是先乘坐第一辆公交车到达车站 7 , 然后换乘第二辆公交车到车站 6 。
示例 2：
输入：routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
输出：-1

逃脱阻碍

你在进行一个简化版的吃豆人游戏。你从 [0, 0] 点开始出发，你的目的地是 $target = [x_target, y_target]$ 。地图上有一些阻碍者，以数组 ghosts 给出，第 $i$ 个阻碍者从 $ghosts = [x_i, y_i]$ 出发。所有输入均为整数坐标 。
每一回合，你和阻碍者们可以同时向东，西，南，北四个方向移动，每次可以移动到距离原位置 1 个单位 的新位置。当然，也可以选择不动 。所有动作同时发生。
如果你可以在任何阻碍者抓住你之前到达目的地（阻碍者可以采取任意行动方式），则被视为逃脱成功。如果你和阻碍者同时到达了一个位置（包括目的地）都不算是逃脱成功。
只有在你有可能成功逃脱时，输出 true ；否则，输出 false 。

示例 1:
输入：
ghosts = [[1, 0], [0, 3]]
target = [0, 1]
输出：true
解释：你可以直接一步到达目的地(0,1)，在(1, 0)或者(0, 3)位置的阻碍者都不可能抓住你。

示例 2:
输入：
ghosts = [[1, 0]]
target = [2, 0]
输出：false
解释：你需要走到位于(2, 0)的目的地，但是在(1, 0)的阻碍者位于你和目的地之间。

示例 3:
输入：
ghosts = [[2, 0]]
target = [1, 0]
输出：false
解释：阻碍者可以和你同时达到目的地。

示例 4：
输入：
ghosts = [[5,0],[-10,-2],[0,-5],[-2,-2],[-7,1]],
target = [7,7]
输出：false

示例 5：
输入：
ghosts = [[-1,0],[0,1],[-1,0],[0,1],[-1,0]],
target = [0,0]
输出：true

有两个容量分别为$x$升和$y$升的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好$z$升的水？ 如果可以，最后请用以上水壶中的一或两个来盛放取得的$z$升水。

你允许：
装满任意一个水壶
清空任意一个水壶
从一个水壶向另外一个水壶倒水，直到装满或者倒空

示例 1:
输入: x = 3, y = 5, z = 4
输出: True

示例 2:
输入: x = 2, y = 6, z = 5
输出: False