查看: 3176|回复: 12
收起左侧

[高频题] 微软近期高频面试题分享 + 分析(六)

  |只看干货
本楼: 👍   100% (3)
 
 
0% (0)   👎
全局: 👍   99% (325)
 
 
0% (2)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x

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


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

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

往期链接:

微软近期高频面试题分享 + 分析(一)


微软近期高频面试题分享 + 分析(二)


微软近期高频面试题分享 + 分析(三)


微软近期高频面试题分享 + 分析(四)


微软近期高频面试题分享 + 分析(五)

评分

参与人数 17大米 +21 收起 理由
MarsC94 + 1 很有用的信息!
ShiearaX + 1 给你点个赞!
Twilight98 + 1 很有用的信息!
Magic_ + 1 赞一个
YufeiZhengBlkZ + 1 赞一个
limiu + 2 给你点个赞!
Liumiuniuniuniu + 1 赞一个
asa11 + 1 很有用的信息!

查看全部评分


上一篇:leetcode可以pass掉的题
下一篇:Leetcode 高频题重新分类
 楼主| YankeeDoodle 2021-5-28 10:59:32 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   99% (325)
 
 
0% (2)    👎
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-26 10:30:25 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   99% (325)
 
 
0% (2)    👎
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.size(); j++) {
        stationToRoute[routes[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>>的方法,来同时记录路线以及之前所经过的路线数量。
回复

使用道具 举报

catling33 2021-5-24 21:18:30 来自APP | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (12)
 
 
0% (0)    👎
感谢楼主!最近过了微软面试,在team match,求打捞~ 刚刚加了LinkedIn。谢谢!
回复

使用道具 举报

windlion 2021-5-24 22:13:29 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (17)
 
 
0% (0)    👎
谢谢,不知道巨硬题国内是共享的吗
回复

使用道具 举报

 楼主| YankeeDoodle 2021-5-25 10:57:43 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (325)
 
 
0% (2)    👎
公交路线问题
给你一个数组 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




回复

使用道具 举报

 楼主| YankeeDoodle 2021-5-26 10:28:48 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (325)
 
 
0% (2)    👎
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.size(); j++) {
        stationToRoute[routes[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.size(); j++) {
                stationToRoute[routes[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)$










回复

使用道具 举报

 楼主| YankeeDoodle 2021-5-27 10:33:10 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (325)
 
 
0% (2)    👎
逃脱阻碍

你在进行一个简化版的吃豆人游戏。你从 [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
回复

使用道具 举报

 楼主| YankeeDoodle 2021-5-29 10:45:37 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (325)
 
 
0% (2)    👎
有两个容量分别为$x$升和$y$升的水壶以及无限多的水。请判断能否通过使用这两个水壶,从而可以得到恰好$z$升的水? 如果可以,最后请用以上水壶中的一或两个来盛放取得的$z$升水。

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

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

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

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表