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

Snapchat电面

全局:

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

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

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

x
刚结束电面,之前承诺地里一位分享面经的同学发面经。
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
cache.祝大家好运!

评分

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

查看全部评分


上一篇:zillow店面
下一篇:Facebook 面试有一轮不好会不会跪
推荐
FTD2014 2016-11-8 10:27:55 | 只看该作者
全局:
  1. public class Solution {
  2.     private int[] dx = {-1, 1, 0, 0};
  3.     private int[] dy = {0, 0, -1, 1};
  4.     public int longestIncreasingPath(int[][] matrix) {
  5.         if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
  6.             return 0;
  7.         }
  8.         int max = 0;
  9.         int[][] dp = new int[matrix.length][matrix[0].length];
  10.         for(int i = 0; i < matrix.length; i++) {
  11.             for(int j = 0; j < matrix[0].length; j++) {
  12.                 max = Math.max(max, dfs(matrix, i, j, dp));
  13.             }
  14.         }
  15.         return max;
  16.     }
  17.     private int dfs(int[][] matrix, int i, int j, int[][] dp) {
  18.         if(dp[i][j] != 0) {
  19.             return dp[i][j];
  20.         }
  21.         for(int k = 0; k < 4; k++) {
  22.             int x = i + dx[k];
  23.             int y = j + dy[k];
  24.             if(x >= 0 && x < matrix.length && y >= 0 && y < matrix[0].length && matrix[i][j] < matrix[x][y]) {
  25.                 dp[i][j] = Math.max(dp[i][j], dfs(matrix, x, y, dp));
  26.             }
  27.         }
  28.         return ++dp[i][j];
  29.     }
  30. }
复制代码
回复

使用道具 举报

推荐
gretchency 2016-11-14 08:47:36 | 只看该作者
全局:
  1. if(x >= 0 && x < matrix.length && y >= 0 && y < matrix[0].length && matrix[i][j] < matrix[x][y]) {
  2.                 dp[i][j] = Math.max(dp[i][j], dfs(matrix, x, y, dp));
  3.             }
复制代码
感觉这里用不着max比一下,直接 dp[i][j] = dfs();

补充内容 (2016-11-14 08:59):
我的我的 要比一下的 比一下知道四个方向最长可以得到几~
回复

使用道具 举报

推荐
luofeidream 2016-11-2 09:33:20 | 只看该作者
全局:
wwtwxlwjh 发表于 2016-11-2 09:25
楼主能不能详细说说cache的做法。。看到好多面经说优化用cache。。。咋用啊。。。谢谢楼主!!

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

使用道具 举报

🔗
wwtwxlwjh 2016-11-2 09:25:20 | 只看该作者
全局:
楼主能不能详细说说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
找到从某个点出发的最长路径之后,把它保存起来,这样下次访问到这个点的时候可以直接返回之前存好的结果 ...

哦哦 谢谢!
回复

使用道具 举报

全局:
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可以不..?感觉也可以试试?

拓普怎么存路径?
回复

使用道具 举报

全局:
jwl2006 发表于 2016-11-3 11:08
时间复杂度是N*M*3^(N*M),这个时间复杂度好难。。。。我也没答对

嗯。 前半部分N*M是算上打印路径的时间了么? 楼主优化了以后应该就是O(NM)了吧
回复

使用道具 举报

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

本版积分规则

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