回复: 16
跳转到指定楼层
上一主题 下一主题
收起左侧

空气床背靠背

全局:

2018(10-12月) 码农类General 硕士 实习@airbnb - 内推 - 技术电面  | | Other | 其他

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

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

x
昨天下午的店面第一轮面了一个graph题,给node到node的time 和 node的scor
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

他家确实要现场run,第一次当场跑代码还挺紧张的

评分

参与人数 8大米 +50 收起 理由
agentic_coding + 25 给你点个赞!
happycsdogs + 3 给你点个赞!
快乐源泉虎东东 + 3 很有用的信息!
Juncaceae + 5 给你点个赞!
mtli + 5 给你点个赞!

查看全部评分


上一篇:推特OA
下一篇:[面试经验]讨论Nvidia coding题目
推荐
不一定 2018-11-11 06:45:05 | 只看该作者
全局:
楼主想请问你的pour water题是两边有无限高墙的吗?
回复

使用道具 举报

推荐
ShawnG 2018-11-12 01:16:08 | 只看该作者
全局:
mtli 发表于 2018-11-11 22:48
咦呐尼....想不明白了.....如果一个node1到node2的time小于node2的score,它只要重复走node1-->node2-->n ...

拓扑排序后,就知道这些node的前后关系,这样你就不需要像bfs时,有些node
和path要visit很多回。然后记录一个map,所有node最高分,src设为自己的score ,其他的都设为了- inifinity
然后根据你拓扑排序的结果,算每个node的分,更新这个map
回复

使用道具 举报

推荐
mtli 2018-11-11 22:48:00 | 只看该作者
全局:
ShawnG 发表于 2018-11-11 06:58
做不了dijstra,dijstra只能找最小,这是最大。你写出来BFS的时候你可以看看时间复杂度,不是O(V+E),这个 ...

咦呐尼....想不明白了.....如果一个node1到node2的time小于node2的score,它只要重复走node1-->node2-->node1的loop,得分是不是可以一直增加?不好意思太弱了,请楼主指点!谢谢🙏
回复

使用道具 举报

🔗
 楼主| savannah_s314 2018-11-9 18:04:42 | 只看该作者
本楼:
全局:
求米~~
回复

使用道具 举报

🔗
mtli 2018-11-9 23:44:21 来自APP | 只看该作者
全局:
楼主想请问下你的第一题是怎么做的呢?谢谢!!
回复

使用道具 举报

🔗
ShawnG 2018-11-10 07:22:56 | 只看该作者
全局:
mtli 发表于 2018-11-9 23:44
楼主想请问下你的第一题是怎么做的呢?谢谢!!

就是滑雪问题 bfs即可。
回复

使用道具 举报

🔗
mtli 2018-11-11 01:35:48 | 只看该作者
全局:
ShawnG 发表于 2018-11-10 07:22
就是滑雪问题 bfs即可。

那需要后续做什么优化吗?需要用到Dijstra之类的吗?
回复

使用道具 举报

🔗
ShawnG 2018-11-11 06:58:26 | 只看该作者
全局:
mtli 发表于 2018-11-11 01:35
那需要后续做什么优化吗?需要用到Dijstra之类的吗?

做不了dijstra,dijstra只能找最小,这是最大。你写出来BFS的时候你可以看看时间复杂度,不是O(V+E),这个时间复杂度比较tricky, 你说他是O(VE)或者O(V+multipleE)也可以,用topo sort能优化到O(V+E);
回复

使用道具 举报

🔗
mtli 2018-11-12 12:00:22 | 只看该作者
全局:
ShawnG 发表于 2018-11-12 01:16
拓扑排序后,就知道这些node的前后关系,这样你就不需要像bfs时,有些node
和path要visit很多回。然后记 ...

好像有点懂了!谢谢楼主!
回复

使用道具 举报

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

本版积分规则

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