一亩三分地论坛

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

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

Snapchat电面

[复制链接] |试试Instant~ |关注本帖
jwl2006 发表于 2016-11-2 07:49:56 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 博士 全职@snapchat - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
刚结束电面,之前承诺地里一位分享面经的同学发面经。 面试官是位和善的中国小哥,题目是matrix里面找从高到低的最长路径。用了DFS,问了时间空间复杂度,要求优化,加了cache.祝大家好运!. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
wwtwxlwjh 发表于 2016-11-2 09:25:20 | 显示全部楼层
楼主能不能详细说说cache的做法。。看到好多面经说优化用cache。。。咋用啊。。。谢谢楼主!!
回复 支持 反对

使用道具 举报

luofeidream 发表于 2016-11-2 09:33:20 | 显示全部楼层
wwtwxlwjh 发表于 2016-11-2 09:25
楼主能不能详细说说cache的做法。。看到好多面经说优化用cache。。。咋用啊。。。谢谢楼主!!

找到从某个点出发的最长路径之后,把它保存起来,这样下次访问到这个点的时候可以直接返回之前存好的结果而避免重复计算~
回复 支持 反对

使用道具 举报

 楼主| jwl2006 发表于 2016-11-2 09:41:46 | 显示全部楼层
luofeidream 发表于 2016-11-2 09:33
找到从某个点出发的最长路径之后,把它保存起来,这样下次访问到这个点的时候可以直接返回之前存好的结果 ...

对的,我就是这样做的
回复 支持 反对

使用道具 举报

wwtwxlwjh 发表于 2016-11-2 09:47:27 | 显示全部楼层
luofeidream 发表于 2016-11-2 09:33
找到从某个点出发的最长路径之后,把它保存起来,这样下次访问到这个点的时候可以直接返回之前存好的结果 ...

哦哦 谢谢!
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-11-3 08:23:22 | 显示全部楼层
jwl2006 发表于 2016-11-2 09:41
对的,我就是这样做的

楼主,这题不优化的话,时间复杂度怎么达? 4^k?
回复 支持 反对

使用道具 举报

flashpacker 发表于 2016-11-3 08:37:15 | 显示全部楼层
这题用topo sort可以不..?感觉也可以试试?
回复 支持 反对

使用道具 举报

 楼主| jwl2006 发表于 2016-11-3 11:08:13 | 显示全部楼层
小A要当码农 发表于 2016-11-3 08:23
楼主,这题不优化的话,时间复杂度怎么达? 4^k?

时间复杂度是N*M*3^(N*M),这个时间复杂度好难。。。。我也没答对
回复 支持 反对

使用道具 举报

 楼主| jwl2006 发表于 2016-11-3 11:10:24 | 显示全部楼层
flashpacker 发表于 2016-11-3 08:37.鐣欏璁哄潧-涓浜-涓夊垎鍦
这题用topo sort可以不..?感觉也可以试试?

拓普怎么存路径?
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-11-3 23:42:07 | 显示全部楼层
jwl2006 发表于 2016-11-3 11:08
时间复杂度是N*M*3^(N*M),这个时间复杂度好难。。。。我也没答对
. Waral 鍗氬鏈夋洿澶氭枃绔,
嗯。 前半部分N*M是算上打印路径的时间了么? 楼主优化了以后应该就是O(NM)了吧
回复 支持 反对

使用道具 举报

shuiguo 发表于 2016-11-3 23:48:43 | 显示全部楼层
请问什么是“从高到低”??
回复 支持 反对

使用道具 举报

luofeidream 发表于 2016-11-4 01:55:13 | 显示全部楼层
小A要当码农 发表于 2016-11-3 23:42.鐣欏璁哄潧-涓浜-涓夊垎鍦
嗯。 前半部分N*M是算上打印路径的时间了么? 楼主优化了以后应该就是O(NM)了吧
. visit 1point3acres.com for more.
N*M应该是每个点都要算一遍产生的,因为每个点都要重新计算一遍
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-11-4 02:51:29 | 显示全部楼层
luofeidream 发表于 2016-11-4 01:55.鐣欏璁哄潧-涓浜-涓夊垎鍦
N*M应该是每个点都要算一遍产生的,因为每个点都要重新计算一遍

嗯。 理解了, 多谢!
回复 支持 反对

使用道具 举报

111180611 发表于 2016-11-4 02:54:37 | 显示全部楼层
电面之前有coding challenge吗?
回复 支持 反对

使用道具 举报

 楼主| jwl2006 发表于 2016-11-4 03:11:33 | 显示全部楼层
shuiguo 发表于 2016-11-3 23:48
请问什么是“从高到低”??

数字大小
回复 支持 反对

使用道具 举报

oldfish 发表于 2016-11-4 04:33:22 | 显示全部楼层
longest path in a directed graph

BFS 也比较容易 从图上最后的节点开始往前推,一直遍历完所有的节点
回复 支持 反对

使用道具 举报

 楼主| jwl2006 发表于 2016-11-4 06:04:17 | 显示全部楼层
111180611 发表于 2016-11-4 02:54
电面之前有coding challenge吗?

. From 1point 3acres bbs我没有。。
回复 支持 反对

使用道具 举报

ayagan 发表于 2016-11-4 06:13:35 | 显示全部楼层
楼主 想问下是求递减的最长路径的长度还是具体的路径?如果只是求长度, 是不是就另外建一个int[][] cache存, 如果是具体路径是不是得每个节点cache一个list....建一个List<Integer>[][]的东西....
回复 支持 反对

使用道具 举报

 楼主| jwl2006 发表于 2016-11-4 06:33:43 | 显示全部楼层
ayagan 发表于 2016-11-4 06:13
楼主 想问下是求递减的最长路径的长度还是具体的路径?如果只是求长度, 是不是就另外建一个int[][] cache ...

问的是长度,你的方案可行
回复 支持 反对

使用道具 举报

ayagan 发表于 2016-11-4 07:01:04 | 显示全部楼层
jwl2006 发表于 2016-11-4 06:33
问的是长度,你的方案可行
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
谢谢楼主!祝拿到offer!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 00:32

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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