查看: 2340|回复: 22
收起左侧

🐶ng 11月初vo

|只看干货
匿名用户-CBE  发表于 2021-12-7 08:13:42 |阅读模式
本楼: 👍   100% (3)
 
 
0% (0)   👎

2021(10-12月) 码农类General 硕士 全职@Google - 内推 - Onsite  | 😐 Neutral 😐 AverageOther | 应届毕业生

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

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

x
本帖最后由 匿名 于 2021-12-6 16:19 编辑

11月初的一个vo 今天收到消息过hc了 发出来攒攒人品1. bq 问了challenging project

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

bfs/dfs多准备准备吧 之前忘记看了第一题连时间复杂度都答错了。。
总而言之看最近的帖子感觉很多题都有重复考 多看看面经应该不会有大问题

还有就是lz等hc等了一个多月 没见过比我慢的了。。如果有同样在等的别着急 会有好结果的

顺便问问pa match有可能挂么

求加米



补充内容 (2021-12-07 15:26 +8:00):
第三题 treenode还记录了parent

评分

参与人数 6大米 +14 收起 理由
bryanjhy + 5 给你点个赞!
Felix1218 + 1 赞一个
清道神君 + 3
月黑风高 + 1 给你点个赞!
AaLlC + 2 给你点个赞!
Smilingon + 2 给你点个赞!

查看全部评分


上一篇:Goldman Sachs Spring Program HireVue面经
下一篇:google 电面
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (2)
 
 
0% (0)    👎
匿名者 发表于 2021-12-7 02:31
思路差不多 时间复杂度我应该分析错了 面试官疯狂暗示应该和edge数有关

不知道为什么和edge个数有关.这道题本质combination的题,在四步中每一步都有O(N)选择.所谓的BFS其实一般的BFS不一样,是Path dependent的,所以time complexity不是一般的(V+E), 因为不同的选择路线(Path)会访问同一个vertex, edge很多次.总的time complexity应该是O(N^4)
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (32)
 
 
0% (0)    👎
gddxykxq 发表于 2021-12-7 11:08
不知道为什么和edge个数有关.这道题本质combination的题,在四步中每一步都有O(N)选择.所谓的BFS其实一般 ...

有航班的城市之间有边,遍历每条边,顶点作为4个城市中间那两个,然后头尾城市遍历边节点的邻居,这样就和边个数有关了吧
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (2)
 
 
0% (0)    👎
匿名者 发表于 2021-12-7 02:24
不可以 每个城市只能去一次

如果每个城市只能去一次,用backtrack其实更好做,time complexity差不多,但space complexity好很多. 因为BFS queue上每个element上要keep track of cities visited
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (105)
 
 
0% (0)    👎
给一堆城市,并给出他们的推荐分数(越高越推荐),以及城市间的航班。让你选出四个城市旅游,使得总分数最高。我用的bfs
---------
谢谢分享 楼主是bfs找所有长为4的路径,维护最大值?是O(N^2)?
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (105)
 
 
0% (0)    👎
哈哈 btw四题都是bfs
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (69)
 
 
0% (0)    👎
想问下楼主,第一题的路径长度最长就是4吗? 还是说某个城市可以visit 多次?
比如说 0-1, 0-2, 0-3, 0 可以作为中转城市吗?
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (2)
 
 
0% (0)    👎
第三题层级遍历没什么问题啊.找到那个node O(N),找到右边的Node O(1).
不可能再好了,除非还有什么条件?
回复

使用道具 举报

地里的匿名用户
匿名用户-CBE  发表于 2021-12-7 15:24:41
本楼: 👍   0% (0)
 
 
0% (0)   👎
moreauFang 发表于 2021-12-6 18:53
想问下楼主,第一题的路径长度最长就是4吗? 还是说某个城市可以visit 多次?
比如说 0-1, 0-2, 0-3, 0 ...

不可以 每个城市只能去一次
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (79)
 
 
1% (1)    👎
请问楼主看面经准备是看几个月的呢?最近三个月吗 谢谢
回复

使用道具 举报

地里的匿名用户
匿名用户-CBE  发表于 2021-12-7 15:25:47
本楼: 👍   0% (0)
 
 
0% (0)   👎
gddxykxq 发表于 2021-12-6 20:22
第三题层级遍历没什么问题啊.找到那个node O(N),找到右边的Node O(1).
不可能再好了,除非还有什么条件?

经你提醒我突然想起来 treenode还记录了parent
回复

使用道具 举报

地里的匿名用户
匿名用户-CBE  发表于 2021-12-7 15:30:05
本楼: 👍   0% (0)
 
 
0% (0)   👎
Felix1218 发表于 2021-12-6 23:25
请问楼主看面经准备是看几个月的呢?最近三个月吗 谢谢

我当时没看面经 面完才发现是别人面经里的
感觉看一两个月内的够了
回复

使用道具 举报

地里的匿名用户
匿名用户-CBE  发表于 2021-12-7 15:31:48
本楼: 👍   0% (0)
 
 
0% (0)   👎
AaLlC 发表于 2021-12-6 16:45
给一堆城市,并给出他们的推荐分数(越高越推荐),以及城市间的航班。让你选出四个城市旅游,使得总分数最 ...

思路差不多 时间复杂度我应该分析错了 面试官疯狂暗示应该和edge数有关
回复

使用道具 举报

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

本版积分规则

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