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

狗狗店面

全局:

2022(4-6月) 码农类General 硕士 全职@google - 内推 - 技术电面  | 😃 Positive 😐 Average | Other | 在职跳槽

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

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

x
新鲜店面,应该是国人小姐姐,很友好很helpful,题目是
您好!
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies

体验很好,希望能过去VO,加油加油!

评分

参与人数 3大米 +7 收起 理由
Falldawn + 1 给你点个赞!
匿名用户-30MHJ + 4
pacemak1r + 2 很有用的信息!

查看全部评分


上一篇:雪花店面+昂赛 时间线
下一篇:Indeed karat 新鲜电面 求加米!
地里匿名用户
推荐
匿名用户-AKLWE  2022-4-12 00:15:58
本帖最后由 匿名 于 2022-4-11 09:25 编辑
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <climits>
  5. #include <array>

  6. using namespace std;

  7. int bfs(vector<vector<int>>& g) {
  8.     int m = g.size();
  9.     int n = g[0].size();
  10.     vector<vector<int>> dist(m, vector<int>(n, m * n + 1));
  11.     queue<array<int,2>> q;
  12.     dist[0][0] = g[0][0];
  13.     q.push({0, 0});
  14.     int dir[] = {-1, 0, 1, 0, -1};
  15.     while(!q.empty()) {
  16.         auto h = q.front();
  17.         q.pop();
  18.         for(int i = 0; i < 4; i++) {
  19.             int x = h[0] + dir[i];
  20.             int y = h[1] + dir[i+1];
  21.             if(x < 0 || x >= m || y < 0 || y >= n || dist[x][y] <= dist[h[0]][h[1]] + g[x][y]) continue;
  22.             dist[x][y] = dist[h[0]][h[1]] + g[x][y];
  23.             q.push({x, y});
  24.         }
  25.     }

  26.     for(auto& t : dist) {
  27.         for(auto& x : t) cout << x << ","; cout << endl;
  28.     }
  29.     return dist[m-1][n-1];
  30. }

  31. int main()
  32. {
  33.     vector<vector<int>> a = {
  34.         { 0, 1, 0, 1, 0, 0 },
  35.         { 1, 1, 0, 1, 0, 0 },
  36.         { 0, 0, 0, 1, 0, 0 },
  37.         { 1, 1, 1, 1, 1, 1 },
  38.         { 0, 0, 0, 0, 1, 1 }
  39.     };


  40.     cout<< bfs(a);

  41.     return 0;
  42. }
复制代码

评分

参与人数 1大米 +4 收起 理由
匿名用户-30MHJ + 4

查看全部评分

回复

使用道具 举报

推荐
 楼主| 微信用户_0b7b21b 2022-4-12 03:30:54 | 只看该作者
全局:
匿名者 发表于 2022-4-11 15:27
followup, how to do O(NLogN)???

followup 没有明确说要求的time complexity,就是问怎么解,能不能别的更好的解法这样
回复

使用道具 举报

推荐
 楼主| 微信用户_0b7b21b 2022-4-12 02:52:01 | 只看该作者
全局:
匿名者 发表于 2022-4-11 13:11
感觉是刷题网常见题 要尔酒散

对,第一问是幺儿就散,followup的话用二分就是nLog(n), weighted graph会更好一些
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-WDCY2  2022-4-12 00:03:12
follow up 可不可以用二分加dfs或bfs?
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-AKLWE  2022-4-12 00:31:02
匿名者 发表于 2022-4-11 09:03
follow up 可不可以用二分加dfs或bfs?

直接BFS就行的。
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-2CRUG  2022-4-12 01:11:28 来自APP
感觉是刷题网常见题 要尔酒散

评分

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

查看全部评分

回复

使用道具 举报

地里匿名用户
🔗
匿名用户-X9QUC  2022-4-12 03:27:02
followup, how to do O(NLogN)???
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-X9QUC  2022-4-12 03:52:10

but this is not dijkstra, isn't it?
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-VU9WP  2022-4-12 05:43:08 来自APP
同觉得follow up可以二分+bfs/dfs
回复

使用道具 举报

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

本版积分规则

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