【生活质量系列】评测几款用过的咖啡机

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 3221|回复: 10
收起左侧

Snapchat电面跪经

[复制链接] |试试Instant~
我的人缘0
wza13579 发表于 2016-10-9 11:11:00 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  70% (7)
 
 
30% (3)  踩

2016(7-9月) 码农类General 硕士 全职@Snapchat - 内推 - 技术电面  | Fail | fresh grad应届毕业生

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

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

x
测试岗技术电面,题目是在一个2D矩阵中,0表示墙,1表示路,请问从左边任意一点到右边任意一点的最短路。可以上下左右走,但是不能走走过的路。

1 0 0
1 1 0.本文原创自1point3acres论坛
0 1 1. 1point3acres

上面这种情况的最短路就是4,用广度优先的方法做,面试千万不能埋头写,要多和面试官沟通。

snapchat要求bugfree,我有bug调不出来跪了。。。

上一篇:vmware OCI OA
下一篇:10.7 fb店面

本帖被以下淘专辑推荐:

我的人缘0
penenda 发表于 2016-10-9 11:55:39 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  68% (435)
 
 
31% (197)  踩
LZ,我觉得广度搜索初始化把左边的1全装进去,然后board每个点都得维护一个和第一列长度相同的数组来记录从哪个点来的最短距离。是这个道理不?

或者第一列每个点都来一次。。

另外,LZ加油,祝你有好的运气!
回复

使用道具 举报

我的人缘0
zyoppy008 发表于 2016-10-9 12:17:05 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (56)
 
 
8% (5)  踩
penenda 发表于 2016-10-9 11:55.本文原创自1point3acres论坛
LZ,我觉得广度搜索初始化把左边的1全装进去,然后board每个点都得维护一个和第一列长度相同的数组来记录从 ...
. visit 1point3acres for more.
你那个每个board点 维护数组有啥用 空间复杂度太高了 难得不是直接装左边的1 bfs 碰到右边返回就行 装的是string就可以了
回复

使用道具 举报

我的人缘0
penenda 发表于 2016-10-9 12:21:34 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  68% (435)
 
 
31% (197)  踩
zyoppy008 发表于 2016-10-9 12:17-google 1point3acres
你那个每个board点 维护数组有啥用 空间复杂度太高了 难得不是直接装左边的1 bfs 碰到右边返回就行 装的 ...

左边任意一点到右边任意一点你怎么存?就楼主这个例子,第一个1在第一次广度搜索就碰到下边那个已经visit了的。 那么我如果要知道左上的1到右下1,你如何计算?
. Waral 博客有更多文章,
补充内容 (2016-10-9 12:24):
等等,我们理解似乎不太一样。我的理解是最后两两之间所有路径求最短。 LZ的意思应该是这个所有左边去右边的各种路径的最短。是后者就装进去bfs一次就行
回复

使用道具 举报

我的人缘0
yangmyfly 发表于 2016-10-9 12:46:51 来自手机 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (17)
 
 
0% (0)  踩
penenda 发表于 2016-10-9 12:21
左边任意一点到右边任意一点你怎么存?就楼主这个例子,第一个1在第一次广度搜索就碰到下边那个已经visit ...

人家只问最短距离是多少就啥都不用存吧,直接左边一列bfs,如果想知道路径用hashmap存父节点的所有可能吧

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
steveguang 发表于 2016-10-9 13:01:40 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (87)
 
 
4% (4)  踩
问下楼主不能走走过的路什么意思?
回复

使用道具 举报

我的人缘0
zyoppy008 发表于 2016-10-9 15:03:27 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (56)
 
 
8% (5)  踩
penenda 发表于 2016-10-9 12:21
左边任意一点到右边任意一点你怎么存?就楼主这个例子,第一个1在第一次广度搜索就碰到下边那个已经visit ...

肯定是左边任意点到右边任意点啊。 path用string 存起来不就行了吗。。。数组也行。
回复

使用道具 举报

我的人缘0
kayv 发表于 2016-10-9 21:00:09 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  60% (3)
 
 
40% (2)  踩
如果是任意一点到任意一点的最短路径,应该是先转换成graph,再floyed算法了

With React+D3v4 you'll learn the basics of building fast data visualization components in about an hour.

回复

使用道具 举报

我的人缘0
 楼主| wza13579 发表于 2016-10-10 00:18:59 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  70% (7)
 
 
30% (3)  踩
steveguang 发表于 2016-10-9 13:01
问下楼主不能走走过的路什么意思?

其实走过的路也可以走,只不过你走重复的路肯定就不是最短路了
回复

使用道具 举报

我的人缘0
 楼主| wza13579 发表于 2016-10-10 00:22:59 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  70% (7)
 
 
30% (3)  踩
https://leetcode.com/problems/walls-and-gates/ 大致上就是leetcode这道题的变种,变成gate都在最左边,问你更新完后最右边那列的最小值是多少
回复

使用道具 举报

我的人缘0
ggwzjhgsq 发表于 2016-10-10 00:40:45 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  93% (15)
 
 
6% (1)  踩
LZ不需要担心
我Snapchat题都没做出来还过了。。。不知道他们怎么想的

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|一亩三分地论坛声明

GMT+8, 2018-9-23 10:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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