视频总结 | ACM大神精讲最新北美面试题5


(darcylike) #1

讲座嘉宾:Steve

讲座链接:ACM大神精讲最新北美面试题 第五讲

讲座总结:6Kunnnnn

题目 1 Boarding Passes 难度 2/5

题目介绍

给定几张机票的起飞和降落城市,找到本次行程的起始城市和终点城市。

![](data:image/svg+xml;utf8,)

题目分析

最简单的暴力解法的话,对于N个城市,找到一个起始点,然后逐个找到路线的中间城市,直到找到所有可能的旅行路线,然后判断起始点和终止点,时间复杂度为O(N^N),显然这样的方法是行不通的。而且,对于不同的输入,也就是从一个城市到另一个城市的机票,有可能存在起点和终点虽然固定,但是可以组成不同路线的情况(输入里没有说明机票的时间顺序),比如下图。所以说,如果是通过具体的行程路线来决定起点和终点的话,会有多种情况存在,所以可能不是一个好方法。

![](data:image/svg+xml;utf8,)

进一步分析,常识来看,对于某个城市,如果乘客到这里后没有离开,就说明是终点城市。但是根据题目来看,即便是终点城市,也有可能存在飞机多次飞往这个城市的情况,也就是说,从这里飞也好,飞到这里也好,最后的最后飞机都是停在了这个城市。那么对于每个城市,联想到有向图的节点出度和入度的性质,从这里起飞就是出度+1,到达这里就是入度+1,那么对于终点城市,必然有入度=出度+1,也就是到达的机票比起飞的机票多1。反过来,如果入度=出度-1,也就是到达的机票比起飞的机票少1,就说明这个城市是起始点,也就是在整个行程开始前,乘客已经来到了这个城市。而如果入度=出度,则说明这个城市是中转城市。如下图,Arrive passes (Ap)就是入度,Leave passes (Lp) 也就是出度。

![](data:image/svg+xml;utf8,)

那么根据这个思路,我们只需要遍历所有的机票,然后计算出每个城市的出度和入度,就能找到起点城市和终点城市,算法思路如下图,其中Count对应的其实就是Ap - Lp,如果为负值即-1,则城市为起点城市,为0则说明是中转城市,否则为1则说明是终点城市。整体的时间复杂度为O(N)。当然,这方法假设是不存在circle的情况,否则在circle的情况下,可能存在多个起点城市和终点城市,如下图。

![](data:image/svg+xml;utf8,)

**代码实现

![](data:image/svg+xml;utf8,)

**

思路补充

其实这道题目本质上是一个有向图的问题,需要考虑图中节点(城市)出度和入度的性质。

题目 2 Sorting Photo Files 难度 1/5

题目介绍

![](data:image/svg+xml;utf8,)

题目分析

这道题目也不难,简单的排序问题。但是需要注意的是不可以直接按照图片的文件名来排序,因为在location之后的数字是需要按照大小来排序的,也就是beijing10要在beijing8的后面,而如果单纯按照string来对待是不够的。换个方法的话,可以用multi-keyword comparsion,就是把文件名拆分成一个location order pair,然后先按照location排序,再按照order排序即可,如下图。

![](data:image/svg+xml;utf8,)

复杂度的话,遍历所有的photo文件名然后构建location-order pair需要O(N),之后排序需要O(NlogN),所以总共的复杂度为O(NlogN),如下图。

![](data:image/svg+xml;utf8,)

**代码实现

![](data:image/svg+xml;utf8,)

**

题目 3 Circle Detect 难度 3/5

题目介绍

**

![](data:image/svg+xml;utf8,)**

题目分析

如果是最简单的暴力解法的话,从每一个节点开始,通过DFS方法,对节点进行遍历并且标记上已经访问过的节点,之后如果遇到某个节点已经被访问过,则说明这个图中存在着circle,如下图。

![](data:image/svg+xml;utf8,)

复杂度的话,总共N个节点,第K个节点要访问N-K的节点,也就是一个等差数列,那么最终需要对这些节点访问O(N^2)次。这种暴力解法耗时的原因就是存在一些节点,已经在之前某次的遍历中检查过是否存在circle了,也就是有很多的重复作业,如下图。

![](data:image/svg+xml;utf8,)

所以如何避免重复访问节点的情况?我们其实可以只考虑从入度为0的节点开始遍历的情况,因为这些节点不存在前驱节点,也就是不存在从其他节点开始遍历到这个节点的情况,也就是这些节点不会被重复访问。如果遍历完所有入度为0的节点后,如果存在没有被访问过的节点,也就是没有一个入度为0的节点可以到达这个点,就说明图中是有circle的。但是这种方法仅仅适用于有向图,对于无向图则需要用另一种方法叫做并查集。而且存在一种特殊情况就是,如果整个的图就是一个circle的话,是无法找到入度为0的节点开始遍历的,也就在这个图中存在节点没有被访问过,如下图。

![](data:image/svg+xml;utf8,)

算法的实现如下图,从所有0-indegree的node开始遍历图,如果在遍历的途中发现了circle,也就是存在被访问过的节点,就说明有circle;否则,Summarize一下节点的访问情况,如果所有的0-indegree的node都尝试过,但仍然存在节点没被访问,就说明也是有circle的,否则没有。复杂度的话,所有的节点都最多被访问一次,也就是所有的edge都会被访问过一次,复杂度为O(M),M为edge的数量。

![](data:image/svg+xml;utf8,)

思路补充

另外一种思路则是类似拓扑排序。如果一个有向图里面不含有circle的话,必存在节点的入度为0。那么如果我们把所有入度0的节点,以及这些节点所经过的边从图中移除,剩下的节点和边所组成的子图和原图是否有circle是等价的(因为有没有circle和入度为0的节点无关),也就是可以通过这个子图来判断原图是否有circle。根据这个想法,我们从入度为0的节点开始遍历图,在移除掉这些节点和他们的edge之后,如果有新的入度为0的节点出现,则再次以同样的方法来处理这个节点;到最后如果仍有剩余的节点没有被处理,也就是存在节点入度不为0,原图就是有circle的。算法思路和时间复杂度如下图,更多细节欢迎大家到太阁官网观看原视频。

**

![](data:image/svg+xml;utf8,)**

AWS云计算工程师训练营:亲手实现12亿纽约出租车原始行驶数据 AWS 数据处理平台

回看第一节课视频:AWS云计算工程师训练营:亲手实现12亿纽约出租车原始行驶数据 AWS 数据处理平台 回看第一节课视频

搜索广告老司机带领同学们一步步从头搭建电商搜索广告平台

报名免费第一节课:搜索广告老司机带领同学们一步步从头搭建电商搜索广告平台 报名免费第一节课

更多精彩,尽在硅谷高端线上教育社区BitTiger:请猛戳我

公众号:论码农的自我修养

知乎专栏:太阁实验室

微博:@太阁BitTiger

今日头条:太阁BitTiger