📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
回复: 11
跳转到指定楼层
上一主题 下一主题
收起左侧

狗家电面面经:有向图包含目标点的最小环

全局:

2019(10-12月) 码农类General 硕士 全职@google - 内推 - 技术电面  | | Other | 在职跳槽

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

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

x
烙印电话面,45min, 问 有向图包含目标点的最小环,

楼主比较弱,上来按照BFS写,后
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies

感觉可能挂了,还不如dfs
ps 貌似 利口还没有原题?

评分

参与人数 4大米 +13 收起 理由
什么名字好呢 + 2 给你点个赞!
哎哎哎echo + 1 很有用的信息!
匿名用户-QSUAS + 8
reliveinfire + 2 很有用的信息!

查看全部评分


上一篇:GS 最新面试
下一篇:Bloomberg 电面

本帖被以下淘专辑推荐:

  • · google|主题: 216, 订阅: 124
推荐
insomniadog 2019-10-29 01:34:26 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

推荐
 楼主| firefox970 2019-10-29 01:04:45 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

推荐
taybson 2020-1-29 11:29:12 | 只看该作者
全局:
  1. # Python3 implementation of the approach
  2. from sys import maxsize as INT_MAX
  3. from collections import deque
  4. from collections import defaultdict
  5.   
  6. N = 100200

  7. gr = [0] * N
  8. for i in range(N):
  9.     gr[i] = []
  10.   
  11. # Function to add edge
  12. def add_edge(x, y):
  13.     global gr
  14.     gr[x].append(y)
  15.     gr[y].append(x)

  16. # Number of vertices
  17. V = 7

  18. def shortest_cycle(n):
  19.     dist = [int(1e9) for _ in range(V)]
  20.     parent = [-1 for _ in range(V)]
  21.     dist[n] = 0
  22.     q = deque()
  23.     q.append(n)
  24.     shortest = float('inf')
  25.     mp = defaultdict(list)
  26.     while q:
  27.         cur = q.popleft()
  28.         for child in gr[cur]:
  29.             if dist[child] == int(1e9):
  30.                 dist[child] = dist[cur] + 1
  31.                 parent[child] = cur
  32.                 q.append(child)
  33.             elif parent[child] != cur and parent[cur] != child:
  34.                 if shortest > dist[cur] + dist[child] + 1:
  35.                     shortest = dist[cur] + dist[child] + 1
  36.                     path = [cur, child]
  37.                     p = cur
  38.                     d = child
  39.                     while parent[p] != n:
  40.                         p = parent[p]
  41.                         path.insert(0, p)
  42.                     while parent[d] != n:
  43.                         d = parent[d]
  44.                         path.append(d)
  45.                     path.append(n)
  46.                     mp[shortest].append(path)

  47.     print(mp[shortest]) #[2, 6, 1, 4, 3]
  48.     return shortest


  49. # Add edges
  50. add_edge(0, 6)
  51. add_edge(0, 5)
  52. add_edge(5, 1)
  53. add_edge(1, 6)
  54. add_edge(2, 6)
  55. add_edge(2, 3)
  56. add_edge(3, 4)
  57. add_edge(4, 1)

  58. # Function call
  59. print(shortest_cycle(3))
复制代码


本帖子中包含更多资源

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

x
回复

使用道具 举报

全局:
bfs+hashmap每个点存父亲节点
如果找到了再用hashmap的信息走回去输出环
回复

使用道具 举报

🔗
 楼主| firefox970 2019-10-29 21:10:16 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
yezhengli_mr9 2019-11-7 03:51:22 | 只看该作者
全局:
目标点有几个?没太明白,比方一个图总共10个nodes,目标点是只有n1,还是有[n1,n2,n3]?
回复

使用道具 举报

🔗
 楼主| firefox970 2019-11-10 22:33:04 | 只看该作者
全局:
yezhengli_mr9 发表于 2019-11-7 03:51
目标点有几个?没太明白,比方一个图总共10个nodes,目标点是只有n1,还是有[n1,n2,n3]?

目标点就一个

评分

参与人数 1大米 +2 收起 理由
yezhengli_mr9 + 2 给你点个赞!

查看全部评分

回复

使用道具 举报

全局:
麻烦楼主可以详细说一下题目么?环的概念是什么?比如 a到b, b到c。目标是c,环在哪里?
回复

使用道具 举报

🔗
 楼主| firefox970 2019-11-10 23:15:09 | 只看该作者
全局:
apollopffd 发表于 2019-11-10 22:55
麻烦楼主可以详细说一下题目么?环的概念是什么?比如 a到b, b到c。目标是c,环在哪里?

给定一个有向图,有一个点叫做 node_1, 找出包含该点的最小环。哈哈当时的描述就这么多
回复

使用道具 举报

🔗
 楼主| firefox970 2019-11-10 23:16:26 | 只看该作者
全局:
楼主这轮电面挂了

评分

参与人数 1大米 +2 收起 理由
yezhengli_mr9 + 2 给你点个赞!

查看全部评分

回复

使用道具 举报

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

本版积分规则

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