一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1658|回复: 24
收起左侧

1030 Google电面 + 1029 L家

[复制链接] |试试Instant~ |关注本帖
kl_hrz 发表于 2015-10-31 03:15:16 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
刚面完,感觉跪了。
面试官是个在G家待了11年的小哥(?)


给一个Vector<vector<int>>表示一个房间,INT_MAX表示墙,INT_MIN表示各种equipment,0表示空位置。现在要放一个fountain,离所有equipment总距离最短。问放在哪里好。

LZ用的bfs(还不小心写成dfs了被小哥指出尼玛。。我刚要改,写了个queue,小哥说不用了这个改还要花点时间,我就直接注明你要用bfs了。。撞墙). Waral 鍗氬鏈夋洿澶氭枃绔,


follow up:时间复杂度,LZ说是O(mnk)。问有木有更快的,LZ并没直接想出来。小哥说可以bfs过程中做一下greedy(然而我总感觉这样不是optimal解),后来又说可以一开始就把任意两个点间距离算出来。
. 1point3acres.com/bbs
还有20分钟就开始让我问问题了,扯了10分钟小哥就说byebye了。。。

顺便,昨天L家,白人小哥面的。一题是找array里的unique elements,然后问文件操作题了,让返回一个log file里面所有的ip地址,同样ip只返回一次= =好久不用C++做文件操作了感觉非常虚。。
. From 1point 3acres bbs
哎。。。

评分

1

查看全部评分

本帖被以下淘专辑推荐:

dong882205 发表于 2015-10-31 03:27:35 | 显示全部楼层
楼主方便给个sample input吗? 没有理解这个"墙"的作用,挡水?还是说就只有四周是墙,没其他作用? 多谢啦!
回复 支持 反对

使用道具 举报

 楼主| kl_hrz 发表于 2015-10-31 04:14:07 | 显示全部楼层
dong882205 发表于 2015-10-31 03:27
楼主方便给个sample input吗? 没有理解这个"墙"的作用,挡水?还是说就只有四周是墙,没其他作用? 多谢啦!
. 鍥磋鎴戜滑@1point 3 acres
啊,就是遇到墙就要绕过去,四周肯定有,里面也可能有。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
比如M表示INT_MAX, N表示INT_MIN:
. Waral 鍗氬鏈夋洿澶氭枃绔,
M M M M M
M N  0 0  M
M M M 0  M. 鍥磋鎴戜滑@1point 3 acres
M N  0 0  M
M M M M M
回复 支持 反对

使用道具 举报

dong882205 发表于 2015-10-31 05:18:26 | 显示全部楼层
kl_hrz 发表于 2015-10-31 04:14
啊,就是遇到墙就要绕过去,四周肯定有,里面也可能有。

比如M表示INT_MAX, N表示INT_MIN:

噢懂了懂了,多谢!
回复 支持 反对

使用道具 举报

returning 发表于 2015-10-31 09:08:17 | 显示全部楼层
BFS是从多个equipment开始,对吧,关键问题是,当两个equipment做BFS到达同一个地点后,还不能停,因为还不知道其他equipment到这里的距离,所以空间要求很大啊,不是很好写code。
不知道我理解对了没有
谢谢了。
回复 支持 反对

使用道具 举报

 楼主| kl_hrz 发表于 2015-10-31 12:07:07 | 显示全部楼层
returning 发表于 2015-10-31 09:08
BFS是从多个equipment开始,对吧,关键问题是,当两个equipment做BFS到达同一个地点后,还不能停,因为还不 ...
. 鍥磋鎴戜滑@1point 3 acres
嗯你说的是对的。我是直接在原vector<vector>上修改的。
回复 支持 反对

使用道具 举报

孤笑客 发表于 2015-10-31 12:14:58 | 显示全部楼层
这道题最优解到底应该是啥
回复 支持 反对

使用道具 举报

A30041839 发表于 2015-10-31 12:17:33 | 显示全部楼层
从所有equipment出发做bfs,可以得到每个empty点到各equipment的最短距离,然后再扫一遍所有empty位置,求最短距离之和最小的位置,不知道思路对不对,请指教~~
回复 支持 反对

使用道具 举报

 楼主| kl_hrz 发表于 2015-10-31 12:22:15 | 显示全部楼层
孤笑客 发表于 2015-10-31 12:14. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
这道题最优解到底应该是啥

嗯其实我也不知道。小哥提供的两种我觉得第一种得到的不是最优解,第二种复杂度应该也不低就是了(至少也是m*n*k,算每一对点间距离我没想好怎么算比较快捷,不确定能不能dp)
回复 支持 反对

使用道具 举报

 楼主| kl_hrz 发表于 2015-10-31 12:23:02 | 显示全部楼层
A30041839 发表于 2015-10-31 12:17
从所有equipment出发做bfs,可以得到每个empty点到各equipment的最短距离,然后再扫一遍所有empty位置,求 ...
.1point3acres缃
我也是这样写的,就是面的时候脑一抽写了个recursion结果搞成dfs。。。
回复 支持 反对

使用道具 举报

孤笑客 发表于 2015-10-31 22:32:52 | 显示全部楼层
kl_hrz 发表于 2015-10-31 12:23
我也是这样写的,就是面的时候脑一抽写了个recursion结果搞成dfs。。。

请教一下,什么叫“从所有equipment除非做bfs"?能给个例子吗?
回复 支持 反对

使用道具 举报

孤笑客 发表于 2015-10-31 22:57:02 | 显示全部楼层
kl_hrz 发表于 2015-10-31 12:23
我也是这样写的,就是面的时候脑一抽写了个recursion结果搞成dfs。。。

是不是有n个equipments就得做n次bfs?
回复 支持 反对

使用道具 举报

hwberg 发表于 2015-11-1 00:38:18 | 显示全部楼层
感觉是LeetCode上walls and gates的变型, 有比bfs更好的吗
回复 支持 反对

使用道具 举报

 楼主| kl_hrz 发表于 2015-11-1 04:03:04 | 显示全部楼层
孤笑客 发表于 2015-10-31 22:57. 1point3acres.com/bbs
是不是有n个equipments就得做n次bfs?

我是这样写的…
回复 支持 反对

使用道具 举报

 楼主| kl_hrz 发表于 2015-11-1 04:07:05 | 显示全部楼层
hwberg 发表于 2015-11-1 00:38
感觉是LeetCode上walls and gates的变型, 有比bfs更好的吗

并不知道= =我是没想到不做bfs的好方法啦,虽然或许可能可以剪枝?
回复 支持 反对

使用道具 举报

returning 发表于 2015-11-1 12:50:36 | 显示全部楼层
hwberg 发表于 2015-11-1 00:38
感觉是LeetCode上walls and gates的变型, 有比bfs更好的吗

比那个难,那个东西,走到了一个格子,就不用再管那个格子了,而这个题需要一直bfs下去,否则你怎么知道哪一个到大家的和最小?
如果没有障碍物,问题也简单。
回复 支持 反对

使用道具 举报

A30041839 发表于 2015-11-3 08:10:10 | 显示全部楼层
感觉这个题还有个陷阱,就是如果一个equipment被墙包住了,墙外面还有equipment,那么就没有任何点可以到达所有的equipment。所以要同时维护一个count矩阵,记录每个empty spot被Hit的次数,只有hit的次数等于equipment的个数,才有解。
回复 支持 反对

使用道具 举报

 楼主| kl_hrz 发表于 2015-11-3 08:51:13 | 显示全部楼层
A30041839 发表于 2015-11-3 08:10
感觉这个题还有个陷阱,就是如果一个equipment被墙包住了,墙外面还有equipment,那么就没有任何点可以到达 ...

嗯,这个他后来让想test case的时候我说了一下,不过写的时候没写…
回复 支持 反对

使用道具 举报

billyli8866 发表于 2015-11-6 10:17:51 | 显示全部楼层
bfs的时候要怎么greedy一下?。。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 10:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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