亚麻 2020 new grad OA2

替小伙伴发一个今天的亚麻OA2.

两道coding题，70min。

第一题是利口240，在2d matrix里找一个数。
第二题是找连通图(2d array)里的所有bridge(critical connections), 使得这个graph变成两个disconnected parts.

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

ewang6898 发表于 2019-9-2 09:57
谢楼上大佬

这个是不行的，复杂度O(N^2)，这题N<=100000
唯一可行的是O(N)的Tarjan算法：https://www.geeksforgeeks.org/bridge-in-a-graph/
目前leetcode上没有任何题用到这个算法

求大佬第二题解题思路

把edge一個一個拔掉再看看是不是连通图？Components >1 爲非连通  裏口散兒傘

gretor0231 发表于 2019-9-2 09:18
把edge一個一個拔掉再看看是不是连通图？Components >1 爲非连通  裏口散兒傘

谢楼上大佬

第二题也太难了吧。。。。最优解写不出来啊。。只能写一个简单的
Dfs