Google8.6 热滚滚的面经

今天下午4:15面的，估计是个白人大哥，人挺耐心但自己水平太差被虐的体无完肤。。。
问一个二维数组表示的n*n的矩阵，找出一条连续的最长的路径的长度。
比如
7

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

（0， 0）开始就崩溃了。。。写了个暴力算法，让优化，估计GG了。。

对，这题楼上的童鞋们已经提到了，用记忆化搜索能够很快的解决，需要用到dfs和HashMap。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

用TreeMap行吗？ 帮我看看呗：

1. public static int longestPath(int[][] array){
   
2.         if(array == null || array.length == 0 || array[0].length == 0) return 0;
   
3.         TreeMap<Integer, Integer> tree = new TreeMap<Integer, Integer>();   // <current, next>
   
4.         for(int i = 0; i < array.length; i++){
   
5.             for(int j = 0; j < array[0].length; j++){
   
6.                 int cur = array[i][j];
   
7.                 if(hasNext(array, i, j)){
   
8.                     tree.put(cur, cur + 1); // pair current and next
   
9.                 }else{
   
10.                     tree.put(cur, cur); // no path
    
11.                 }
    
12.             }
    
13.         }
    
14.         int result = 0;
    
15.         int sum = 0;    // number of path, not dot
    
16.         while(!tree.isEmpty()){
    
17.             int curKey = tree.firstKey();
    
18.             int curVal = tree.get(curKey);
    
19.             if(curKey + 1 == curVal){   // has one path
    
20.                 sum++;
    
21.                 result = Math.max(result, sum);
    
22.                 tree.remove(curKey);
    
23.                 if(!tree.isEmpty()){    // may have further path
    
24.                     int nextKey = tree.firstKey();
    
25.                     if(curVal != nextKey){  // actually not
    
26.                         sum = 0;
    
27.                     }
    
28.                 }
    
29.             }else{
    
30.                 tree.remove(curKey);
    
31.             }
    
32.         }
    
33.         return result + 1;  // number of node == path + 1
    
34.     }
    
35. 
    
36.     private static boolean hasNext(int[][] array, int row, int col){
    
37.         int cur = array[row][col];
    
38.         if(row > 0 && array[row - 1][col] == cur + 1) return true;
    
39.         if(col > 0 && array[row][col - 1] == cur + 1) return true;
    
40.         if(row < array.length - 1 && array[row + 1][col] == cur + 1) return true;
    
41.         if(col < array[0].length - 1 && array[row][col + 1] == cur + 1) return true;
    
42.         return false;
    
43.     }

复制代码

时间复杂度是O(n^2)吧？

这又来滑雪了。

poj 1088 滑雪 经典题啊

eval 发表于 2015-8-7 06:00
poj 1088 滑雪 经典题啊

哪里有这道题的解法呢？谢谢

blessed, and good luck

这道题是lintcode里面的Longest Increasing Continues Subsequences II, 解法主要就是DP+Recursion. 本来想把我以前写的代码贴出来，发现lint code现在好像和leetcod一样也是会员制了，果然天下没有免费午餐了。以后都不知道去哪儿刷题了，蛋疼！！！

yemingliang 发表于 2015-8-7 09:35
这道题是lintcode里面的Longest Increasing Continues Subsequences II, 解法主要就是DP+Recursion. 本来想 ...

怎么会员制了。。。我的完全没变啊。。难道是因为之前都刷过了？

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

woshiee123 发表于 2015-8-7 08:48
哪里有这道题的解法呢？谢谢

google下POJ 1088就有了。

可能是昨天他服务器出问题，刚发现好像又能刷了！多谢楼主提醒